数据结构图的遍历PPT课件

1、复习复习- -图的存储结构图的存储结构BACDFE0 1 0 0 1 0 1 0 0 0 1 1 0 0 0 1 0 1 0 0 1 0 0 1 1 1 0 0 0 0 0 1 1 1 0 0 第1页/共50页复习复习- -图的存储结构图的存储结构BACDFE012345ABCDEF14043525011253第2页/共50页复习复习- -图的存储结构图的存储结构ABECD0 1 0 0 1 0 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 0 第3页/共50页复习复习- -图的存储结构图的存储结构ABECD01234ABCDE1430122第4页/共50页复习复习-

2、 -图的存储结构图的存储结构ABECD0101234ABCDE32034第5页/共50页复习复习- -图的存储结构图的存储结构例aecbd1234acdb5e 1 2 1 4 3 4 3 2 3 5 5 2mark ivex ilink jvex jlink第6页/共50页复习复习- -图的存储结构图的存储结构ABCABC0 1 20 12 1 0 2 2 0 第7页/共50页存储结构的比较存储结构的比较邻接矩阵可用于DG、UDG、DN、UDN邻接表可用于DG、UDG、DN、UDN十字链表用于DG和DN邻接多重链表用于UDG和UDN一、应用范围第8页/共50页存储结构的比较存储结构的比较邻接矩

3、阵: n + n2邻接表用于DG和DN：n + e或者n + 2e；用于UDG和UDN：n + 2e十字链表: n + e邻接多重链表: n + e二、存储空间第9页/共50页存储结构的比较存储结构的比较三、对操作的支持1、对顶点的访问LocateVex(G, u); /返回u的位置GetVex(G, v); / 返回 v 的值。PutVex(&G, u, value);/ 对 u 赋值value。第10页/共50页存储结构的比较存储结构的比较2、插入和删除顶点都要对存放顶点数组元素的操作但是对邻接矩阵，还要修改邻接矩阵InsertVex(&G, v); /在图G中增添新顶点v

4、。DeleteVex(&G, v); / 删除G中顶点v及其相关的弧。第11页/共50页存储结构的比较存储结构的比较3、插入和删除弧InsertArc(&G, v, w); DeleteArc(&G, v, w); 第12页/共50页存储结构的比较存储结构的比较邻接矩阵：修改边（以及）邻接表：无向图，修改两个顶点的链表；有向图，修改一个（或两个）顶点的链表十字链表：涉及两个链表多重邻接表：涉及两个链表第13页/共50页存储结构的比较存储结构的比较4、邻接点FirstAdjVex(G, v); / 返回 v 的“第一个邻接点第一个邻接点” 。若该顶点/在 G 中没有邻接点

5、，则返回“空”。NextAdjVex(G, v, w); / 返回 v 的（相对于 w 的） “下一个邻接下一个邻接/ 点点”。若 w 是 v 的最后一个邻接点，则/ 返回“空”。第14页/共50页存储结构的比较存储结构的比较邻接矩阵：第v行邻接表：第v个链表十字链表：第v个链表多重邻接表：第v个链表第15页/共50页存储结构的比较存储结构的比较邻接矩阵：第v行邻接表：第v个链表十字链表：第v个链表多重邻接表：第v个链表4、邻接边第16页/共50页邻接点函数的实现邻接点函数的实现012345ABCDEF14043525011253FirstAdjVex(G, v); /返回第1个邻接点的位置，

6、没有邻接点，返回-1。NextAdjVex(G, v, w); /返回w后面的邻接点的位置。第17页/共50页邻接点函数的实现邻接点函数的实现int firstAdjVex(ALGragh G, int v) p=G.verticesv.firstarc;/v的第1个邻接点 if(!p) return -1;/无邻接点 return p-adjvex;第18页/共50页邻接点函数的实现邻接点函数的实现int nextAdjVex(ALGragh G, int v, int w) p=G.verticesv.firstarc;/v的第1个邻接点 while(p & p-adjvex !=

7、 w) p=p-nextarc; if(p) p = p-nextarc;/w之后的下一个邻接点 if(p) return p-adjvex; else return -1;第19页/共50页用用C C语言描述存储结构语言描述存储结构1、图的二个参数：顶点个数边数（弧数）Vertex(Vertices)，vexnumEdge(arc)，arcnum，edgenum2、图的第三个参数：图的类型GraphKind=DG, UDG, DN, UDN第20页/共50页图的遍历图的遍历定义：从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。用途：是解决图的连通性、拓扑排

8、序和求关键路径等算法的基础。u深度优先搜索u广度优先搜索分类：第21页/共50页深度优先搜索深度优先搜索SG1SG2SG3W1、W2和W3 均为 V 的邻接点，SG1、SG2 和 SG3 分别为含顶点W1、W2和W3 的子图。Vw1w3w2第22页/共50页深度优先搜索深度优先搜索SG1SG2SG3Vw1w3w2访问顶点V ; ;for (W1、W2、W3 )若邻接点Wi未被访问，则从它出发进行深度优先搜索历。第23页/共50页深度优先搜索深度优先搜索- -连通图连通图 深度遍历序列：V1V2V4V5V3V7V6V8V1 V2 V4 V8 V5 V6 V3 V7V1V2V4V5V3V7V6V8

