数据结构第7章图.ppt
第七章 图,7.1 图的类型定义,7.2 图的存储结构,7.3 图的遍历,7.4 最小生成树,7.5 有向无环图及其应用,7.6 最短路径,7.3 图的遍历,图的遍历：从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。在图中，访问部分顶点后，可能又沿着其他边回到已被访问过的顶点。为保证每一个顶点只被访问一次，必须对顶点进行标记，一般用一个辅助数组 visit0.n-1 作为对顶点的标记，当顶点vi未被访问，visiti 值为0；当vi已被访问，则 visiti 值为1。通常，有两种遍历图的路径：深度优先搜索和广度优先搜索，对无向图和有向图都适用。,图的两种遍历方法：1.深度优先搜索图的深度优先遍历类似于树的先根遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相应地，用此方法遍历图就称之为图的深度优先遍历。2.广度优先搜索广度优先遍历类似于树的按层次遍历。采用的搜索方法的特点是尽可能先对横向进行搜索，故称其为广度优先搜索(Breadth-FirstSearch)。相应的遍历就称为广度优先遍历。,1.深度优先搜索 DFS,基本思想：选择图中某个(强)连通分量中某个顶点v出发：访问顶点 v，并将其访问标记置为访问过，即 visitedv=1；依次从 v 的未被访问的邻接点出发，继续对图进行深度优先遍历，直到(强)连通分量中和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,访问标志:,访问次序:,例如:,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(!visitedw)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,深度优先遍历序列 对图进行深度优先遍历时，按访问顶点的先后次序得到的顶点序列称为该图的深度优先遍历序列，或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出发的深度优先遍历序列。,深度优先遍历序列：,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 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=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序列不一定是惟一的;给定了源点及图的存储结构时，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，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 条带权的边中选取 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 和 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：,Uv1,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集中的相邻顶点序号 VRType 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 的最小生成树/网 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=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 中边的条数为 n-1。,算法的基本思想：,考虑问题的出发点:为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。,具体做法:先构造一个只含 n 个顶点的子图 SG，然后从权值最小的边开始，若它的添加不使SG 中产生回路，则在 SG 上加上这条边，如此重复，直至加上 n-1 条边为止。,步骤：(1)最小生成树的初始状态为只有n个顶点而无边的非连通图 T=(V,)。(2)在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边，选取下一条代价最小的边。(3)依此类推，直至T中所有顶点都在同一连通分量上为止。,例2 用克鲁斯卡尔算法构造图G最的小生成树。,(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的最小生成树（详细步骤）,
