资源描述：
《数据结构第7章图.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第七章图7.1图的类型定义7.2图的存储结构7.3图的遍历7.4最小生成树7.5有向无环图及其应用7.6最短路径7.3图的遍历图的遍历：从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。在图中，访问部分顶点后，可能又沿着其他边回到已被访问过的顶点。为保证每一个顶点只被访问一次，必须对顶点进行标记，一般用一个辅助数组visit[0..n-1]作为对顶点的标记，当顶点vi未被访问，visit[i]值为0；当vi已被访问，则visit[i]值为1。通常，有两种遍历图的路径：深度优先搜索和广度优先搜索，对无向图和有向图都适用。图的两种遍历
2、方法：1.深度优先搜索图的深度优先遍历类似于树的先根遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-FirstSearch)。相应地，用此方法遍历图就称之为图的深度优先遍历。2.广度优先搜索广度优先遍历类似于树的按层次遍历。采用的搜索方法的特点是尽可能先对横向进行搜索，故称其为广度优先搜索(Breadth-FirstSearch)。相应的遍历就称为广度优先遍历。1.深度优先搜索DFS基本思想：选择图中某个(强)连通分量中某个顶点v出发：⑴访问顶点v，并将其访问标记置为访问过，即visited[v]=1；⑵依次从v的
3、未被访问的邻接点出发，继续对图进行深度优先遍历，直到(强)连通分量中和v有路径相通的顶点都被访问过；⑶如果图中还有顶点未被访问，则另选图中其余(强)连通分量中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问过为止。非连通图的每一个连通部分称为连通分量。连通分量：连通：在无向图中，如果从顶点v到顶点w有路径，则称v和w是连通的。LABMCFIDGJEHKDEIGHKLABMCFJ(强)连通分量的遍历：W1、W2和W3均为V的邻接点。SG1为从W1出发可以访问到的顶点集；SG2为从W2出发可以访问到的顶点集；SG3为从W3出发可以访问到的顶点集。访问顺
4、序：SG1SG2SG3。交集部分只访问一次。abchdekfg812345670FFFFFFFFF012345678TTTTTTTTTachdkfebgachkfedbg访问标志:访问次序:例如:hkvoidDFSTraverse(GraphG){//深度优先遍历for(v=1;v<=G.vexnum;++v)visited[v]=FALSE;//访问标志数组初始化for(v=1;v<=G.vexnum;++v)if(!visited[v])DFS(G,v,Visit);}voidDFS(GraphG,intv,Status(*Visit)(intv)){//
5、从顶点v出发，深度优先搜索遍历连通分量visited[v]=TRUE;(*Visit)(v);//尚未访问的邻接顶点递归调用for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))if(!visited[w])DFS(G,w,Visit);}//DFS深度优先遍历的递归算法例1：深度优先遍历图G，并写出深度优先遍历序列。序列1：V1,V2,V4,V8,V5,V3,V6,V7序列2：V1,V2,V5,V8,V4,V3,V7,V6V1V2V4V5V3V7V6V8注意：由于没有规定访问邻接点的顺序，深度优先序列不是唯一的。例2：深
6、度优先遍历图G，并写出深度优先遍历序列。V1V2V4V5V3V7V6V8深度优先遍历序列：V1,V2,V4,V8,V5,V6,V3,V7V1,V2,V5,V8,V4,V6,V3,V7V1,V3,V7,V8,V6,V5,V2,V4深度优先遍历序列对图进行深度优先遍历时，按访问顶点的先后次序得到的顶点序列称为该图的深度优先遍历序列，或DFS序列。⒈一个图的DFS序列不一定惟一;⒉源点和存储结构的内容均已确定的图的DFS序列惟一。⑴邻接矩阵表示的图确定源点后，DFS序列惟一；⑵只有给出了邻接表的内容及初始出发点，才能惟一确定其DFS序列例3：已知图的邻接表如下，求从顶点
7、0出发的深度优先遍历序列。深度优先遍历序列：0,1,2,3,4132120413204V0V1V2V3V401234V0V4V3V1V2深度优先遍历序列：0,1,2,3,40,1,2,4,30,1,4,2,30,3,2,1,40,3,2,4,1例4：已知图的邻接矩阵，求从顶点0出发的深度优先遍历序列。深度优先遍历序列：0,1,3,4,2,5,6例5：已知图的邻接表如下，求从顶点0出发的深度优先遍历序列。深度优先遍历序列：0,1,2,32.广度优先搜索BFS选择(强)连通分量中的某个顶点vi出发：⑴访问顶点vi，并将其访问标志置为已被访问，即visited[vi]=
8、1；⑵访问