9、第24页/共50页深度优先搜索深度优先搜索V1V2V4V5V3V7V6V8V4V6V8V2V5V1V3V7第25页/共50页深度优先搜索深度优先搜索V1V2V4V3V7V6V8V1V2V4V3V7V6V8第26页/共50页深度深度优先搜索优先搜索Vw1w8w3w7w6w2w5w4w1w8w3w7w6w2w5第27页/共50页1、从深度优先搜索遍历连通图的过程类似于树的先根遍历2、对图G深度优先搜索得到的顶点序列不是唯一的？3、搜索过程中经过的边和所有的顶点构成了图的一棵生成树。4、如何判别V的邻接点是否被访问？ 为每个顶点设立一个“访问标志 visitedw”;深度优先搜索深度优先搜索- -连

10、通图连通图 第28页/共50页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深度优先搜索深度优先搜索- -连通图连通图 第29页/共50页void DFS(Graph G, int v) / 从顶点从顶点v出发，深度优先搜索遍历连通图出发，深度优先搜索遍历连通图 G vis

11、itedv = TRUE; for(w=FirstAdjVex(G, v); w=0; w=NextAdjVex(G,v,w) if (!visitedw) DFS(G, w); / 对v的尚未访问的邻接顶点w递归调用DFS / DFS深度优先搜索深度优先搜索- -连通图连通图 第30页/共50页V1V2V3V4V5V1V2V8V5V6V4V2V8V8V3V1V6V7V3V8按照完成DFS的先后，顶点的次序是: V5 , V7, V3, V6, V8, V4, V2, V1DFS(G, V1)V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8V7第31页/共50页void DFS

12、(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深度优先搜索深度优先搜索- -连通图连通图 第32页/共50页深度优先搜索深度优先搜索非连通图非连

13、通图 首先将图中每个顶点的访问标志设为 FALSE, 之后搜索图中每个顶点，如果未被访问，则以该顶点为起始点，进行深度优先搜索遍历，否则继续检查下一顶点。第33页/共50页深度优先搜索深度优先搜索非连通图非连通图achdkfe bg访问次序访问次序: :abchdekfg812345670812345670achdkfebgF F F F F F F F F0 1 2 3 4 5 6 7 8TTTTTTTTT访问标志访问标志: :abchdekfg第34页/共50页深度优先搜索深度优先搜索非连通图非连通图void DFSTraverse(Graph G, int v) for (v=0; vG

14、.vexnum; +v) visitedv = FALSE; / 访问标志数组初始化 for (v=0; vw1, V-w2, V-w8 的路的路径长度为径长度为1;V-w7, V-w3, V-w5的的路径长度为路径长度为2; ;V-w6, V-w4的路径长度为的路径长度为3。w1w8w3w7w6w2w5w4第37页/共50页广度优先搜索广度优先搜索1.1.从图中的某个顶点V V0 0出发，并在访问此顶点之后依次访问V V0 0的所有未被访问过的邻接点2.2.然后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V V0 0有路径相通的顶点都被访问到。3.3.若此时图中尚有顶点未被

15、访问, ,则另选图中一个未曾被访问的顶点作起始点4.4.重复上述过程，直至图中所有顶点都被访问到为止第38页/共50页广度优先搜索广度优先搜索V1V2V4V5V3V7V6V8V1V8广度遍历序列：V4V6V8V2V5V1V3V7 V2 V3 V4 V5 V6 V7第39页/共50页广度优先搜索广度优先搜索V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8V1V8广度遍历序列： V2 V3 V4 V5 V6 V7第40页/共50页广度优先搜索广度优先搜索V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8V1V8广度遍历序列： V2 V3 V4 V6 V7V5第41页/

16、共50页广度优先搜索广度优先搜索 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 第42页/共50页广度优先搜索广度优先搜索visitedv = TRUE; Visit(v); / 访问uEnQueue(Q, v); / v入队列while (!QueueEmpt

17、y(Q) DeQueue(Q, u); / 队头元素出队并置为u for(w=FirstAdjVex(G, u); w; w=NextAdjVex(G,u,w) if ( ! visitedw) visitedw=TRUE; Visit(w); EnQueue(Q, w); / 访问的顶点w入队列 / if / while第43页/共50页课堂练习课堂练习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,babedcf第44页/共50页2：已知一无向图G=（V，E），其中V=a,b,c,d,e E=(a,b),(a,d),(a,c),(d,c),(b,e)现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是_。课堂练习课堂练习adbec第45页/共50页小结和作业小结和作业图的遍历定义、用途图的深度优先搜索图的广度优先搜索作业：7.4、7.22 图的遍历方法第46页/共50页深度优先搜索深度优先搜索- -连通图连通图 栈的变化V1V2V4V5V3V7V6V8V1V2V4V5V3