数据结构图的遍历.pptx
复习复习-图的存储结构图的存储结构BACDFE第1页/共50页复习复习-图的存储结构图的存储结构BACDFE012345ABCDEF14043525011253第2页/共50页复习复习-图的存储结构图的存储结构ABECD第3页/共50页复习复习-图的存储结构图的存储结构ABECD01234ABCDE1430122第4页/共50页复习复习-图的存储结构图的存储结构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页存储结构的比较存储结构的比较邻接矩阵: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。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 中没有邻接点，则返回“空”。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个邻接点的位置，没有邻接点，返回-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!=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页图的遍历图的遍历定义：从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。用途：是解决图的连通性、拓扑排序和求关键路径等算法的基础。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第24页/共50页深度优先搜索深度优先搜索V1V2V4V5V3V7V6V8V4V6V8V2V5V1V3V7第25页/共50页深度优先搜索深度优先搜索V1V2V4V3V7V6V8V1V2V4V3V7V6V8第26页/共50页深度深度优先搜索优先搜索Vw1w8w3w7w6w2w5w4w1w8w3w7w6w2w5第27页/共50页1、从深度优先搜索遍历连通图的过程类似于树的先根遍历2、对图G深度优先搜索得到的顶点序列不是唯一的？3、搜索过程中经过的边和所有的顶点构成了图的一棵生成树。4、如何判别V的邻接点是否被访问？为每个顶点设立一个“访问标志 visitedw”;深度优先搜索深度优先搜索-连通图连通图 第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 visitedv=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(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页深度优先搜索深度优先搜索非连通图非连通图 首先将图中每个顶点的访问标志设为 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.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.若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点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页/共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(!QueueEmpty(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页深度优先搜索深度优先搜索-连通图连通图 栈的变化V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8V1V3V2V3V5V4V3V5V8V3V5V6V5V3V5V6V3V5V3V3V5V7V3V5V3第47页/共50页深度优先搜索深度优先搜索非连通图非连通图V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8深度遍历：V1 V2 V4 V8V5V3 V6 V7第48页/共50页2：遍历图的过程实质上是_，breath-first search遍历图的时间复杂度_；depth-first search遍历图的时间复杂度_，两者不同之处在于_，反映在数据结构上的差别是_。课堂练习课堂练习第49页/共50页感谢您的观看！第50页/共50页
