数据结构图图的遍历幻灯片.ppt

《数据结构图图的遍历幻灯片.ppt》由会员分享，可在线阅读，更多相关《数据结构图图的遍历幻灯片.ppt（21页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、数据结构图图的遍历第1页，共21页，编辑于2022年，星期六 7.3 图的遍历l在图中有回路，从图中某一顶点出发访问图中其它顶点时，可能又会回到出发点，而图中可能还剩余有顶点没有访问到。l我们可以设置一个全局型标志数组visited来标志某个顶点是否被访问过，未访问的值为0，访问过的值为1。l图的遍历有两种方法：深度优先搜索遍历（DFS）和广度优先搜索遍历（BFS）。第2页，共21页，编辑于2022年，星期六1 深度优先搜索思想深度优先搜索思想(1)首先访问顶点i，并将其访问标记置为访问过，即visitedi=1；(2)然后搜索与顶点i有边相连的下一个顶点j，若j未被访问过，则访问它，并将j的

2、访问标记置为访问过，visitedj=1，然后从j开始重复此过程，若j已访问，再看与i有边相连的其它顶点；(3)若与i有边相连的顶点都被访问过，则退回到前一个访问顶点并重复刚才过程，直到图中所有顶点都被访问完为止。7.3.1深度优先搜索遍历第3页，共21页，编辑于2022年，星期六例如，对下图所示无向图G7，从顶点1出发的深度优先搜索遍历序列可有多种，下面仅给出三种，其它可作类似分析。1,2,4,8,5,6,3,71,2,5,8,4,7,3,61,3,6,8,7,4,2,5可以看出，从某一个顶点出发的遍历结果是不唯一的。但是,若我们给定图的存贮结构,则从某一顶点出发的遍历结果应是唯一的。第4页

3、，共21页，编辑于2022年，星期六void dfs(Graph G,vtx*v)void dfs(Graph G,vtx*v)/*/*从从v v出发深度优先遍历图出发深度优先遍历图g*/g*/visit(v);visit(v);visitedv=1;visitedv=1;w=FIRSTADJ(G,v);/w w=FIRSTADJ(G,v);/w为为v v的邻接点的邻接点 while(w!=0)while(w!=0)/当邻接点存在时当邻接点存在时 if(!visitedw)if(!visitedw)dfs(G,w);dfs(G,w);w=NEXTADJ(G,v,w);/w=NEXTADJ(G,

4、v,w);/找下一邻接点找下一邻接点 深度优先遍历算法描述第5页，共21页，编辑于2022年，星期六邻接矩阵的深度优先搜索演示邻接矩阵的深度优先搜索演示1.用邻接矩阵实现图的深度优先搜索第6页，共21页，编辑于2022年，星期六邻接矩阵存储时的算法描述为下面形式：voiddfs(inti)/从顶点i出发遍历intj;visit(i);/输出访问顶点visitedi=1;/全局数组访问标记置1表示已经访问for(j=1;jadjvex)dfs1(p-adjvex);p=p-next;而而当当以以邻邻接接表表作作图图的的存存储储结结构构时时，找找邻邻接接点点所所需需时时间间为为O(e)O(e)，其

5、其中中e e为为无无向向图图中中边边 的的数数或或有有向向图图中中弧弧的的数数。由由此此，当当以以邻邻接接表表作作存存储储结结构构时时，深深度度优优先先搜搜索索遍遍历历图的时间复图的时间复 杂度为杂度为O(nO(ne)e)。邻接表深度优先搜索演示邻接表深度优先搜索演示第10页，共21页，编辑于2022年，星期六用刚才算法，可以描述从顶点7出发的深度优先搜索遍历示意图，其中实线表示下一层递归，虚线表示递归返回，箭头旁边数字表示调用的步骤。遍历序列为7，3，1，2，4，8，5，6。第11页，共21页，编辑于2022年，星期六在每个连通分量或每个强连通分量中都选一个顶点，进行深度优先搜索遍历，最后将

6、每个连通分量或每个强连通分量的遍历结果合起来，则得到整个非连通图的遍历结果。遍历算法实现与连通图的只有一点不同，即对所有顶点进行循环，反复调用连通图的深度优先搜索遍历算法即可。具体实现如下：for(inti=1;i=n;i+)if(!visitedi)dfs(i);for(inti=1;i=n;i+)if(!visitedi)dfs1(i);或者3.非连通图的深度优先搜索 第12页，共21页，编辑于2022年，星期六1 广度优先搜索的思想广度优先搜索的思想广度优先搜索遍历类似于树的按层次遍历。设图G的初态是所有顶点均未访问，在G中任选一顶点i作为初始点，则广度优先搜索的基本思想是：(1)首先访

