数据结构第7章图.ppt

《数据结构第7章图.ppt》由会员分享，可在线阅读，更多相关《数据结构第7章图.ppt（60页珍藏版）》请在三一办公上搜索。

1、第七章 图,7.1 图的类型定义,7.2 图的存储结构,7.3 图的遍历,7.4 最小生成树,7.5 有向无环图及其应用,7.6 最短路径,7.3 图的遍历,图的遍历：从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。在图中，访问部分顶点后，可能又沿着其他边回到已被访问过的顶点。为保证每一个顶点只被访问一次，必须对顶点进行标记，一般用一个辅助数组 visit0.n-1 作为对顶点的标记，当顶点vi未被访问，visiti 值为0；当vi已被访问，则 visiti 值为1。通常，有两种遍历图的路径：深度优先搜索和广度优先搜索，对无向图和有向图都适用。,图的两种遍历

2、方法：1.深度优先搜索图的深度优先遍历类似于树的先根遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相应地，用此方法遍历图就称之为图的深度优先遍历。2.广度优先搜索广度优先遍历类似于树的按层次遍历。采用的搜索方法的特点是尽可能先对横向进行搜索，故称其为广度优先搜索(Breadth-FirstSearch)。相应的遍历就称为广度优先遍历。,1.深度优先搜索 DFS,基本思想：选择图中某个(强)连通分量中某个顶点v出发：访问顶点 v，并将其访问标记置为访问过，即 visitedv=1；依次从 v 的未被访问的邻接点出发，

3、继续对图进行深度优先遍历，直到(强)连通分量中和v有路径相通的顶点都被访问过；如果图中还有顶点未被访问，则另选图中其余(强)连通分量中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问过为止。,(强)连通分量的遍历：W1、W2 和 W3 均为 V 的邻接点。SG1 为从 W1 出发可以访问到的顶点集；,SG2 为从 W2 出发可以访问到的顶点集；SG3 为从 W3 出发可以访问到的顶点集。,访问顺序：SG1 SG2 SG3。交集部分只访问一次。,T,T,T,T,T,T,T,T,T,a,c,h,d,k,f,e,b,g,a,c,h,k,f,e,d,b,g,访问标志:,访问次序:,例如

