最小生成树与最短路径问题

1、 图图 最小生成树与最短路径问题 2009/05/142基于邻接表的图操作运算基于邻接表的图操作运算3基于邻接表的图操作运算基于邻接表的图操作运算45主要内容主要内容 生成树的概念（spanning tree） Prim算法 Kruskal算法 最短路径问题 Dijkstra算法 Floyd算法6生成树（支撑树）的概念生成树（支撑树）的概念GraphMatrix graph = 6, 0, 10, M, M, 19,21,10, 0, 5, M, M, 11,M, 5, 0, M, M, M,M, M, M, 0, 18, 14,19, M, M, 18, 0, 33,21, 11, M, 1

2、4, 33, 0; 0 1 2 3 4 5子图子图 + 连通连通 + 无环无环7无向图中无环的充要条件无向图中无环的充要条件 检查每一个连通分枝 对于所有连通分枝： 顶点数 边的数目 = 1可以采用周游算法。算法复杂度：n 0 1 2 3 4 58最小生成树最小生成树 Minimum-cost Spanning Tree 连通无向带权图 网络。 网络（带权图）的生成树中生成树各边的权值加起来称为生成树的权生成树的权，把权值最小的生成树称为最小生成树。最小生成树。 (简称为MST)。 9 G=(V，E)是一个网络，U是顶点集合V的一个真子集。 如果uU，vV-U，且边(u,v)是图G中所有一个端

3、点在U里，另一端点在V-U里的边中权值最小的边， 则一定存在G的一棵最小生成树包括此边(u,v)。MST必包含连通图中任意两个顶点划分之间的最小权的边。（任意割集中的最小边）MST性质性质10MST性质证明（反证法）性质证明（反证法）uuvvUV-Uvv边(u,v)是图G中所有一个端点在U里，另一端点在V-U里的边中权值最小的边。 假设：存在G的一棵最小生成树不包括此边。11Prim算法（找算法（找MST）prim算法的基本思想是算法的基本思想是 首先从集合V中任取一顶点(例如取顶点v0)放入集合U中这时U=v0，TE=NULL 然后在所有一个顶点在集合U里，另一个顶点在集合V-U里的边中，找

4、出权值最小的边(u,v)(uU，vV-U)，将边加入TE，并将顶点v加入集合U 重复上述操作直到U=V为止。这时TE中有n-1条边，T=(U，TE)就是G的一棵最小生成树12最小生成树的构造最小生成树的构造准备工作： 设图采用邻接矩阵表示法表示，用一对顶点的下标(在顶点表中的下标)表示一条边，定义如下 在构造最小生成树的过程中定义一个类型为Edge的数组 mst Edge mstn-1; 其中n为网络中顶点的个数，算法结束时，mst中存放求出的最小生成树的n-1条边。typedef structint start_vex, stop_vex;/* 边的起点和终点 */AdjType weigh

5、t; /* 边的权 */Edge;13例子：例子：mst Edge mstn-1;已知带权图G及其邻接矩阵如图所示请构造该图的最小生成树 v0 10 v1 21 11 5 v5 19 33 14 6 v2 6 v4 18 v3 033141121330181914180666051165010211910014 n=6，只有顶点v0在最小生成树中。 mst5=0,1,10, 0,2, 0,3, 0,4,19, 0,5,21 在mst0到mst4中找出权值最小的边mst0，即(v0, v1)，将顶点v1及边(v0, v1)加入最小生成树。 v0 10 v1 21 11 5 v5 19 33 14

6、 6 v2 6 v4 18 v3 03314112133018191418066605116501021191001n -115 n=6，只有顶点v0在最小生成树中。 mst5=0,1,10, 0,2, 0,3, 0,4,19, 0,5,21 在mst0到mst4中找出权值最小的边mst0，即(v0, v1)，将顶点v1及边(v0, v1)加入最小生成树。调整： mst5=0,1,10, 1,2,5, 1,3,6, 0,4,19, 1,5,11 v0 10 v1 21 11 5 v5 19 33 14 6 v2 6 v4 18 v3 033141121330181914180666051165

7、01021191002n -2比较16mst5=0,1,10, 1,2,5, 1,3,6, 3,4,18, 1,5,11 mst5=0,1,10, 1,2,5, 1,3,6, 3,4,18, 1,5,11 03314112133018191418066605116501021191003n -3 v0 10 v1 21 11 5 v5 19 33 14 6 v2 6 v4 18 v3 17mst5=0,1,10, 1,2,5, 1,3,6, 1,5,11 , 3,4,18 v0 10 v1 21 11 5 v5 19 33 14 6 v2 6 v4 18 v3 18调整为成新边19Prim算法

