数据结构与算法第7章图课件

要点回顾n图的基本概念及存储方式图的基本概念及存储方式n图的遍历图的遍历7.5 最小生成树v基本概念基本概念vPrim算法算法vKruskal算法算法7.5 最小生成树v问题提出问题提出 13149181921123389顶点城市，边 两城市之间的公路，权相应的代价，希望找到使n个城市连通的总造价最低的方案构造最小生成树。ABCDEF12139891418332119v问题分析问题分析 7.5 最小生成树最小生成树pn个城市间，最多可修建n(n-1)/2条公路。pn个村镇间建立公路网，只需n-1条公路。问题转化为：如何在可能的公路中选择n-1条，能把所有 村镇（顶点）均连起来，且总耗费（各边权 值之和）最小。一、基本概念1.1.图的生成树图的生成树图的生成树图的生成树 若G 是连通图G的子图，并有：V(G)=V(G),E(G )E(G)，还满足：G 是连通图，且所有顶点不存在回路；G 是图是图G G的一棵生成树。的一棵生成树。oo2.2.图的最小生成树图的最小生成树图的最小生成树图的最小生成树o 图G的生成树是一棵包含G的所有顶点的树，树上所o有权值总和表示代价，那么在G的所有的生成树中，o代价最小的生成树称为图G的最小生成树最小生成树(minimum-ocost spanning tree，简称MST)。例：下图例：下图(b),(c),(d)为为(a)所示连通图的不同生成树。所示连通图的不同生成树。(a)BCFDAEBCFDAE(b)BCFDAE(c)BCFDAE(d)一、基本概念(a)连通图连通图(b)边权值总和边权值总和 37(d)边权值总和边权值总和 26(c)边权值总和边权值总和 23BFDE6CA4510122BCFDAE438626BCFDAE45810123D62BCFAE5310一、基本概念3.3.构造最小生成树的准则构造最小生成树的准则构造最小生成树的准则构造最小生成树的准则n必须使用且仅使用该网络中的n-1条边来连接网络中的n个顶点；n不能使用产生回路的边；n各边上的权值总和达到最小。一、基本概念vMST性质性质 设G=（V，E）是一个连通网,U是顶点集V的一个非空子集。若（u，v）是一条具有最小权值的边，其中uU，vV-U，则必存在一棵包含边(u，v)的最小生成树。o用反证法证明如下：n由于T是生成树，T中必存在不同于边（u，v）的另一条边（u，v ），使得u U，v V-U，且u和u 之间，v和v 之间均有路径相连通。n假设网G的任何一棵最小生成树都不包含边（u，v），显然当把边（u，v）加入到G的一棵最小生成树T中时，由生成树的定义，将产生一个含有边（u，v）的回路。n将边（u ，v ）删除，这样就消除了上述回路，并得到了另一棵生成树T。由于W(u，v)W(u，v)，所以生成树T 的耗费不大于树T的耗费。于是T 是一棵包含边(u，v)的最小生成树，这与假设矛盾。v普里姆普里姆（Prim）算法算法 v克鲁斯卡尔（克鲁斯卡尔（Kruskal）算法）算法 一、基本概念二、Prim算法v设G=(V,E)是连通网，TE是G上最小生成树中边的集合，则Prim算法通过以下步骤得到最小生成树：初始状态：U=u0，TE=。其中u0是顶点集合V中的某一个顶点；在所有uU，vV-U的边(u,v)E中找一条权值最小的边(u0，v0)，将这条边加进集合TE中，同时将此边的另一顶点v0并入U；如果U=V，则算法结束；否则重复步骤2；算法结束时，TE中包含了G中的n-1条边。经过上述步骤选取到的所有边恰好就构成了图G的一棵最小生成树。v算法思想算法思想 例165432651356642516543265135664251364256516465352 Prim算法构造最小生成树的过程算法构造最小生成树的过程14253二、二、Prim算法算法ABCDEF12139891418332119A 练习练习BCDFE89121318边权值总和：边权值总和：8+9+12+13+18=60二、二、Prim算法算法三、Kruskal算法v设图G=(V,E)其生成树T的顶点集合为V，边集合为TE。初始状态：只有n个顶点而无边的非连通图T=(V,)，每 个顶点自成一个连通分量；在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边，选取下一条代价最小的边；依此类推，直至T中所有顶点都在同一连通分量上为止。v算法思想算法思想 例165432651356642516543212345三、Kruskal算法ABCDEF12139891418332119A 练习练习BCDFE89121318边权值总和：边权值总和：8+9+12+13+18=60三三、Kruskal算法算法 iClosedgei12345UV-UkadjvexlowcostV16V11V15V1V1V1V2,V3,V4,V5,V62adjvexlowcostV350V15V36V34V1,V3V2,V4,V5,V65adjvexlowcostV350V62V360V1,V3,V6V2,V4,V53adjvexlowcostV3500V360V1,V3,V6,V4V2,V51adjvexlowcost000V230V1,V3,V6,V4,V2V54adjvexlowcost00000V1,V3,V6,V4,V2,V5 Prim算法各参量的变化算法各参量的变化 四、四、Prim算法的计算机实现算法的计算机实现 设置辅助数组closedge,记录从U到V-U具有最小权值的边。对每个顶点viV-U,在辅助数组中存在一个相应的分量closedgei-1，它包括两个域：closedgei-1.lowcost=Mincost(u,vi)|u U：各顶点的边中，权值最小的边的权值；closedgei-1.vex：表示上述权值最小的边所依附的U集中的顶点。0 0 0 0 0 0 0 0 0 0 0 0 0 60 6 1 1 5 max 5 max maxmax iVexilowcosti 0 1 2 3 4 5 ivexilowcosti 0 1 2 3 4 5U=v0U=v0,v2V-U=v1,V2,V3,V4,V5 V-U=v1,V3,V4,V5 V V2 2V V0 0V V3 3V V5 5V V4 4V V1 13652165546U UV V2 2V V0 0V V3 3V V5 5V V4 4V V1 13652165546U U 0 2 0 0 2 2 0 2 0 0 2 2 0 5 0 5 60 5 0 5 6 4 4四、四、Prim算法的计算机实现算法的计算机实现v算法分析算法分析 vPrim算法的时间复杂为O（n2），与网中的边数无关，因此适用于求边稠密的网的最小生成树。四、四、Prim算法的计算机实现算法的计算机实现（0）用顶点数组和边数组存放顶点和边信息；）用顶点数组和边数组存放顶点和边信息；（1）初始时，令每个顶点的）初始时，令每个顶点的jihe互不相同；每个边的互不相同；每个边的flag为为0；（2）选出权值最小且）选出权值最小且flag为为0的边的边；（3）若该边依附的两个顶点的）若该边依附的两个顶点的jihe 值不同，即非连通，则令该边的值不同，即非连通，则令该边的flag=1,选中该边；再令该边依附的两顶点的选中该边；再令该边依附的两顶点的jihe 以及两集合中所有顶点以及两集合中所有顶点的的jihe 相同相同；若该边依附的两个顶点的若该边依附的两个顶点的jihe 值相同，即连通，则令该值相同，即连通，则令该 边的边的flag=2,即舍去该边即舍去该边；（4）重复上述步骤，直到选出）重复上述步骤，直到选出n-1条边为止条边为止。顶点结点：typedef struct int data;/顶点信息 int jihe;VEX;边结点：typedef struct int vexh,vext;/边依附的两顶点 int weight;/边的权值 int flag;/标志域EDGE;五、五、Kruskal算法的计算机实现算法的计算机实现v算法实现算法实现 例1654326513566425datajihe124536124536124536vexhweight112213233544vextflag6153550000000134256789334556666426000011111421112222216543212345v算法描述算法描述 五、五、Kruskal算法的计算机实现算法的计算机实现vKruskal算法的时间复杂度为O(eloge)。这个算法的时间复杂度主要取决于边数，因此Kruskal算法适合于构造稀疏图的最小生成树。五、五、Kruskal算法的计算机实现算法的计算机实现7.6 最短路径v7.6.1 单源最短路径单源最短路径v7.6.2 每对顶点之间的最短路径每对顶点之间的最短路径oo在非网图中在非网图中，最短路径是指两顶点之间经历的，最短路径是指两顶点之间经历的边数边数最最少的路径。少的路径。BAEDCAEAE：1 1ADEADE：2 2 ADCEADCE：3 3ABCEABCE：3 37.6 最短路径oo在网图中在网图中，最短路径是指两顶点之间经历的，最短路径是指两顶点之间经历的边上权值之边上权值之和和最短的路径。最短的路径。B BA AE ED DC C101050503030101010010020206060AEAE：100100ADEADE：90 90 ADCEADCE：60 60 ABCEABCE：70707.6 最短路径v问题提出问题提出 n用带权的有向图表示一个交通运输网，图中：p顶点表示城市；p边表示城市间的交通联系；p权表示此线路的长度或沿此线路运输所花的时间 或费用等。问题：从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径最短路径最短路径。7.6 最短路径v单源最短路径单源最短路径迪杰斯特拉（迪杰斯特拉（Dijkstra）算法算法v每对顶点之间的最短路径每对顶点之间的最短路径弗洛伊德（弗洛伊德（Floyd）算法算法7.6.1 单源最短路径v给定一个带权图G 和源点V，求从V到G中其余各顶点的最短路径，这个问题通常称为单源最短路径单源最短路径(single-source shortest paths)问题。516432085623013717329权值最短路径13813192120p迪杰斯特拉（Dijkstra）提出了一个按路径长度递增的 次序产生最短路径的算法Dijkstra算法。7.6.1 单源最短路径vDijkstra算法基本思想：把V分成两组：pS：已求出最短路径的顶点的集合。pT=V-S：尚未确定最短路径的顶点集合。将T中顶点按最短路径递增的次序加入到S中，保证：p从源点V0到S中各顶点的最短路径长度都不大于从V0到T中任何顶点的最短路径长度。p每个顶点对应一个距离值：uS中顶点：从V0到此顶点的最短路径长度。uT中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度。ABAEDC105030101002060S=AS=AAB:(A,B)10AB:(A,B)10ACAC:(A,C):(A,C)AD:AD:(A,D)30(A,D)30AE:AE:(A,E)100(A,E)1007.6.1 单源最短路径ABAEDC105030101002060S=A,BS=A,BAB:(A,B)10AB:(A,B)10ACAC:(A,B,C)60:(A,B,C)60AD:AD:(A,D)30(A,D)30AE:AE:(A,E)100(A,E)100B7.6.1 单源最短路径ABAEDC105030101002060S=A,B,DS=A,B,DAB:(A,B)10AB:(A,B)10ACAC:(A,D,C)50:(A,D,C)50AD:AD:(A,D)30(A,D)30AE:AE:(A,D,E)90(A,D,E)90BD7.6.1 单源最短路径ABAEDC105030101002060S=A,B,D,CS=A,B,D,CAB:(A,B)10AB:(A,B)10ACAC:(A,D,C)50:(A,D,C)50AD:AD:(A,D)30(A,D)30AE:AE:(A,D,C,E)60(A,D,C,E)60BDC7.6.1 单源最短路径138 30 32V0,V213-1330 32V0,V1,V2-13302220V0,V1,V2,V3-192220V0,V1,V2,V3,V4终点终点 从从V0到各终点的最短路径及其长度到各终点的最短路径及其长度V1V2V3V4V5V6S516432085623013717329终点终点 从从V0到各终点的最短路径及其长度到各终点的最短路径及其长度V1V2V3V4V5V6S-21-V0,V1,V2,V3,V4,V5,V6516432085623013717329-2120V0,V1,V2,V3,V4,V6-7.6.1 单源最短路径v对于n个顶点e条边的图，图中的任何一条边都可能在最短路径中出现，因此最短路径算法对每条边至少都要检查一次。v如果采用最小堆来选择权值最小的边，那么每次改变最短特殊路径长度时需要对堆进行一次重排，此时的时间复杂度为O(n+e)loge)，适合于稀疏图。n方法一：每次以一个顶点为源点，重复执行Dijkstra算法n次 T(n)=O(n)。n方法二：弗洛伊德(Floyd)算法。pFloyd算法用相邻矩阵adj来表示带权有向图，该算法的基本思想是：逐个顶点试探法。求最短路径步骤：u初始时设置一个n阶方阵，令其对角线元素为0，若存在弧，则对应元素为权值；否则为。u逐步试着在原直接路径中增加中间顶点，若加入中间点后路径变短，则修改之；否则，维持原值。u所有顶点试探完毕，算法结束。7.6.2 每对顶点之间的最短路径每对顶点之间的最短路径例例ACB2643110 4 116 0 23 0初始：初始：路径：路径：AB ACBA BCCA0 4 66 0 23 7 0加入加入V2：路径：路径：AB ABCBA BCCA CAB0 4 116 0 23 7 0加入加入V1：路径：路径：AB ACBA BCCA CAB0 4 65 0 23 7 0加入加入V3：路径：路径：AB ABCBCA BCCA CAB7.6.2 每对顶点之间的最短路径每对顶点之间的最短路径v算法实现图用邻接矩阵存储。length存放最短路径长度。pathij是从Vi到Vj的最短路径上Vj前一顶点序号。7.6.2 每对顶点之间的最短路径每对顶点之间的最短路径算法描述例例132264311初始：初始：0 4 116 0 23 0length=0 1 12 0 23 0 0path=加入加入V1：0 4 116 0 23 7 0length=0 1 12 0 23 1 0path=加入加入V2：0 4 66 0 23 7 0length=0 1 22 0 23 1 0path=加入加入V3：0 4 65 0 23 7 0length=0 1 23 0 23 1 0path=p算法分析：T(n)=O(n)7.6.2 每对顶点之间的最短路径每对顶点之间的最短路径7.6.2 每对顶点之间的最短路径The EndThe End