《图的遍历和连通性》PPT课件

《《图的遍历和连通性》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、7.1基本术语7.2存储结构7.3图的遍历7.4图的连通性7.5图的应用第7章图17.3图的遍历遍历：从已给的连通图中某一顶点出发，沿着一些边，访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历，它是图的基本运算。遍历实质：找每个顶点的邻接点的过程。图的特点：图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。解决思路：可设置一个辅助数组visited[n]，用来标记每个被访问过的顶点。它的初始状态为false，在图的遍历过程中，一

2、旦某一个顶点i被访问，就立即改visited[i]为true，防止它被重复访问。怎样避免重复访问？2深度优先搜索和广度优先搜索图常用的遍历：一、深度优先搜索(DFS)Depth_FirstSearch基本思想：——类似于树的先根遍历过程。1、连通图的深度优先搜索遍历步骤：访问起始点v;依次从v的未被访问的邻接点出发深度优先遍历图直至图中所有和v有路径相通的顶点都被访问到。3v1v1v2v3v8v7v6v4v5DFS结果：例1：→→→→→→→v2v4v8v5v3v6v7起点应退回到V8，因为V2已有标记vo

3、idDFS(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}//DFS4对于无向图，这个算法可以遍历到v顶点所在的连通分量中的所有顶点，而与v顶点不在一个连通分量中的所有顶点遍历不到；对于有向图可以遍历到起始顶点v能够到达的所有顶点。若希望遍历到图中的

4、所有顶点，就需要在上述深度优先遍历算法的基础上，增加对每个顶点访问状态的检测。2、非连通图的深度优先搜索遍历步骤：访问起始点v及图中所有和v有路径相通的顶点。如果图中尚有顶点未被访问，则以该顶点为起始点，进行深度优先搜索遍历。重复上述过程，直至所有顶点都已被访问。5abchdekfgFFFFFFFFFTTTTTTTTTachdkfebgachkfedbg访问标志:访问次序:例2:0123456788123456706voidDFSTraverse(GraphG,Status(*Visit)(intv)){

5、//对图G作深度优先遍历。VisitFunc=Visit;for(v=0;v

6、个结点即可完成遍历，加上访问n个头结点的时间，因此遍历图的时间复杂度为O(n+e)。结论：稠密图适于在邻接矩阵上进行深度优先遍历；稀疏图适于在邻接表上进行深度优先遍历。8二、广度优先搜索(BFS)基本思想：——仿树的层次遍历过程。Breadth_FirstSearch在访问了起始点v之后，依次访问v的各个未曾访问过的邻接点；然后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V有路径相通的顶点都被访问到。若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图

7、中所有顶点都被访问到为止。步骤：9v1v1v2v3v8v7v6v4v5BFS结果：例1：→→→→v2v3→v4v5→v6v7→v8v3→BFS结果：→v4→v5→起点起点v2→v1→v6v9→v8→v7例2：10讨论：答:利用一个队列结构记录顶点访问顺序，将访问的每个顶点入队，然后，再依次出队，出队时访问其邻接点并将邻接点入队。（2）如何避免重复访问某个顶点？（1）在广度优先遍历中，要求先被访问的顶点其邻接点也被优先访问，应采用何种方式记录顶点访问顺序？答：创建一个一维数组visited[0..n-1]（

8、n是图中顶点的数目），用来记录每个顶点是否已经被访问过。（3）广度优先搜索有回退的情况吗？11答：广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有回退的情况。因此广度优先搜索不是一个递归的过程，其算法也不是递归的。voidBFSTraverse(GraphG,Status(*Visit)(intv)){for(v=0;v