数据结构-第七章图(图的定义存储实现和图的遍历)描述PPT课件

,1、图的定义和术语2、图的存储结构3、图的遍历4、图的连通性问题5、有向无环图及其应用6、最短路径,第七章图,7.1.1图的定义,图（Graph）是一种网状数据结构，其形式化定义如下：Graph=(V,R)V=x|xDataObjectR=VR/数据关系VR=|P(x,y)(x,yV)DataObject：是一个集合，该集合中的所有元素具有相同的特性。V：中的数据元素通常称为顶点（Vertex）（图中的顶点）。VR：是两个顶点之间的关系的集合。P(x,y)：表示x和y之间有特定的关联属性P。,7.1.1图的定义,若VR，则表示从顶点x到顶点y的弧(Arc)，称x为弧尾(Tail)或起始点，称y为弧头(Head)，或终端点。此时图中的弧是有方向的，此时的图称为有向图(Digraph)。若VR，必有VR，即VR是对称关系，这时以无序对(x,y)来代替两个有序对，表示x和y之间的一条边(Edge)，此时的图称为无向图(Undigraph)。,7.1.1图的定义,图的基本操作和其它数据结构一样，也有创建、插入、删除、查找等。图的抽象类型定义和基本操作如P156所示。,7.1.2图的基本术语,图邻接点路径和回路度权与网生成树,7.1.2图的基本术语,无向图：若VR，必有VR，即VR是对称关系，这时以无序对(x,y)来代替两个有序对，表示x和y之间的一条边（Edge），此时的图称为无向图。,7.1.2图的基本术语,若VR，则表示从顶点x到顶点y的弧(Arc)，称x为弧尾(Tail)或起始点，称y为弧头(Head)，或终端点（箭头指向的点）。图中的边是有方向的，此时的图称为有向图(Digraph)。,7.1.2图的基本术语,A,B,C,D,A,B,C,D,E,有向图G1,无向图G2,结点(顶点),有向边（弧）、弧尾(初始结点)、弧头(终止结点),A,B,A,B,有向图：G1=(V1，E1)V1=A,B,C,DE1=,结点(顶点),边(无向边),A,B,无向图：G2=(V2，E2)V2=A,B,C,D,EE2=(A,B),(A,C),(B,D),(B,E）,(C,E),(D,E),A,B,7.1.2图的基本术语,完全图有向完全图：有n(n-1)条边（图中每个顶点和其余n-1个顶点都有弧相连）的有向图为有向完全图。,7.1.2图的基本术语,完全图无向完全图：有n(n-1)/2条边（图中每个顶点和其余n-1个顶点都有边相连）的无向图为无向完全图（或称为完全图）。,注意：对于有很少条边的图（enlogn）称为稀疏图，反之称为稠密图。,7.1.2图的基本术语,子图：设有两个图G=(V,E)和图G=(V,E)，若VV，且EE，则称图G为G的子图。,A,B,C,D,无向图G2,A,A,C,D,A,C,A,B,C,D,有向图G1的子图,A,B,C,D,E,A,B,D,E,A,A,B,C,D,A,B,C,D,E,无向图G2的子图,有向图G1,7.1.2图的基本术语,连通图：在无向图G=(V,E)中，若从vi到vj有路径相通，则称顶点vi与vj是连通的。如果对于图中的任意两个顶点vi、vjV，vi,vj都是连通的，则称该无向图G为连通图。,7.1.2图的基本术语,连通分量：无向图中的极大连通子图称为该无向图的连通分量。,7.1.2图的基本术语,强连通图：在有向图G=(V,A)中，若对于每对顶点vi、vjV且vivj，从vi到vj和vj到vi都有路径，则称该有向图为强连通图。,7.1.2图的基本术语,强连通分量：有向图的极大强连通子图称作有向图的强连通分量。,7.1.2图的基本术语,邻接点对于无向图G=(V,E)，如果边(v,v)E，则称顶点v,v互为邻接点，即v,v相邻接。边（v,v）依附于顶点v和v，或者说边（v,v）与顶点v和v相关联。对于有向图G=(V,A)而言，若弧A，则称顶点v邻接到顶点v，顶点v邻接自顶点v，或者说弧与顶点v,v相关联。,7.1.2图的基本术语,路径和回路路径路径长度回路或环简单路径简单回路,7.1.2图的基本术语,路径无向图路径：无向图G=(V,E)中从顶点v到v的路径是一个顶点序列（v=vi,0,vi,1,vi,2,.,vi,m=v)，其中(vi,j-1,vi,j)E,1jm。有向图路径：如果图G是有向图，则路径也是有向的，顶点序列应满足A，1jm。路径长度：指路径上经过的弧或边的数目。简单路径：若表示路径的顶点序列中的顶点各不相同，则称这样的路径为简单路径。,7.1.2图的基本术语,回路或环：在一个路径中，若其第一个顶点和最后一个顶点是相同的，即v=v，则称该路径为一个回路或环。简单回路（简单环）：除了第一个和最后一个顶点外，其余各顶点均不重复出现的回路为简单回路。,7.1.2图的基本术语,度无向图的度：顶点v的度是指和v相联的边的数目，记作TD(v)。有向图的度：对于有向图而言顶点v的度有出度和入度两部分：以顶点v为弧头的弧的数目称为该顶点的入度，记作ID(V)；以顶点v为弧尾的弧的数目称为该顶点的出度，记作OD(v)；则顶点v的度为TD(v)=ID(v)+OD(v)度的计算公式：如果顶点vi的度记为TD(vi)，那么一个有n个顶点，e条边或弧的图，满足如下关系：,7.1.2图的基本术语,权：在实际应用中，有时图的边或弧上往往与具有一定意义的数有关，即每一条边都有与它相关的数，称为权。这些权可以表示从一个顶点到另一个顶点的距离或耗费等信息。将这种带权的图称做网或赋权图。,7.1.2图的基本术语,生成树：一个连通图的生成树是指一个极小连通子图，它含有图中的全部n个顶点，但只有足以构成一棵树的n-1条边。,注意：1.在生成树中添加一条边之后，必定会形成回路或环。2.一颗有n个顶点的生成树有且仅有n-1条边。3.如果一个图有n个顶点和小于n-1条边，则它必是非连通图。,7.2图的存储结构,7.2.1、邻接矩阵和加权邻接矩阵（labeledadjacencymatrix）,定义：采用两个数组来表示图一个是用于存储顶点信息的一维数组；另一个是用于存储图中顶点之间关联关系的二维数组，该数组被称为邻接矩阵。（边或弧的关系）,图的常用存储形式：7.2.1邻接矩阵和加权邻接矩阵（数组表示法）7.2.2邻接表,7.2图的存储结构,表示：若图G是一个有n个顶点的无权图，G的邻接矩阵是如下性质的nn矩阵A：注意：Aii=0。,无权值的无向图的邻接矩阵设无向图有n个结点，则用n行n列的矩阵A表示该无向图；如果i至j有一条边,则Aij=1；否则，Aij=0注意：Aii=0。i结点的度:i行或i列之和。为对称矩阵。,表示成右图矩阵,0110010011100010100101110,A,B,C,D,E,对称矩阵,01234,01234,7.2图的存储结构,表示：若图G是一个有n个顶点的网（加权图），G的邻接矩阵是如下性质的nn矩阵A：注意：Aii=。,图的加权邻接矩阵设图有n个顶点，则用n行n列的矩阵A表示该图；如果i至j有一条边（弧）且它的权值为w。则Aij=w;否则，Aij=（或其它标志）；,a,b,0123,0123,7.2图的存储结构,C语言描述：/-图的数组（邻接矩阵）存储表示-#defineINFINITYINT_MAX/最大值#defineMAX_VERTEX_NUM20/最大顶点个数typedefenumDG,GN,UDG,UDNGraphKind;/有向图，有向网，无向图，无向网typedefstructArcCellVRTypeadj;/顶点关系类型，对无权图，用1或0表示相邻否；/对带权图，则为权值类型。InfoType*info;/该弧相关信息的指针ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedefstructVertexTypevexsMAX_VERTEX_NUM;/顶点向量AdjMatrixarcs;/邻接矩阵intvernum,arcnum;/图的当前顶点数和弧数GraphKindkind;/图的种类标志MGraph;,7.2图的存储结构,邻接矩阵表示法的特点：1.存储空间便于计算1）无向图：邻接矩阵是对称矩阵，可采用压缩存储法（下三角或上三角），其存储空间只需存放n个顶点信息和n(n-1)/2个弧信息的存储空间。2）有向图：邻接矩阵不一定是对称矩阵，所以需存放n个顶点信息和n2个弧信息的存储空间。,7.2图的存储结构,邻接矩阵表示法的特点：2.便于运算1）便于判定图中任意两个顶点之间是否有边（或弧）相连，即根据Aij=0或1（和wi,j）来判断。2）便于求得各个顶点的度。无向图：其邻接矩阵第i行（或列）元素之和就是图中第i个顶点的度：有向图：第i行元素之和就是图中第i个顶点的出度；第i列元素之和就是图中第i个顶点的入度；,7.2图的存储结构,邻接矩阵表示法的特点：3.便于实现一些基本操作如FirstAdjVertex(G,v)：找v的第一个邻接点（1）首先，LocateVertex(G,v）找到v在图中的位置，即v在一维数组vexs（顶点向量）中的序号i；（2）二维数组arcs（邻接矩阵）中第i行上第一个adj域非零（为“1”）的分量所在的列号j，便是v的第一个邻接点在图G中的位置。（3）取出一维数组vexsj中的数据信息，即与顶点v邻接的第一个邻接点的信息。,图的建立：图顶点号从1开始计，数组下标按C/C+习惯从0计算,#defineMAXINT(1sizeof(int)*8-1)-1CreateGraph(aVexNuM,e)/VexNuM-图的顶点数,e-边（弧）数for(i=0;iVexNuM;i+)for(j=0;jVexNuM;j+)aij=INFINITY;for(k=1;k=e;k+)cinijw;/读入顶点号i,j和边上权wai-1j-1=w;aj-1i-1=w;/无向网,2147483647,P162示例：,P162示例：,7.2.2、邻接表,设图具有n个结点，则用顶点数组表、边（弧）表表示该有向图或无向图。顶点数组表：用数组存放所有的顶点。数组大小为图顶点数n。边表（边结点表，表结点表）：每条边用一个结点进行表示。同一个结点的所有的边形成它的边结点单链表。,它实际上是图的一种链式存储结构。其基本思想是只存有关联的信息，对于图中存在的边信息则存储，而对于不相邻接的顶点则不保留信息。,实例：,adj,数组下标,结点值,数组下标,结点值,7.2图的存储结构,C语言描述：/-图的邻接表存储表示-#defineMAX_VERTEX_NUM20/最大顶点个数typedefstructArcNode/定义表结点intadjvex;/该弧所指向的顶点的位置structArcNode*nextarc;/指向下一条弧的指针InfoType*info;/该弧相关信息的指针ArcNode;typedefstructVNode/定义头结点VertexTypedata;/顶点信息ArcNode*firstarc;/指向第一条依附该顶点的弧的指针VNode,AdjListMAX_VERTEX_NUM;typedefstructAdjListvertices;/头结点向量intvernum,arcnum;/图的当前顶点数和弧数intkind;/图的种类标志ALGraph;,7.2图的存储结构,存储空间：对于有n个顶点，e条边的图而言，若采取邻接表作为存储结构：无向图，则需要n个表头结点和2e个表结点。所以在边稀疏的情况下，采用邻接表表示图比邻接矩阵节省存储空间。有向图，则需要n个表头结点和e个表结点。,12,4,7.2图的存储结构,图的度：在无向图的邻接表中，顶点vi的度就是第i个边链表上结点的个数。在有向图中，第i个边链表上顶点的个数是顶点vi的出度。要想求得该顶点的入度，则必须遍历整个邻接表。在所有单链表中查找邻接点域的值为i的结点并计数求和。由此可见，对于用邻接表方式存储的有向图，求顶点的入度并不方便，它需要扫描整个邻接表才能得到结果。解决的方法：采用逆邻接表法，对每个顶点vi建立一个所有以顶点vi为弧头的弧的表。这样求顶点vi的入度即是计算逆邻接表中第i个顶点的边链表中结点的个数。,有向图邻接表建立,voidCreate(Graph,#definemax20typedefstructArcNode/表结点intadjvex;ArcNode*nextarc;/省略与弧相关信息定义ArcNode;typedefstructVexnode/头结点intdata;ArcNode*firstarc;Vexnode;Typedefstruct/有向图Vexnodeadjmax;intn,e;/省略定义图的类型Graph;,头结点数据与顶点的编号有关时的头插入法（v-1，u-1）,#definemax20typedefstructArcNode/表结点intadjvex;ArcNode*nextarc;ArcNode;typedefstructVexnode/头结点intdata;ArcNode*firstarc;Vexnode;Typedefstruct/有向图Vexnodeadjmax;intn,e;Graph;,intsearch(GraphG,Telemtypee)for(inti=0;iG.n;i+)if(G.adji.data=e