8、时间复杂度算法时间复杂度 Prim算法的时间主要花费在选择最小生成树的n-1条边上。外循环执行n-1次，内循环两个，时间耗费为： 整个算法的时间复杂度为O(n2) 20221202)1(2) )1()1(ninijnijninijOOO20贪心算法一般思路贪心算法一般思路 初态（起点） 候选对象集合 贪心选择算法（按当前状态） 可行评估函数 目标函数21Kruskal算法 设G=(V，E)是网络，最小生成树的初始状态为只有n个顶点而无边的非连通图T=(V，)，T中每个顶点自成为一个连通分量。 将集合E中的边按权递增顺序排列，从小到大从小到大依次选择顶点分别在两个不同连通分量分别在两个不同连通分

9、量中的边加入图T，则原来的两个连通分量由于该边的连接而成为一个连通分量。 依次类推，直到T中所有顶点都在同一个连通分量上为止，该连通分量就是G的一棵最小生成树。22例题例题 用用Kruskal方法构造图的最小生成方法构造图的最小生成树树 集合E中的边按权递增顺序排列为(v1, v2 5), (v1, v3 6), (v2, v3 6), (v0, v1 10), (v1, v5 11), (v3, v5 14), (v3, v4 18), (v0, v4 19), (v0, v5 21), (v4, v5 33) v0 10 v1 21 11 5 v5 19 33 14 6 v2 6 v4 1

10、8 v3 23初始时，T为只有6个顶点的非连通图。边(v1, v2)的两个顶点v1，v2分别属于两个连通分量，将边(v1, v2)加入T。同理，将边(v1, v3)加入T。由于边由于边(v2, v3)的两个顶点的两个顶点v2，v3属于同一个连通分量，因属于同一个连通分量，因此，舍去这条边。此，舍去这条边。同理将边(v0, v1)、(v1, v5)加入T，边(v3, v5)舍去，边(v3, v4)加入T。这时T中含的边数为5条，成为一个连通分量，T就是G的一棵最小生成树。2425算法框架算法框架 T=(V,)while(T中所含边数 distmin.length + G.arcsmini 则将顶

11、点vi的距离值改为 distmin.length + G.arcsmini并修改路径上vi的前趋顶点： disti.prevex = min33例子：例子： 初始状态V = v0 结果distn为0, 0, 50, 0, 10, 0, MAX, -1, 45, 0, MAX, -1 34在集合V-U中找出距离值最小的顶点v2，将顶点v2加入集合U中。原：distn为0, 0, 50, 0, 10, 0, MAX, -1, 45, 0, MAX, -1 后：distn为0, 0, 50, 0, 10, 0, 25, 2, 45, 0, MAX, -1 35（接）同理在集合V-U中找出当前距离值最

12、小的顶点v3，并调整集合V-U中顶点的距离值。原：distn为0, 0, 50, 0, 10, 0, 25, 2, 45, 0, MAX, -1 后：distn为0, 0, 45, 3, 10, 0, 25, 2, 45, 0, MAX, -1 36最后：最后： 在集合V-U中找出当前距离值最小的顶点v4。并调整集合V-U中顶点的距离值。 结果distn为0, 0, 45, 3, 10, 0, 25, 2, 45, 0, MAX, -1 没有可以再加入集合U的顶点了，说明从顶点v0到顶点v5之间无路径相通。过程结束。37算法分析算法分析 算法中的初始化部分的时间复杂度为O(n)， 求最短路径部

13、分由一个大循环组成，其中外循环运行n-1次，内循环为两个，均运行n-1次，因此，算法的时间复杂度为O(n2)。 另外需要注意，在算法中改变了关系矩阵中的初始状态，如果要求算法不能破坏原始数据，就需要另外增加数据结构记录集合的值。空间代价是（） 38FloydFloyd算法算法 All pairs Shortest Paths 基本思想： 图采用邻接矩阵作为存储结构。把关系矩阵看成是没有经过任何中间结点，直接可以到达的每一对顶点间的最短路径的完整表示， 然后经过多次迭代，每次增加一个新的结点，在允许这个结点作为中间结点的条件下，计算每一对顶点间的最短路径的缩短变化， 直到把所有结点都考虑进去为止

14、，结果得到每一对顶点间的最短路径。 39数据结构数据结构typedef structAdjType *a; /*存放每对顶点间最短路径长度 */int *nextvex; /*存放vi到vj最短路径上vi的后继顶点的下标值 */ShortPath;*a: 存放每对顶点间的距离（或最短路径长度） ， 以关系矩阵作为其初始状态。*nextvex：存放vi到vj最短路径上vi的后继顶点的下标值。以 保存全部最短路径的轨迹，40例题例题 用Floyd方法求图G10各顶点间的最短路径长度。4103030350201502051504510500A0513111143111143111113210141211141210nextvex0