4、:,h,k,void DFSTraverse(Graph G)/深度优先遍历 for(v=1;v=G.vexnum;+v)visitedv=FALSE;/访问标志数组初始化 for(v=1;v=G.vexnum;+v)if(!visitedv)DFS(G,v,Visit);,void DFS(Graph G,int v,Status(*Visit)(int v)/从顶点 v 出发，深度优先搜索遍历连通分量 visitedv=TRUE;(*Visit)(v);/尚未访问的邻接顶点递归调用 for(w=FirstAdjVex(G,v);w=0;w=NextAdjVex(G,v,w)if(!visi

5、tedw)DFS(G,w,Visit);/DFS,深度优先遍历的递归算法,例1：深度优先遍历图G，并写出深度优先遍历序列。序列1：V1,V2,V4,V8,V5,V3,V6,V7序列2：V1,V2,V5,V8,V4,V3,V7,V6,注意：由于没有规定访问邻接点的顺序，深度优先序列不是唯一的。,例2：深度优先遍历图G，并写出深度优先遍历序列。,深度优先遍历序列：,V1,V2,V4,V8,V5,V6,V3,V7,V1,V2,V5,V8,V4,V6,V3,V7,V1,V3,V7,V8,V6,V5,V2,V4,深度优先遍历序列 对图进行深度优先遍历时，按访问顶点的先后次序得到的顶点序列称为该图的深度优

6、先遍历序列，或DFS序列。一个图的DFS序列不一定惟一;源点和存储结构的内容均已确定的图的DFS序列惟一。邻接矩阵表示的图确定源点后，DFS序列惟一；只有给出了邻接表的内容及初始出发点，才能惟一确定其DFS序列,例3：已知图的邻接表如下，求从顶点0出发的深度优先遍历序列。,深度优先遍历序列：,0,1,2,3,4,深度优先遍历序列：,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出发的深度优先遍历序列。,深度

7、优先遍历序列：,0,1,2,3,2.广度优先搜索 BFS,选择(强)连通分量中的某个顶点vi出发：访问顶点vi，并将其访问标志置为已被访问，即visitedvi=1；访问 vi 的所有未被访问的邻接点w1,w2,wk；依次从这些邻接点出发，访问它们的所有未被访问的邻接点，直到(强)连通分量的所有顶点都被访问；重复上述步骤，直到图中所有的顶点都被访问。,对连通图，从起点V到其余各顶点必定存在路径。,其中，Vw1,Vw2,Vw5的路径长度为1；,Vw3,Vw6,Vw8 的路径长度为2；,Vw4,Vw7 的路径长度为3,各顶点和起点之间存在“远近”关系。就是按照“由近到远”的顺序进行遍历。,void

8、 BFSTraverse(Graph G,Status(*Visit)(int v)/广度优先非递归遍历。使用辅助队列Q和访问标志数组visited。for(v=1;v G.vexnum;+v)visitedv=FALSE;InitQueue(Q);/置空的辅助队列Q for(v=1;v G.vexnum;+v)if(!visitedv)/v尚未访问 visitedv=TRUE;(*Visit)(v);/访问起点 EnQueue(Q,v);/v入队列 while(!QueueEmpty(Q)DeQueue(Q,u);/队头元素出队并置为u,下页,for(w=FirstAdjVex(G,u);w

9、=0;w=NextAdjVex(G,u,w)/访问邻接点 if(!visitedw)/u的尚未访问的邻接顶点w入队列Q visitedw=TRUE;(*Visit)(w);EnQueue(Q,w);/if/while/BFSTraverse,例1：广度优先遍历图G，并写出广度优先遍历序列。广度优先遍历序列：V1,V2,V3,V4,V5,V6,V7,V8,例2：广度优先遍历图G，并写出广度优先遍历序列。广度优先遍历序列：V1,V2,V3,V4,V5,V6,V7,V8,图的广度优先遍历序列 广度优先遍历图所得的顶点序列，定义为图的广度优先遍历序列，简称BFS序列。一个图的BFS序列不一定是惟一的;

10、给定了源点及图的存储结构时，BFS序列就是惟一的。,例3：已知图的邻接表如下，求从顶点0出发的广度优先遍历序列。,广度优先遍历序列：,0,1,3,2,4,广度优先遍历序列：,0,1,3,2,40,1,3,4,20,3,1,2,4,例4：已知图的邻接矩阵，求从顶点0出发的广度优先遍历序列。,0,1,2,3,4,6,5,广度优先遍历序列：,例5：已知图的邻接表如下，求从顶点0出发的广度优先遍历序列。,例6：画出该网的邻接矩阵。根据画出的邻接矩阵存储结构，从顶点1出发，分别进行深度优先遍历和广度优先遍历；,1 2 3 4 5 6,1 2 3 4 5 6,深度优先：1，2，5，4，6，3广度优先：1，

11、2，3，5，6，4,极大连通子图：该子图是无向图D的连通子图，将D的任何不在该子图中的顶点加入，子图不再是连通的；,极小连通子图：该子图是G的连通子图，在该子图中删除任何一条边，子图不再连通。,若T是G的生成树当且仅当T满足如下条件：1.T是G的连通子图 2.T包含G的所有顶点3.T中无回路,7.4 最小生成树,7.4 最小生成树,假设要在 n 个城市之间建立通讯联络网，如何在最节省经费的前提下建立这个通讯网？,问 题：,分析：首先，该网必须是连通网；其次，网中的线路必须最少；最后，考虑所有线路的长度之和最小。,最小生成树满足上述要求。,上述问题等价于：构造网的一棵最小生成树，即：在 e 条带

12、权的边中选取 n-1 条边（不构成回路），使“权值之和”最小。求最小生成树的两个算法：普里姆算法：适用于求边稠密的网的最小生成树。克鲁斯卡尔算法：适用于求边稀疏的网的最小生成树。,假设有连通网 N=V,E，求 N 的最小生成树 T=TV,TE。,算法的基本思想:,一、普里姆(Prim)算法,令 TV=v,TE=；/从一个顶点v开始TE+=min(v,u)，TV+=u，其中,vTV,uV-TV;重复步骤 2，直到 TV=V。,取图中任意一个顶点 v 作为生成树的根，之后往生成树上添加新的顶点 w。在添加的顶点 w 和已经在生成树上的顶点v 之间必定存在一条边，并且该边的权值在所有连通顶点 v 和

13、 w 之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有 n 个顶点为止。,普里姆算法的基本思想:,步骤：(1)初始时，U=v0，边集合TE=；(2)在所有 v0U、wV-U的边中选择一条权值最小的边，设这条边为（v0,w）；(3)将边(v0,w)加入TE，同时将w 加入U中，而把w从V-U中删掉；(4)重复(2)、(3)，直到U=V为止。,(1)普里姆算法举例,例1 使用普里姆算法为图G构造最小生成树。,设最小生成树为：T(U，TE),图 G(V,E),构造步骤如下：,步骤 1：初始状态,Uv1 TE=V-U=v2,v3,v4,v5,v6,(1)普里姆算法举例,步骤 2：,Uv

14、1,v3 V-U=v2,v4,v5,v6,(1)普里姆算法举例,步骤 3：,Uv1,v3,v6 V-U=v2,v4,v5,(1)普里姆算法举例,步骤 4：,Uv1,v3,v6,v4 V-U=v2,v5,(1)普里姆算法举例,步骤 5：,Uv1,v3,v6,v4,v2 V-U=v5,(1)普里姆算法举例,步骤 6：,Uv1,v2,v3,v4,v5,v6 UV，结束,(1)普里姆算法举例,在算法实现中设置一个辅助数组 closedege，对当前 V-U 集合中的每个顶点，记录和顶点集 U 中顶点相连接的代价最小的边；,struct VertexType adjvex;/U集中的相邻顶点序号 VRT

15、ype lowcost;/边的权值 closedgeMAX_VERTEX_NUM;,例如:,所得生成树权值和=14+8+3+5+16+21=67,a,e,d,c,b,a,a,a,19,14,18,14,例如:,e,12,e,e,8,16,8,d,3,d,d,7,21,3,c,5,5,所得生成树权值和,=14+8+3+5+16+21=67,例2:,a,e,d,c,b,g,f,14,8,5,3,16,21,所得生成树权值和,=14+8+3+5+16+21=67,void MiniSpanTree_P(MGraph G,VertexType u)/用 Prim 算法从顶点 u 出发构造网 G 的最小

16、生成树/网 G 用邻接矩阵表示 k=LocateVex(G,u);max=100;for(j=0;j G.vexnum;+j)/辅助数组初始化 if(j!=k)closedgej=u,G.arcskj.adj;closedgek.lowcost=0;/初始，TV=u for(i=1;i G.vexnum;+i)for(n=1;n G.vexnum;+i)if(closedgen.lowcast max,下页,printf(“(%c,%c)”,closedgek.adjvex,G.vexsk);/输出最小生成树的一条边 closedgek.lowcost=0;/k 顶点并入 TV 集 for(j

17、=0;j G.vexnum;+j)/修改顶点的 lowcast if(G.arcskj.adj closedgej.lowcost)closedgej=G.vexsk,G.arcskj.adj;/for/MiniSpanTree_P,练习题1 使用普里姆算法为图G构造一棵最小生成树。,练习题2 使用普里姆算法为图G构造一棵最小生成树。,算法的基本思想：,二、克鲁斯卡尔(Kruskal)算法,假设有连通网 N=V,E，求 N 的最小生成树 T=TV,TE。,令 TV=V,TE=；/包含所有顶点TE+=min(v,u),(v,u)是顶点 v,u 之间的唯一路径;重复步骤 2，直到 TE 中边的条数

18、为 n-1。,算法的基本思想：,考虑问题的出发点:为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。,具体做法:先构造一个只含 n 个顶点的子图 SG，然后从权值最小的边开始，若它的添加不使SG 中产生回路，则在 SG 上加上这条边，如此重复，直至加上 n-1 条边为止。,步骤：(1)最小生成树的初始状态为只有n个顶点而无边的非连通图 T=(V,)。(2)在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边，选取下一条代价最小的边。(3)依此类推，直至T中所有顶点都在同一连通分量上为止。,例2 用克鲁斯卡尔算法构造图G最的

19、小生成树。,(2)克鲁斯卡尔算法,设最小生成树为：T(U，TE),构造步骤如下：,步骤1：初始状态,T中只有 n 个顶点，无边,(2)克鲁斯卡尔算法,图 G=(V,E),步骤2：,T中有 n 个顶点，1条边,(2)克鲁斯卡尔算法,图 G=(V,E),步骤3：,T中有 n 个顶点，2条边,2,(2)克鲁斯卡尔算法,图 G=(V,E),步骤4：,T中有 n 个顶点，3条边,(2)克鲁斯卡尔算法,图 G=(V,E),步骤5：,T中有 n 个顶点，4条边,(2)克鲁斯卡尔算法,图 G=(V,E),步骤6：,此时，所有顶点都在同一个连通分量中，构造结束。,(2)克鲁斯卡尔算法,练习题1 使用克鲁斯卡尔算法为图G构造一棵最小生成树。,50,40,50,30,45,42,最小生成树,练习题2 使用克鲁斯卡尔算法为图G构造一棵最小生成树。,练习：求图G的最小生成树（详细步骤）,