《数据结构课件、代码》第5章图.ppt
第5章 图,张成文北京邮电大学计算机学院,数据结构-第5章 图,2,5.1 图的基本概念,非线性结构，数据元素之间呈多对多的关系。5.1.1 图的定义Graph=(V,VR)V：顶点(数据元素)的有穷非空集合。VR：弧(关系)的有穷集合。,数据结构-第5章 图,3,例1：G1=(V1,VR1),V1=A,B,C,D,EVR1=,例2：G2=(V2,VR2),V2=A,B,C,D,E,FVR2=(A,B),(A,E),(B,E),(C,D),(D,F),(B,F),(C,F),数据结构-第5章 图,4,5.1.2 图的相关术语,顶点 数据元素所构成的结点。有向图 弧的顶点偶对是有序的。对弧而言，vi是弧尾/初始点；vj是弧头/终端点。无向图 弧的顶点偶对是无序的。(vi,vj)和(vj,vi)代表同一条边(ij)。(无向)完全图 每个顶点与其余顶点都有边的无向图。顶点数为n时，边数 e=n(n-1)/2有向完全图 每个顶点与其余顶点都有弧的有向图。顶点数为n时，弧数 e=n(n-1)稀疏图 有很少边或弧的图。（enlogn）稠密图 有较多边或弧的图。,vi vj,数据结构-第5章 图,5,权 图中的边或弧具有一定的大小的概念。网 边/弧带权的图。邻接 有边/弧相连的两个顶点之间的关系。存在(vi,vj)，则称vi和vj互为邻接点；存在，则称vi邻接到vj，vj邻接于vi 关联(依附)边/弧与顶点之间的关系。存在(vi,vj)/，则称该边/弧关联于vi和vj顶点的度 与该顶点相关联的边的数目，记为D(v)。入度ID(v)：有向图中，以该顶点为弧头的弧数目。出度OD(v)：有向图中，以该顶点为弧尾的弧数目。,数据结构-第5章 图,6,路径 接续的边构成的顶点序列。路径长度 路径上边或弧的数目/权值之和。回路(环)第一个顶点和最后一个顶点相同的路径。简单路径 序列中顶点均不相同的路径。简单回路(简单环)除路径起点和终点相同外，其余顶 点均不相同的路径。,数据结构-第5章 图,7,连通图 无向图中，任何一对顶点间都存在路径。连通分量 无向图中的极大连通子图。强连通图 有向图中，任何一对顶点间都存在路径。强连通分量 有向图中的极大连通子图。,数据结构-第5章 图,8,子图 对于图G=(V,E)和G=(V,E)，如果VV，E E，且E关联的顶点都在V中，则称G是G的子图。生成子图 由图的全部顶点和部分边组成的子图称为原图的生成子图。生成树 包含图中全部顶点的极小连通子图。有向树 图中恰有一个顶点入度为0，其余顶点入度均为1。生成森林 有向图中，包含所有顶点的若干棵有向树构成的子图。,数据结构-第5章 图,9,5.2 图的存储结构,5.2.1 数组/邻接矩阵 表示法(顺序存储方式),数据结构-第5章 图,10,5.2.2 邻接表 顺序存储+链式存储,顶点顺序表 邻接顶点的单链表(边表)G1:0 A 1 2 1 B 0 2 3 2 C 0 1 3 3 D 1 2 G2:0 A 1 3 2 2 1 B 3 4 2 C 1 5 3 D 2 2 出边表(逆邻接表时用入边表),nextarc,adjvex,nextarc,weight,adjvex,无向图,有向网,vertices,数据结构-第5章 图,11,5.3 图的遍历,深度优先遍历(树的先根遍历的推广)广度优先遍历(树的按层次遍历的推广)例,v1,v2,v3,v4,v5,v6,v7,v8,深度：v1 v2 v4 v8 v5 v6 v3 v7,广度：v1 v2 v3 v4 v5 v6 v7 v8,设从v1出发遍历,数据结构：主图的存储结构 辅数组 visited0.n-1,数据结构-第5章 图,12,5.3.1 深度优先搜索,递归的算法思想(1)访问顶点v，并记录v已被访问(2)依次从v的未访问的邻接点出发，深度优先搜索图G。算法描述,typedef enumFALSE,TRUE Boolean;/FALSE为0，TRUE为1Boolean visitedMAX_VERTEX_NUM;/辅助访问标志向量void DFSTraverse(Graph G)for(v=0;vG.vexnum;+v)visitedv=FALSE;/标志向量初始化 for(v=0;vG.vexnum;+v)if(!visitedv)DFS(G,v);/DFSTraverse,数据结构-第5章 图,13,void DFS(Graph G,int v)visit(v);visitedv=TRUE;/访问顶点v，并标记 for(w=FirstAdjVex(G,v);w-1;w=NextAdjVex(G,v,w)if(!visitedw)DFS(G,w);/DFS,void DFS(MGraph G,int v)/深度优先遍历邻接矩阵表示的图 visit(G.vexsv);visitedv=TRUE;for(j=0;jG.vexnum;+j)if(G.arcsvj!=0/DFS,void DFS(ALGraph G,int v)/深度优先遍历邻接表表示的图 visit(G.verticesv.data);visitedv=TRUE;p=G.verticesv.firstarc;/取v边表的头指针 while(p)if(!visitedp-adjvex)DFS(G,p-adjvex);p=p-nextarc;/DFS,例,数据结构-第5章 图,14,T,T,T,T,T,T,T,T,T,a,c,h,d,k,f,e,b,g,a,c,h,k,f,e,d,b,g,访问标志:,访问次序:,例,a,c,h,d,k,f,e,数据结构-第5章 图,15,5.3.2 广度(宽度)优先遍历,算法思想(1)访问顶点v，并记录它已被访问；顶点v入队列；(2)如果队列空，则退出；否则，从队中取出一顶点；(3)求该顶点的一个邻接点；如果此邻接点未被访问，则访问它，并记录它已被访问，将其入队列；(4)如果该顶点还有下一个邻接点，则转(3)；否则，转(2),数据结构-第5章 图,16,算法描述,void BFSTraverse(Graph G)for(v=0;v-1;w=NextAdjVex(G,u,w)if(!visitedw)visitedw=TRUE;visit(w);EnQueue(Q,w);/BFSTraverse,数据结构-第5章 图,17,算法时间复杂度分析 与深度优先遍历过程相同 5.3.3 图的遍历小结深度优先遍历算法借助于栈结构实现；广度优先遍历算法借助于队列结构实现图的遍历序列与算法和存储方式有关,数据结构-第5章 图,18,5.3.4 图的遍历应用举例,例1 求一条从顶点 i 到顶点 s 的简单路径,b-k,从b出发深度优先搜索遍历：,假设找到的第一个邻接点是a,且得到的结点访问序列为:b a d h c e k f g,假设找到的第一个邻接点是c,则得到的结点访问序列为:b c h d a e k f g,结论:1.从顶点 i 到顶点 s,若存在路径，则从顶点 i 出发进行深度优先搜索，必能搜索到顶点 s。2.遍历过程中搜索到的顶点不一定是路径上的顶点。3.由它出发进行的深度优先遍历已经完成的顶点不是路径上的顶点。,数据结构-第5章 图,19,例2 求两个顶点之间的一条路径长度最短的路径,因此，求路径长度最短的路径可以基于广度优先搜索遍历进行，但需要修改链队列的结点结构及其入队列和出队列的算法。,深度优先搜索访问顶点的次序取决于图的存储结构，而广度优先搜索访问顶点的次序是按“路径长度”渐增的次序。,数据结构-第5章 图,20,求右图中顶点 3 至顶点 5 的一条最短路径。,链队列的状态如下所示:,
