数据结构第7章 图3

第七章图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。通常，有两种遍历图的路径：深度优先搜索和广度优先搜索，对无向图和有向图都适用。图的两种遍历方法：1.深度优先搜索图的深度优先遍历类似于树的先根遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-FirstSearch)。相应地，用此方法遍历图就称之为图的深度优先遍历。2.广度优先搜索广度优先遍历类似于树的按层次遍历。采用的搜索方法的特点是尽可能先对横向进行搜索，故称其为广度优先搜索(Breadth-FirstSearch)。相应的遍历就称为广度优先遍历。1.深度优先搜索DFS基本思想：选择图中某个(强)连通分量中某个顶点v出发：⑴访问顶点v，并将其访问标记置为访问过，即visited[v]=1；⑵依次从v的未被访问的邻接点出发，继续对图进行深度优先遍历，直到(强)连通分量中和v有路径相通的顶点都被访问过；⑶如果图中还有顶点未被访问，则另选图中其余(强)连通分量中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问过为止。非连通图的每一个连通部分称为连通分量。连通分量：连通：在无向图中，如果从顶点v到顶点w有路径，则称v和w是连通的。LABMCFIDGJEHKDEIGHKLABMCFJ(强)连通分量的遍历：W1、W2和W3均为V的邻接点。SG1为从W1出发可以访问到的顶点集；SG2为从W2出发可以访问到的顶点集；SG3为从W3出发可以访问到的顶点集。VW1W2W3SG1SG2SG3访问顺序：SG1SG2SG3。交集部分只访问一次。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)){//从顶点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：深度优先遍历图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：已知图的邻接表如下，求从顶点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]=1；⑵访问vi的所有未被访问的邻接点w1,w2,…,wk；⑶依次从这些邻接点出发，访问它们的所有未被访问的邻接点，直到(强)连通分量的所有顶点都被访问；⑷重复上述步骤，直到图中所有的顶点都被访问。对连通图，从起点V到其余各顶点必定存在路径。其中，Vw1,Vw2,Vw5的路径长度为1；Vw3,Vw6,Vw8的路径长度为2；Vw4,Vw7的路径长度为3VW3W5W7W8W6W4W2W1各顶点和起点之间存在“远近”关系。就是按照“由近到远”的顺序进行遍历。voidBFSTraverse(GraphG,Status(*Visit)(intv)){//广度优先非递归遍历。使用辅助队列Q和访问标志数组visited。for(v=1;vG.vexnum;++v)visited[v]=FALSE;InitQueue(Q);//置空的辅助队列Qfor(v=1;vG.vexnum;++v)if(!visited[v]){//v尚未访问visited[v]=TRUE;(*Visit)(v);//访问起点EnQueue(Q,v);//v入队列while(!QueueEmpty(Q)){DeQueue(Q,u);//队头元素出队并置为u下页for(w=FirstAdjVex(G,u);w=0;w=NextAdjVex(G,u,w))//访问邻接点if(!visited[w]){//u的尚未访问的邻接顶点w入队列Qvisited[w]=TRUE;(*Visit)(w);EnQueue(Q,w);}//if}//while}//BFSTraverse例1：广度优先遍历图G，并写出广度优先遍历序列。广度优先遍历序列：V1,V2,V3,V4,V5,V6,V7,V8V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8例2：广度优先遍历图G，并写出广度优先遍历序列。广度优先遍历序列：V1,V2,V3,V4,V5,V6,V7,V8图的广度优先遍历序列广度优先遍历图所得的顶点序列，定义为图的广度优先遍历序列，简称BFS序列。⑴一个图的BFS序列不一定是惟一的;⑵给定了源点及图的存储结构时，BFS序列就是惟一的。例3：已知图的邻接表如下，求从顶点0出发的广度优先遍历序列。广度优先遍历序列：0,1,3,2,4132120413204V0V1V2V3V401234V0V4V3V1V2广度优先遍历序列：0,1,3,2,40,1,3,4,20,3,1,2,4例4：已知图的邻接矩阵，求从顶点0出发的广度优先遍历序列。0,1,2,3,4,6,5广度优先遍历序列：例5：已知图的邻接表如下，求从顶点0出发的广度优先遍历序列。0,3,2,1广度优先遍历序列：0,3,2,1深度优先遍历序列：例6：⑴画出该网的邻接矩阵。⑵根据画出的邻接矩阵存储结构，从顶点1出发，分别进行深度优先遍历和广度优先遍历；51234610104101541522030∞2015∞∞∞2∞∞∞1030∞4∞∞∞10∞∞∞∞∞∞∞∞∞15∞∞∞∞∞410∞123456123456深度优先：1，2，5，4，6，3广度优先：1，2，3，5，6，4非连通图的每一个连通部分称为连通分量。连通分量：连通分量：无向图中的极大连通子图。极大连通子图：该子图是无向图D的连通子图，将D的任何不在该子图中的顶点加入，子图不再是连通的；生成树：包含无向图G中所有n个顶点和n-1条边的极小连通子图称为G的生成树。极小连通子图：该子图是G的连通子图，在该子图中删除任何一条边，子图不再连通。若T是G的生成树当且仅当T满足如下条件：1.T是G的连通子图2.T包含G的所有顶点3.T中无回路7.4最小生成树7.4最小生成树假设要在n个城市之间建立通讯联络网，如何在最节省经费的前提下建立这个通讯网？问题：分析：首先，该网必须是连通网；其次，网中的线路必须最少；最后，考虑所有线路的长度之和最小。最小生成树满足上述要求。上述问题等价于：构造网的一棵最小生成树，即：在e条带权的边中选取n-1条边（不构成回路），使“权值之和”最小。求最小生成树的两个算法：普里姆算法：适用于求边稠密的网的最小生成树。克鲁斯卡尔算法：适用于求边稀疏的网的最小生成树。假设有连通网N={V,{E}}，求N的最小生成树T={TV,{TE}}。算法的基本思想:一、普里姆(Prim)算法1.令TV={v},TE={}；//从一个顶点v开始2.TE+=min[(v,u)]，TV+=u，其中,v∈TV,u∈V-TV;3.重复步骤2，直到TV=V。取图中任意一个顶点v作为生成树的根，之后往生成树上添加新的顶点w。在添加的顶点w和已经在生成树上的顶点v之间必定存在一条边，并且该边的权值在所有连通顶点v和w之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有n个顶点为止。普里姆算法的基本思想:V2V0V3V5V4V13652165546步骤：(1)初始时，U={v0}，边集合TE=；(2)在所有v0U、wV-U的边中选择一条权值最小的边，设这条边为（v0,w）；(3)将边(v0,w)加入TE，同时将w加入U中，而把w从V-U中删掉；(4)重复(2)、(3)，直到U=V为止。V3V1V4V6V5V23652165546(1)普里姆算法举例例1使用普里姆算法为图G构造最小生成树。设最小生成树为：T＝(U，{TE})图G＝(V,{E})构造步骤如下：步骤1：初始状态U＝{v1}TE=V-U={v2,v3,v4,v5,v6}V1(1)普里姆算法举例V3V1V4V6V5V23652165546图G＝(V,{E})步骤2：V3V11U＝{v1,v3}V-U={v2,v4,v5,v6}(1)普里姆算法举例V3V1V4V6V5V23652165546图G＝(V,{E})步骤3：V3V1V614U＝{v1,v3,v6}V-U={v2,v4,v5}(1)普里姆算法举例V3V1V4V6V5V23652165546图G＝(V,{E})步骤4：U＝{v1,v3,v6,v4}V-U={v2,v5}V3V1V4V6142(1)普里姆算法举例V3V1V4V6V5V23652165546图G＝(V,{E})步骤5：U＝{v1,v3,v6,v4,v2}V-U={v5}V3V1V4V6V21425(1)普里姆算法举例V3V1V4V6V5V23652165546图G＝(V,{E})步骤6：U＝{v1,v2,v3,v4,v5,v6}U＝V，结束V3V1V4V6V5V214253(1)普里姆算法举例V3V1V4V6V5V23652165546图G＝(V,{E})在算法实现中设置一个辅助数组closedege，对当前V-U集合中的每个顶点，记录和顶点集U中顶点相连接的代价最小的边；struct{VertexTypeadjvex;//U集中的相邻顶点序号VRTypelowcost;//边的权值}closedge[MAX_VERTEX_NUM];例如:所得生成树权值和=14+8+3+5+16+21=67abcdegf195141827168213127closedge0a1b2c3d4e5f6g