7、问顶点i，并将其访问标志置为已被访问，即visitedi=1；(2)接着依次访问与顶点i有边相连的所有顶点W1，W2，Wt；(3)然后再按顺序访问与W1，W2，Wt有边相连又未曾访问过的顶点；依此类推，直到图中所有顶点都被访问完为止。8.3.2 广度优先搜索遍历第13页，共21页，编辑于2022年，星期六在无向图G7中，从顶点1出发的广度优先搜索遍历序列举三种为：1,2,3,4,5,6,7,81,3,2,7,6,5,4,81,2,3,5,4,7,6,8第14页，共21页，编辑于2022年，星期六和深度优先搜索类似，在遍历的过程中也需要一个访问标志数组。和深度优先搜索类似，在遍历的过程中也需要一

8、个访问标志数组。并且，为了顺次访并且，为了顺次访 问路径长度为问路径长度为2、3、的顶点，需附设队列以的顶点，需附设队列以存储已被访问的路径长度为存储已被访问的路径长度为1，2，的顶点。广的顶点。广 度优先遍历的算度优先遍历的算法如下所示。法如下所示。void bfs(Graph g,vtx*vvoid bfs(Graph g,vtx*v）visit(v);visitedv=1;visit(v);visitedv=1;INIQUEUE(Q);INIQUEUE(Q);ENQUEUE(Q,v);ENQUEUE(Q,v);while(!EMPTY(Q)while(!EMPTY(Q)DLQUEUE(Q

9、,v);/DLQUEUE(Q,v);/队头元素出队队头元素出队 w=FIRSTADJ(g,v);/w=FIRSTADJ(g,v);/求求v v的邻接点的邻接点 while(w!=0)while(w!=0)if(!visitedw)if(!visitedw)visit(w);visitedw=1;ENQUEUE(Q,w);visit(w);visitedw=1;ENQUEUE(Q,w);w=NEXTADJ(g,v,w);/w=NEXTADJ(g,v,w);/求下一邻接点求下一邻接点 /bfs /bfs 第15页，共21页，编辑于2022年，星期六根据该算法用及图7-14中的邻接矩阵，可以得到图G

10、7的广度优先搜索序列，若从顶点1出发，广度优先搜索序列为：1，2，3，4，5，6，7，8。若从顶点3出发，广度优先搜索序列为：3，1，6，7，2，8，4，5。1.用邻接矩阵实现图的广度优先搜索遍历第16页，共21页，编辑于2022年，星期六算法描述如下：voidbfs(inti)/从顶点i出发遍历intQn+1;/Q为队列intf,r,j;/f,r分别为队列头，尾指针f=r=0;/设置空队列visit(vi);/输出访问顶点visitedi=1;/全局数组标记置1表示已经访问r+;qr=i;/入队列while(fr)f+;i=qf;/出队列for(j=1;j=n;j+)if(Aij=1)&(!

11、visitedj)visit(vj);visitedj=1;r+;qr=j;第17页，共21页，编辑于2022年，星期六可以得到图G7的广度优先搜索序列，若从顶点1出发，广度优先搜索序列为：1，2，3，4，5，6，7，8，若从顶点7出发，广度优先搜索序列为：7，3，8，1，6，4，5，2。2.用邻接表实现图的广序优先搜索遍历第18页，共21页，编辑于2022年，星期六算法描述如下：voidBFS1(inti)intqn+1;/定义队列intf,r;E_NODE*p;/P为搜索指针f=r=0;visit(headi);visitedi=1;r+;qr=i;/进队while(fadjvex)vis

12、it(headp-adjvex.vertex;visitedp-adjvex=1;r+;qr=p-adjvex;p=p-next;邻接表的广度优先搜索演示邻接表的广度优先搜索演示第19页，共21页，编辑于2022年，星期六可以在每个连通分量或每个强连通分量中都选一个顶点，进行广度优先搜索遍历，最后将每个连通分量或每个强连通分量的遍历结果合起来，则得到整个非连通图或非强连通图的广度优先搜索遍历序列。具体可以表示如下：3.非连通图的广度优先搜索for(inti=1;i=n;i+)for(inti=1;i=n;i+)if(!visitedi)或if(!visitedi)bfs(i);bfs1(i);

13、分析上述过程，每个顶点至多进一次队列。遍历图的过程实质分析上述过程，每个顶点至多进一次队列。遍历图的过程实质上是通过边或弧找邻接上是通过边或弧找邻接 点的过程、因此广度优先搜索遍历图的点的过程、因此广度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同，两者不同之时间复杂度和深度优先搜索遍历相同，两者不同之 处仅仅在于处仅仅在于对顶点访问的顺序不同。对顶点访问的顺序不同。第20页，共21页，编辑于2022年，星期六作业l已知图的邻接矩阵如右图，从顶点0出发，写出按深度优先遍历的结点序列。并画出像讲义中的示意图，其中实线表示下一层递归，虚线表示递归返回，箭头旁边数字表示调用的步骤。l写出按广度优先遍历右图的结点序列并画出每次访问一个结点的时候队列中的节点序列。第21页，共21页，编辑于2022年，星期六