数据结构-图的遍历.ppt

《数据结构-图的遍历.ppt》由会员分享，可在线阅读，更多相关《数据结构-图的遍历.ppt（50页珍藏版）》请在三一办公上搜索。

1、图的遍历,深度优先搜索,广度优先搜索,图的遍历,小结和作业,复习,课堂练习,复习-图的存储结构,复习-图的存储结构,复习-图的存储结构,复习-图的存储结构,复习-图的存储结构,复习-图的存储结构,mark ivex ilink jvex jlink,复习-图的存储结构,0 1 2,存储结构的比较,邻接矩阵可用于DG、UDG、DN、UDN邻接表可用于DG、UDG、DN、UDN十字链表用于DG和DN邻接多重链表用于UDG和UDN,一、应用范围,存储结构的比较,邻接矩阵:n+n2邻接表用于DG和DN：n+e或者n+2e；用于UDG和UDN：n+2e十字链表:n+e邻接多重链表:n+e,二、存储空间,

2、存储结构的比较,三、对操作的支持,1、对顶点的访问,LocateVex(G,u);/返回u的位置,GetVex(G,v);/返回 v 的值。,PutVex(/对 u 赋值value。,存储结构的比较,2、插入和删除顶点,都要对存放顶点数组元素的操作但是对邻接矩阵，还要修改邻接矩阵,InsertVex(/在图G中增添新顶点v。,DeleteVex(/删除G中顶点v及其相关的弧。,存储结构的比较,3、插入和删除弧,InsertArc(,DeleteArc(,存储结构的比较,邻接矩阵：修改边（以及）邻接表：无向图，修改两个顶点的链表；有向图，修改一个（或两个）顶点的链表十字链表：涉及两个链表多重邻接

3、表：涉及两个链表,存储结构的比较,4、邻接点,FirstAdjVex(G,v);/返回 v 的“第一个邻接点”。若该顶点/在 G 中没有邻接点，则返回“空”。,NextAdjVex(G,v,w);/返回 v 的（相对于 w 的）“下一个邻接/点”。若 w 是 v 的最后一个邻接点，则/返回“空”。,存储结构的比较,邻接矩阵：第v行邻接表：第v个链表十字链表：第v个链表多重邻接表：第v个链表,存储结构的比较,邻接矩阵：第v行邻接表：第v个链表十字链表：第v个链表多重邻接表：第v个链表,4、邻接边,邻接点函数的实现,FirstAdjVex(G,v);/返回第1个邻接点的位置，没有邻接点，返回-1。

4、,NextAdjVex(G,v,w);/返回w后面的邻接点的位置。,邻接点函数的实现,int firstAdjVex(ALGragh G,int v)p=G.verticesv.firstarc;/v的第1个邻接点 if(!p)return-1;/无邻接点 return p-adjvex;,邻接点函数的实现,int nextAdjVex(ALGragh G,int v,int w)p=G.verticesv.firstarc;/v的第1个邻接点 while(p,用C语言描述存储结构,1、图的二个参数：,顶点个数,边数（弧数）,Vertex(Vertices)，vexnum,Edge(arc)，

5、arcnum，edgenum,2、图的第三个参数：,图的类型,GraphKind=DG,UDG,DN,UDN,图的遍历,定义：从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。,用途：是解决图的连通性、拓扑排序和求关键路径等算法的基础。,深度优先搜索,广度优先搜索,分类：,深度优先搜索,W1、W2和W3 均为 V 的邻接点，SG1、SG2 和 SG3 分别为含顶点W1、W2和W3 的子图。,深度优先搜索,访问顶点V;for(W1、W2、W3)若邻接点Wi未被访问，则从它出发进行深度优先搜索历。,深度优先搜索-连通图,深度遍历序列：,V1 V2 V4 V8 V5

6、,V6 V3 V7,V1,V2,V4,V5,V3,V7,V6,V8,深度优先搜索,深度优先搜索,深度优先搜索,1、从深度优先搜索遍历连通图的过程类似于树的先根遍历2、对图G深度优先搜索得到的顶点序列不是唯一的？3、搜索过程中经过的边和所有的顶点构成了图的一棵生成树。4、如何判别V的邻接点是否被访问？为每个顶点设立一个“访问标志 visitedw”;,深度优先搜索-连通图,void DFS(Graph G,int v)/从顶点v出发，深度优先搜索遍历连通图 G visitedv=TRUE;for(w=FirstAdjVex(G,v);w=0;w=NextAdjVex(G,v,w)if(!visi

7、tedw)DFS(G,w);/对v的尚未访问的邻接顶点w递归调用DFS/DFS,深度优先搜索-连通图,void DFS(Graph G,int v)/从顶点v出发，深度优先搜索遍历连通图 G visitedv=TRUE;for(w=FirstAdjVex(G,v);w=0;w=NextAdjVex(G,v,w)if(!visitedw)DFS(G,w);/对v的尚未访问的邻接顶点w递归调用DFS/DFS,深度优先搜索-连通图,V1,V2,V3,V4,V5,V1,V2,V8,V5,V6,V4,V2,V8,V8,V3,V1,V6,V7,V3,V8,按照完成DFS的先后，顶点的次序是:V5,V7,V

8、3,V6,V8,V4,V2,V1,DFS(G,V1),V7,void DFS(Graph G,int v)/非递归算法 InitStack(S);visited=FALSE;/所有的顶点尚未被访问过 Push(S,v);while(!Empty(S)Pop(S,u);if(!visitedu)visit(u),visitedu=TRUE;for(w=FirstAdjVex(G,u);w=0;w=NextAdjVex(G,u,w)if(!visitedw)Push(G,w)/将没访问的邻接点压栈 DestroyStack(S);/DFS,深度优先搜索-连通图,深度优先搜索非连通图,首先将图中每个

9、顶点的访问标志设为 FALSE,之后搜索图中每个顶点，如果未被访问，则以该顶点为起始点，进行深度优先搜索遍历，否则继续检查下一顶点。,深度优先搜索非连通图,a,c,h,d,k,f,e,b,g,访问次序:,8,1,2,3,4,5,6,7,0,a,c,h,d,k,f,e,b,g,T,T,T,T,T,T,T,T,T,访问标志:,a,b,c,h,d,e,k,f,g,深度优先搜索非连通图,void DFSTraverse(Graph G,int v)for(v=0;vG.vexnum;+v)visitedv=FALSE;/访问标志数组初始化 for(v=0;vG.vexnum;+v)if(!visite

10、dv)DFS(G,v);/对尚未访问的顶点调用DFS,深度优先搜索,1.从图中某个顶点V0 出发，访问此顶点,2.然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有与V0有路径的顶点都被访问到。,3.如果图中还有顶点未被访问，则令选一个未曾被访问的顶点作为起始点，重复上述过程，直至图中所有顶点都被访问到。,广度优先搜索,对连通图，从起始点V到其余各顶点必定存在路径。其中，,V-w1,V-w2,V-w8 的路径长度为1;,V-w7,V-w3,V-w5的路径长度为2;,V-w6,V-w4的路径长度为3。,w1,w8,w3,w7,w6,w2,w5,w4,广度优先搜索,1.从图中

11、的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问过的邻接点,2.然后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V0有路径相通的顶点都被访问到。,3.若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点,4.重复上述过程，直至图中所有顶点都被访问到为止,广度优先搜索,V1,V8,广度遍历序列：,V4,V6,V8,V2,V5,V1,V3,V7,V2 V3,V4 V5 V6 V7,广度优先搜索,V1,V2,V4,V5,V3,V7,V6,V8,V1,V8,广度遍历序列：,V2 V3,V4 V5,V6 V7,广度优先搜索,V1,V2,V4,V5,V3,V

12、7,V6,V8,V1,V8,广度遍历序列：,V2 V3,V4,V6 V7,V5,广度优先搜索,void BFSTraverse(Graph G,Status(*Visit)(int v)for(v=0;vG.vexnum;+v)visitedv=FALSE;/初始化访问标志 InitQueue(Q);/置空的辅助队列Q for(v=0;vG.vexnum;+v)if(!visitedv)/v 尚未访问/BFSTraverse,广度优先搜索,visitedv=TRUE;Visit(v);/访问uEnQueue(Q,v);/v入队列while(!QueueEmpty(Q)DeQueue(Q,u);

13、/队头元素出队并置为u for(w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w)if(!visitedw)visitedw=TRUE;Visit(w);EnQueue(Q,w);/访问的顶点w入队列/if/while,课堂练习,1：无向图G=(V,E),其中：V=a,b,c,d,e,f,E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)，对该图进行深度优先遍历，得到的顶点序列正确的（）。Aa,b,e,c,d,f Ba,c,f,e,b,d Ca,e,b,c,f,d Da,e,d,f,c,b,a,b,e,d,c,f,2：已知一无向

14、图G=（V，E），其中V=a,b,c,d,e E=(a,b),(a,d),(a,c),(d,c),(b,e)现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是_。,课堂练习,a,d,b,e,c,小结和作业,图的遍历定义、用途,图的深度优先搜索,图的广度优先搜索,作业：7.4、7.22,图的遍历方法,深度优先搜索-连通图,栈的变化,V1,V3,V2,V3,V5,V4,V3,V5,V8,V3,V5,V6,V5,V3,V5,V6,V3,V5,V3,V3,V5,V7,V3,V5,V3,深度优先搜索非连通图,V1,V2,V4,V5,V3,V7,V6,V8,深度遍历：,V1 V2 V4 V8,V5,V3 V6 V7,2：遍历图的过程实质上是_，breath-first search遍历图的时间复杂度_；depth-first search遍历图的时间复杂度_，两者不同之处在于_，反映在数据结构上的差别是_。,课堂练习,