第七章图(2)图的遍历

《第七章图(2)图的遍历》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第7章图（2）图的遍历主讲：刘春学习目标①掌握图的基本概念，包括图、有向图、无向图、完全图、子图连通图、度、入度、初度、简单回路和环等基本概念的定义。②重点掌握图的各种存储结构、包括邻接矩阵和邻接表等③重点掌握图的基本元素、包括创建图、输出图、深度优先遍历、广度优先遍历算法等④掌握图的其他运算、包括最小生成树、最短路径、拓扑排序和关键路径等算法⑤灵活运用图这种数据结构解决一些综合应用问题。7.3图的遍历图的遍历的定义从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。1问题：图中可能存在回路，且图的任一顶点都可能与其它顶点相通

2、，在访问完某个顶点之后23可能会沿着某些边又回到了曾经访问过的顶点。为了避免重复访问，可设置一个标志辅助数组456visited[]，它的初始状态为0，在图的遍历过程7中，一旦某一个顶点i被访问，就立即让visited[i]为1，防止它被多次访问。8根据搜索方法的不同，图的遍历有两种：深度优先搜索(DFS)和广度优先搜素(WFS)。7.3图的遍历深度优先搜索(Depp_thFirstSearch)主要思想：从图中某个顶点V出发，访问此顶点，然后选择一个0与V邻接且未被访问的顶点W为初始顶点,再从W出发进行深度优0先搜索,直至图中所有和V有路径相通的顶点都被访

3、问到；0若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为起始点，重复上述过程，直至图中所有顶点都被访问到为止。深度优先搜索是个递归的过程7.3图的遍历连通图DFS的具体搜索过程：在访问图中任意选某一起始顶点v后，由v出发，访问它的任一邻接顶点w；再从w出发，访问与w邻接但还没有访问过的顶点111w；然后再从w出发，进行类似的访问，…如此进行下去，直至22到达所有的邻接顶点都被访问过的顶点u为止。接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，

4、就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。7.3图的遍历深度优先搜索(Depp_thFirstSearch)深度优先搜索过程深度优先生成树7.3图的遍历分析：假设W、W和W均为V的邻接点，SG、SG和SG123123分别为含顶点W、W和W的子图。123V访问顶点V：for(W、W、W)123若该邻接点W未被访问，iww1w23则从它出发进行深度优先搜索遍历。SGSGSG312结论：深度优先搜索遍历连通图的过程类似于树的先根遍历7.3图的遍历Eg7-4对无向图连通图G1，写出从顶点1出发的深度优先搜索遍历序列？1深度优先搜索序列2

5、31,2,4,8,5,6,3,7561,2,5,8,4,7,3,6471,3,6,8,7,4,2,58无向图G1结论：从某一个顶点出发的遍历结果是不唯一的。7.3图的遍历voidDFSTraverse(GraphG,Status(*Visit)(intv)){//对连通图G作深度优先遍历。VisitFunc=Visit;for(vfor(v0;=0;v

6、TraversevoidDFS((p,GraphG,intv)){{//从顶点v出发，深度优先搜索遍历连通图Gvisited[v]=TRUE;VisitFunc(v);for(w=FirstAdjVex(G,v);w!=0;w=NextAdjVex(G,v,w))if(!visited[w])DFS(G,w);//对v的尚未访问的邻接顶点w//递归调用DFS}//DFS7.3图的遍历非连通图的深度优先遍历①在每个连通分量或每个强连通分量中都选一个顶点，进行深度优先搜索遍历，最后将每个连通分量或每个强连通分量的遍历结果合起来，则得到整个非连通图的遍历结果。②遍

7、历算法实现与连通图的只有一点不同，即对所有顶点进行循环，反复调用连通图的深度优先搜索遍历算法即可。7.3图的遍历Eg7-5对无向图非连通图G2，从顶点a开始，进行深度优先遍历。0a1bab2cg3d4ecdef5f6g7hhi8i012345678访问标志:TFTFTFTFFTFTTFTFFT访问次序:achdifebg7.3图的遍历voidDFSTraverse(GraphG,Status(*Visit)(intv)){//对非连通图G作深度优先遍历。VisitFunc=Visit;for(vfor(v0;=0;v

8、v);++v)visited[v]=FALSE;//