第4章__贪心算法

1、贪心算法贪心算法1提纲提纲n贪心算法的概念贪心算法的概念n活动安排问题活动安排问题n最优装载问题最优装载问题n哈夫曼编码哈夫曼编码n单源最短路径单源最短路径n最小生成树最小生成树n多机调度问题多机调度问题2提纲提纲n贪心算法的概念贪心算法的概念n活动安排问题活动安排问题n最优装载问题最优装载问题n哈夫曼编码哈夫曼编码n单源最短路径单源最短路径n最小生成树最小生成树n多机调度问题多机调度问题3贪心算法贪心算法的概念的概念n贪心算法的设计思想贪心算法的设计思想q找硬币的例子：假设有四种硬币，它们的面值找硬币的例子：假设有四种硬币，它们的面值分别为：分别为：2角角5分，分，1角，角，5分，分，1分分

2、。现在要找给。现在要找给顾客顾客6角角3分分。怎样找使得给顾客的。怎样找使得给顾客的硬币最少硬币最少。q首先选出一个不超过首先选出一个不超过6角角3分的最大硬币，然后分的最大硬币，然后，从，从6角角3分中减去，再在剩余的值中选出一个分中减去，再在剩余的值中选出一个不超过该值的最大硬币，如此反复，直到找够不超过该值的最大硬币，如此反复，直到找够为止。这个找硬币的算法就是为止。这个找硬币的算法就是贪心选择算法贪心选择算法。4贪心算法贪心算法的概念的概念q如果上述问题改为：要找给顾客如果上述问题改为：要找给顾客1角角5分分，硬币，硬币的面值分别为：的面值分别为：1角角1分，分，5分和分和1分分。q这

3、时用贪心算法，给顾客找的情况是：一个这时用贪心算法，给顾客找的情况是：一个1角角1分和四个分和四个1分。而找分。而找三个三个5分为最优找法分为最优找法。故贪。故贪心算法心算法不是对所有问题都能得到整体最优解不是对所有问题都能得到整体最优解。n贪心算法的概念贪心算法的概念q贪心算法总是作出贪心算法总是作出在当前看来最好的选择在当前看来最好的选择。也。也就是说贪心算法就是说贪心算法并不从整体最优考虑并不从整体最优考虑，它所作，它所作出的选择只是在某种意义上的出的选择只是在某种意义上的局部最优局部最优选择。选择。5贪心算法贪心算法的概念的概念n贪心算法的概念贪心算法的概念q希望贪心算法得到的最终结果

4、也是希望贪心算法得到的最终结果也是整体最优整体最优。q虽然贪心算法虽然贪心算法不能对所有问题不能对所有问题都得到整体最优都得到整体最优解，但对解，但对许多问题许多问题它能产生它能产生整体最优解整体最优解。如。如单单源最短路经源最短路经问题，问题，最小生成树最小生成树问题等。问题等。q在一些情况下，即使贪心算法不能得到整体最在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是优解，其最终结果却是最优解的很好近似最优解的很好近似。6提纲提纲n贪心算法的概念贪心算法的概念n活动安排问题活动安排问题n最优装载问题最优装载问题n哈夫曼编码哈夫曼编码n单源最短路径单源最短路径n最小生成树最小生成树

5、n多机调度问题多机调度问题7活动安排问题活动安排问题n问题描述问题描述q活动安排问题就是要在所给的活动集合中选出活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合最大的相容活动子集合，是可以用，是可以用贪心算法贪心算法有有效求解的很好例子。效求解的很好例子。q该问题要求高效地安排该问题要求高效地安排一系列争用某一公共资一系列争用某一公共资源的活动源的活动。q贪心算法提供了一个贪心算法提供了一个简单、漂亮的方法简单、漂亮的方法使得使得尽尽可能多的活动可能多的活动能兼容地使用公共资源。能兼容地使用公共资源。8活动安排问题活动安排问题n问题描述问题描述q设有设有n个活动的集合个活动的集合E

6、=1,2,n，其中每个活，其中每个活动都要求使用动都要求使用同一资源同一资源，如演讲会场等，而在，如演讲会场等，而在同一时间内只有一个活动能使用这一资源同一时间内只有一个活动能使用这一资源。q每个活动每个活动i都有一个要求使用该资源的起始时间都有一个要求使用该资源的起始时间si和一个结束时间和一个结束时间fi，且，且si fi 。如果选择了活动。如果选择了活动i，则它在半开时间区间，则它在半开时间区间si, fi)内占用资源。若区内占用资源。若区间间si, fi)与区间与区间sj, fj)不相交不相交，则称活动，则称活动i与活动与活动j是是相容相容的。也就是说，当的。也就是说，当sifj或或s

7、jfi时，活动时，活动i与与活动活动j相容。相容。9活动安排问题的贪心算法活动安排问题的贪心算法templatevoid GreedySelector(int n, Type s, Type f, bool A) A1=true; int j=1; for (int i=2;i=fj) Ai=true; j=i; else Ai=false; 10各活动的起始时间和结各活动的起始时间和结束时间存储于数组束时间存储于数组s s和和f f中且按中且按结束时间的非减结束时间的非减序排列序排列 活动安排问题活动安排问题n输入的活动以其输入的活动以其完成时间的非减序排列完成时间的非减序排列q算法算法gr

8、eedySelector每次总是选择具有最早完成每次总是选择具有最早完成时间的相容活动加入集合时间的相容活动加入集合A中。中。q按这种方法选择相容活动为未安排活动留下尽按这种方法选择相容活动为未安排活动留下尽可能多的时间。可能多的时间。q该算法的贪心选择的意义是该算法的贪心选择的意义是使剩余的可安排时使剩余的可安排时间段极大化，以便安排尽可能多的相容活动间段极大化，以便安排尽可能多的相容活动。11活动安排问题活动安排问题n算法算法greedySelector的的效率极高效率极高。q当输入的活动已按结束时间的非减序排列，算当输入的活动已按结束时间的非减序排列，算法只需法只需O(n)的时间安排的时

9、间安排n个活动个活动，使最多的活动，使最多的活动能相容地使用公共资源。能相容地使用公共资源。q如果所给出的活动未按非减序排列，可以用如果所给出的活动未按非减序排列，可以用O(nlogn)的时间重排的时间重排。 12活动安排问题举例活动安排问题举例n设待安排的设待安排的11个活动的开始时间和结束时个活动的开始时间和结束时间间按结束时间的非减序排列按结束时间的非减序排列如下：如下：13i1234567891011Si130535688212fi4567891011121314活动安排问题计算过程活动安排问题计算过程n算法算法greedySelector的的计算过程如左图所示计算过程如左图所示q图中

10、图中每行每行相应于算法相应于算法的的一次迭代一次迭代。q阴影长条阴影长条表示的活动表示的活动是已选入集合是已选入集合A的活动的活动，而，而空白长条空白长条表示的表示的活动是当前正在检查活动是当前正在检查相容性的活动。相容性的活动。14活动安排问题计算过程活动安排问题计算过程n若被检查的活动若被检查的活动i的开始时间的开始时间Si小于最近选择小于最近选择的活动的活动j的结束时间的结束时间fj，则，则不选择不选择活动活动i，否则，否则选择活动选择活动i加入集合加入集合A中。中。 n贪心算法贪心算法并不总能求得并不总能求得问题的整体问题的整体最优解最优解n对于对于活动安排问题活动安排问题，贪心算法，

11、贪心算法greedySelector却却总能求得的整体最优解总能求得的整体最优解，即它最终所确定，即它最终所确定的相容活动集合的相容活动集合A的规模最大。这个结论可的规模最大。这个结论可以用以用数学归纳法证明数学归纳法证明。15贪心算法的基本要素贪心算法的基本要素n贪心选择性质贪心选择性质q贪心选择性质贪心选择性质是指所求问题的是指所求问题的整体最优解整体最优解可以通可以通过过一系列局部最优的选择一系列局部最优的选择，即，即贪心选择贪心选择来达到。来达到。这是贪心算法可行的这是贪心算法可行的第一个基本要素第一个基本要素，也是贪心，也是贪心算法算法与动态规划与动态规划算法的算法的主要区别主要区别

12、。q动态规划动态规划算法通常以算法通常以自底向上自底向上的方式解的方式解各子问题各子问题，而，而贪心算法贪心算法则通常以则通常以自顶向下自顶向下的方式进行，以的方式进行，以迭代的方式作出相继的贪心选择，每作一次迭代的方式作出相继的贪心选择，每作一次贪心贪心选择选择就就将所求问题简化将所求问题简化为规模更小的子问题。为规模更小的子问题。 q 16贪心算法的基本要素贪心算法的基本要素n贪心选择性质贪心选择性质q对于一个对于一个具体问题具体问题，要确定它是否具有，要确定它是否具有贪心选择贪心选择性质性质，必须证明每一步所作的贪心选择，必须证明每一步所作的贪心选择最终导致最终导致问题的问题的整体最优解

13、整体最优解。n最优子结构性质最优子结构性质n当一个问题的最优解当一个问题的最优解包含其子问题的最优解包含其子问题的最优解时，时，称此问题具有最优子结构性质。称此问题具有最优子结构性质。n问题的最优子结构性质是该问题问题的最优子结构性质是该问题可用动态规划可用动态规划算算法或法或贪心算法贪心算法求解的求解的关键关键特征。特征。 17贪心算法的基本要素贪心算法的基本要素n贪心算法与动态规划算法的差异贪心算法与动态规划算法的差异q贪心算法和动态规划算法贪心算法和动态规划算法都要求都要求问题具有问题具有最优子最优子结构结构性质，这是性质，这是2类算法的一个类算法的一个共同点共同点。q对于具有最优子结构

14、的问题应该对于具有最优子结构的问题应该选用选用贪心算法还贪心算法还是动态规划算法是动态规划算法求解求解?q是否能用是否能用动态规划动态规划算法求解的问题也能用算法求解的问题也能用贪心算贪心算法法求解求解?q下面研究下面研究2个经典的个经典的组合优化问题组合优化问题，并以此说明，并以此说明贪心算法与动态规划算法的贪心算法与动态规划算法的主要差别主要差别。18贪心算法的基本要素贪心算法的基本要素n0-1背包问题背包问题q给定给定n种物品和一个背包。物品种物品和一个背包。物品i的重量是的重量是Wi，其，其价值为价值为Vi，背包的容量为，背包的容量为C。应如何选择装入背。应如何选择装入背包的物品，使得

15、装入背包中物品的包的物品，使得装入背包中物品的总价值最大总价值最大?q在选择装入背包的物品时，对每种物品在选择装入背包的物品时，对每种物品i只有只有2种种选择选择，即，即装入装入背包或背包或不装入不装入背包。背包。q不能不能将物品将物品i装入背包多次装入背包多次，也不能，也不能只装入部分只装入部分的的物品物品i。 19贪心算法的基本要素贪心算法的基本要素n背包问题背包问题q与与0-1背包问题背包问题类似类似，所不同的是在选择物品，所不同的是在选择物品i装装入背包时，入背包时，可以选择物品可以选择物品i的一部分的一部分，而不一定要，而不一定要全部装入背包，全部装入背包，1in。q这这2类问题类问

16、题都具有最优子结构都具有最优子结构性质，极为相似，性质，极为相似，但但背包问题背包问题可以用可以用贪心算法贪心算法求解，而求解，而0-1背包问题背包问题却却不能用不能用贪心算法求解。贪心算法求解。20贪心算法的基本要素贪心算法的基本要素n用贪心算法解背包问题的基本步骤用贪心算法解背包问题的基本步骤q首先计算每种物品首先计算每种物品单位重量的价值单位重量的价值Vi/Wi；q然后，依然后，依贪心选择策略贪心选择策略，将尽可能多的，将尽可能多的单位重量单位重量价值最高价值最高的物品装入背包。的物品装入背包。q若将这种物品全部装入背包后，背包内的物品若将这种物品全部装入背包后，背包内的物品总总重量未超

17、过重量未超过C，则选择单位重量价值，则选择单位重量价值次高次高的物品的物品并尽可能多地装入背包。依此策略一直地进行下并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。去，直到背包装满为止。21贪心算法的基本要素贪心算法的基本要素void Knapsack(int n,float M,float v,float w,float x) Sort(n,v,w); int i; for (i=1;i=n;i+) xi=0; float c=M; for (i=1;ic) break; xi=1; c-=wi; if (i=n) xi=c/wi;22算法算法knapsack的的主主要计算时

18、间要计算时间在于将在于将各种物品依其单位各种物品依其单位重量的价值从大到重量的价值从大到小小排序排序。因此，算。因此，算法的计算时间上界法的计算时间上界为为O(nlogn)。为了证明为了证明算法的正算法的正确性确性，还必须证明，还必须证明背包问题具有背包问题具有贪心贪心选择性质选择性质。贪心算法的基本要素贪心算法的基本要素n对于对于0-1背包问题，贪心选择之所以不能得到背包问题，贪心选择之所以不能得到最优解是因为在这种情况下最优解是因为在这种情况下q它它无法保证无法保证最终能将背包装满，部分最终能将背包装满，部分闲置的背包闲置的背包空间空间使每公斤背包空间的使每公斤背包空间的价值降低价值降低了

19、。了。q在考虑在考虑0-1背包问题背包问题时，应比较时，应比较选择选择该物品和该物品和不选不选择择该物品所导致的该物品所导致的最终方案最终方案，然后再作出最好选，然后再作出最好选择。由此就导出许多择。由此就导出许多互相重叠的子问题互相重叠的子问题。这正是。这正是该问题可用该问题可用动态规划动态规划算法求解的另一重要特征。算法求解的另一重要特征。q动态规划算法动态规划算法的确可以有效地解的确可以有效地解0-1背包问题背包问题。 23提纲提纲n贪心算法的概念贪心算法的概念n活动安排问题活动安排问题n最优装载问题最优装载问题n哈夫曼编码哈夫曼编码n单源最短路径单源最短路径n最小生成树最小生成树n多机

20、调度问题多机调度问题24最优装载问题最优装载问题n问题描述问题描述q有一批集装箱要装上一艘有一批集装箱要装上一艘载重量为载重量为c的轮船。其中的轮船。其中集装箱集装箱i的重量为的重量为Wi。最优装载问题要求确定在装。最优装载问题要求确定在装载载体积不受限制体积不受限制的情况下，将的情况下，将尽可能多的集装箱尽可能多的集装箱装上轮船。装上轮船。n算法描述算法描述q最优装载问题可用最优装载问题可用贪心算法贪心算法求解。采用求解。采用重量最轻重量最轻者先装者先装的贪心选择策略，可产生最优装载问题的的贪心选择策略，可产生最优装载问题的最优解。最优解。25最优装载问题算法描述最优装载问题算法描述temp

21、latevoid Loading(int x, Type w, Type c, int n) int *t = new int n+1; Sort(w, t, n); for (int i = 1; i = n; i+) xi = 0; for (int i = 1; i = n & wti = c; i+) xti = 1; c -= wti; 26最优装载问题最优装载问题n贪心选择性质贪心选择性质q可以证明最优装载问题具有可以证明最优装载问题具有贪心选择性质贪心选择性质。 n最优子结构性质最优子结构性质q最优装载问题具有最优装载问题具有最优子结构性质最优子结构性质。n由最优装载问题

22、的贪心选择性质和最优子结由最优装载问题的贪心选择性质和最优子结构性质，容易证明构性质，容易证明算法算法loading的正确性的正确性。q主要计算量在于将集装箱依其重量主要计算量在于将集装箱依其重量从小到大排序从小到大排序，故算法所需的计算时间为，故算法所需的计算时间为 O(nlogn)。 27提纲提纲n贪心算法的概念贪心算法的概念n活动安排问题活动安排问题n最优装载问题最优装载问题n哈夫曼编码哈夫曼编码n单源最短路径单源最短路径n最小生成树最小生成树n多机调度问题多机调度问题28哈夫曼编码哈夫曼编码n哈夫曼编码哈夫曼编码q广泛地用于广泛地用于数据文件压缩数据文件压缩的十分有效的编码方法的十分有

23、效的编码方法。其压缩率通常在。其压缩率通常在20%90%之间。之间。q哈夫曼编码算法用字符在文件中出现的哈夫曼编码算法用字符在文件中出现的频率表频率表来来建立建立一个用一个用0，1串串表示各字符的最优表示方式。表示各字符的最优表示方式。q给出现给出现频率高频率高的字符较短的编码，出现的字符较短的编码，出现频率较低频率较低的字符以较长的编码，可以大大的字符以较长的编码，可以大大缩短总码长缩短总码长。29哈夫曼编码哈夫曼编码n前缀码前缀码q对每一个字符规定一个对每一个字符规定一个0, 1串作为其代码，并要串作为其代码，并要求求任一字符的代码都不是其它字符代码的前缀任一字符的代码都不是其它字符代码的

24、前缀。这种编码称为前缀码。这种编码称为前缀码。q编码的前缀性质可以使译码方法非常简单。编码的前缀性质可以使译码方法非常简单。 q表示最优前缀码的二叉树总是一棵完全二叉树，表示最优前缀码的二叉树总是一棵完全二叉树，即树中任一结点即树中任一结点都有都有2个儿子结点个儿子结点。q平均码长定义为：平均码长定义为：q30)()()(cdcfTBTCc哈夫曼编码哈夫曼编码q使平均码长达到最小的前缀码编码方案称为给定使平均码长达到最小的前缀码编码方案称为给定编码字符集编码字符集C的的最优前缀码最优前缀码。n构造哈夫曼编码构造哈夫曼编码q哈夫曼提出构造最优前缀码的哈夫曼提出构造最优前缀码的贪心算法贪心算法，由

25、此产，由此产生的编码方案称为生的编码方案称为哈夫曼编码哈夫曼编码。q哈夫曼算法以哈夫曼算法以自底向上自底向上的方式构造表示最优前缀的方式构造表示最优前缀码的二叉树码的二叉树T。q算法以算法以|C|个叶结点开始，执行个叶结点开始，执行|C|1次的次的“合并合并”运算后产生最终所要求的树运算后产生最终所要求的树T。 31哈夫曼编码哈夫曼编码n在书上给出的算法在书上给出的算法huffmanTree中中n编码字符集中每一字符编码字符集中每一字符c的频率是的频率是f(c)。以。以f为键值为键值的优先队列的优先队列Q用在贪心选择时有效地确定算法当用在贪心选择时有效地确定算法当前要合并的前要合并的2棵棵具有

26、具有最小频率的树最小频率的树。n一旦一旦2棵具有最小频率的树合并后，产生一棵新棵具有最小频率的树合并后，产生一棵新的树，其频率为合并的的树，其频率为合并的2棵树的频率之和，并将棵树的频率之和，并将新树新树插入插入优先队列优先队列Q。n经过经过n1次的合并后，优先队列中只剩下一棵树次的合并后，优先队列中只剩下一棵树，即所要求的树，即所要求的树T。32哈夫曼编码哈夫曼编码33abcdef频率频率(千次千次)4513121695定长码定长码000001010011100101变长码变长码010110011111011100定长码：定长码：3*(45+13+12+16+9+5) = 300 千位千位变

27、长码：变长码：1*45+3*13+3*12+3*16+4*9+4*5 224 千位千位哈夫曼编码哈夫曼编码3445a13b12c16d9e5f哈夫曼编码哈夫曼编码3545a13b12c16d9e5f哈夫曼编码哈夫曼编码36140145a13b12c16d9e5f哈夫曼编码哈夫曼编码3745a16d14019e5f13b12c哈夫曼编码哈夫曼编码3845a16d14019e5f13b12c2501哈夫曼编码哈夫曼编码3945a16d14019e5f13b12c2501哈夫曼编码哈夫曼编码4045a16d14019e5f13b12c25013001哈夫曼编码哈夫曼编码4145a13b12c2501

28、16d14019e5f3010哈夫曼编码哈夫曼编码4245a13b12c250116d14019e5f30015501哈夫曼编码哈夫曼编码4345a13b12c250116d14019e5f30015501哈夫曼编码哈夫曼编码4445a13b12c250116d14019e5f3001550110010100010111001101111哈夫曼编码哈夫曼编码45字母字母a ab bc cd de ef f变长码变长码0 01011011001001111111101110111001100例例: 010011101011000111101100111 0 100 111 0 101 100 0

29、 111 101 100 111 a c d a b c a d b c d哈夫曼编码哈夫曼编码4645a13b12c250116d14019e5f3001550110010100010111001101111例例: 0 100 111 0 101 100 0 111 101 100 111 a c d a b c a d b c d提纲提纲n贪心算法的概念贪心算法的概念n活动安排问题活动安排问题n最优装载问题最优装载问题n哈夫曼编码哈夫曼编码n单源最短路径单源最短路径n最小生成树最小生成树n多机调度问题多机调度问题47单源最短路径单源最短路径n给定带权有向图给定带权有向图G =(V, E)q

30、每条边的每条边的权权是是非负实数非负实数。q给定给定V中的一个中的一个顶点顶点，称为，称为源源。q现在要计算从现在要计算从源源到所有到所有其它各顶点其它各顶点的最短路长的最短路长度。这里路的长度是指路上度。这里路的长度是指路上各边权之和各边权之和。这个。这个问题通常称为问题通常称为单源最短路径问题单源最短路径问题。n算法基本思想算法基本思想qDijkstra算法是解单源最短路径问题的算法是解单源最短路径问题的贪心算贪心算法法。48单源最短路径单源最短路径q设置设置顶点集合顶点集合S并不断地作并不断地作贪心选择贪心选择来来扩充扩充这这个集合。一个顶点个集合。一个顶点属于集合属于集合S当且仅当从源

31、到当且仅当从源到该顶点的该顶点的最短路径长度已知最短路径长度已知。q初始时，初始时，S中仅含有中仅含有源源。设。设u是是G的某一个顶点，的某一个顶点，把从源到把从源到u且中间只经过且中间只经过S中顶点的路称为从源中顶点的路称为从源到到u的的特殊路径特殊路径，并用数组，并用数组dist记录当前每个顶记录当前每个顶点所对应的点所对应的最短特殊路径长度最短特殊路径长度。Dijkstra算法算法每次从每次从V-S中取出具有中取出具有最短特殊路长度的顶点最短特殊路长度的顶点u，将将u添加到添加到S中，同时对数组中，同时对数组dist作必要的修改。作必要的修改。一旦一旦S包含了所有包含了所有V中顶点，中顶

32、点，dist就记录了从源就记录了从源到所有其它顶点之间的最短路径长度。到所有其它顶点之间的最短路径长度。49单源最短路径单源最短路径n例如，对右图中例如，对右图中的有向图，应用的有向图，应用Dijkstra算法计算法计算从算从源顶点源顶点1到到其它顶点间最短其它顶点间最短路径的过程列在路径的过程列在下页的表中下页的表中。50单源最短路径单源最短路径nDijkstra算法的迭代过程：算法的迭代过程：51迭代迭代Sudist2dist3dist4dist5初始初始1-10maxint3010011,22603010021,2,44509031,2,4,336041,2,4,3,55单源最短路径单源

33、最短路径n贪心选择性质贪心选择性质n最优子结构性质最优子结构性质n计算复杂性计算复杂性q对于具有对于具有n个顶点和个顶点和e条边的条边的带权有向图带权有向图，如果，如果用用带权邻接矩阵带权邻接矩阵表示这个图，那么表示这个图，那么Dijkstra算算法的主循环体需要法的主循环体需要 时间。这个循环需要执行时间。这个循环需要执行n-1次，所以完成循环需要次，所以完成循环需要 时间。算法的其时间。算法的其余部分所需要时间不超过余部分所需要时间不超过 。52)(2nO)(nO)(2nO提纲提纲n贪心算法的概念贪心算法的概念n活动安排问题活动安排问题n最优装载问题最优装载问题n哈夫曼编码哈夫曼编码n单源

34、最短路径单源最短路径n最小生成树最小生成树n多机调度问题多机调度问题53最小生成树最小生成树n设设G =(V,E)是是无向连通带权图无向连通带权图。qE中每条边中每条边(v,w)的的权权为为cvw。q如果如果G的子图的子图G是一棵包含是一棵包含G的所有顶点的树，的所有顶点的树，则称则称G为为G的的生成树生成树。生成树上各边权的总和。生成树上各边权的总和称为该生成树的称为该生成树的耗费耗费。在。在G的所有生成树中，的所有生成树中，耗费最小的生成树称为耗费最小的生成树称为G的的最小生成树最小生成树。q网络的最小生成树在实际中有广泛应用。网络的最小生成树在实际中有广泛应用。n例如，在设计通信网络时，

35、用图的顶点表示城市，例如，在设计通信网络时，用图的顶点表示城市，用边用边(v,w)的权的权cvw表示建立城市表示建立城市v和城市和城市w之间的之间的通信线路所需的费用，则最小生成树就给出了通信线路所需的费用，则最小生成树就给出了建立建立通信网络的最经济的方案通信网络的最经济的方案。 54最小生成树最小生成树n最小生成树性质最小生成树性质q用贪心算法设计策略可以设计出构造最小生成用贪心算法设计策略可以设计出构造最小生成树的有效算法。本节介绍的构造最小生成树的树的有效算法。本节介绍的构造最小生成树的Prim算法算法和和Kruskal算法算法都可以看作是应用贪都可以看作是应用贪心算法设计策略的例子。

36、尽管这心算法设计策略的例子。尽管这2个算法做贪心个算法做贪心选择的方式不同，它们都利用了下面的选择的方式不同，它们都利用了下面的最小生最小生成树性质成树性质：q设设G=(V,E)是连通带权图，是连通带权图，U是是V的真子集。如的真子集。如果果(u,v) E，且，且u U，v V-U，且在所有这样的，且在所有这样的边中，边中，(u,v)的权的权cuv最小最小，那么一定存在，那么一定存在G的的一棵最小生成树，它以一棵最小生成树，它以(u,v)为其中一条边。这为其中一条边。这个性质有时也称为个性质有时也称为MST性质性质。 55最小生成树最小生成树nPrim算法算法 q设设G=(V,E)是是连通带权

37、图连通带权图，V=1,2,n。q构造构造G的最小生成树的的最小生成树的Prim算法的算法的基本思想基本思想是：是：q首先置首先置S=1，然后，只要，然后，只要S是是V的真子集的真子集，就，就作如下的作如下的贪心选择贪心选择：选取满足条件：选取满足条件i S，j V-S，且且cij最小的边，将最小的边，将顶点顶点j添加到添加到S中中。这个过。这个过程一直进行到程一直进行到S=V时为止时为止。q在这个过程中在这个过程中选取到的所有边选取到的所有边恰好恰好构成构成G的一的一棵棵最小生成树最小生成树。 56最小生成树最小生成树n利用最小生成树性质和利用最小生成树性质和数学归纳法数学归纳法容易证明容易证

38、明，上述算法中的上述算法中的边集合边集合T始终始终包含包含G的某棵最小的某棵最小生成树中的边生成树中的边。因此，。因此，在算法结束时，在算法结束时，T中的中的所有边所有边构成构成G的一棵的一棵最最小生成树小生成树。 n如，对于右图中的带权如，对于右图中的带权图，图，按按Prim算法选取算法选取边的过程边的过程如下页图所示。如下页图所示。57最小生成树最小生成树58最小生成树最小生成树n在上述在上述Prim算法中，还应当考虑如何有效算法中，还应当考虑如何有效地找出满足条件地找出满足条件i S,j V-S，且，且权权cij最小最小的边的边(i,j)。实现这个目的的较简单的办法是。实现这个目的的较简

39、单的办法是设置设置2个数组个数组closest和和lowcost。n在在Prim算法执行过程中，先找出算法执行过程中，先找出V-S中使中使lowcost值最小的顶点值最小的顶点j，然后根据数组，然后根据数组closest选取边选取边(j,closestj)，最后将，最后将j添加到添加到S中，并对中，并对closest和和lowcost作必要的修改。作必要的修改。n用这个办法实现的用这个办法实现的Prim算法所需的计算时算法所需的计算时间为间为 59)(2nO最小生成树最小生成树nKruskal算法构造最小生成树的基本思想是算法构造最小生成树的基本思想是q首先将首先将G的的n个顶点看成个顶点看成

40、n个孤立的连通分支个孤立的连通分支。将所有的边将所有的边按权从小到大排序按权从小到大排序。q然后从第一条边开始，依然后从第一条边开始，依边权递增边权递增顺序查看每顺序查看每一条边，并按下述方法连接一条边，并按下述方法连接2个不同的连通分支：个不同的连通分支：n当查看到第当查看到第k条边条边(v,w)时，如果端点时，如果端点v和和w分别分别是当前是当前2个不同的连通分支个不同的连通分支T1和和T2中的顶点时中的顶点时，就用边，就用边(v,w)将将T1和和T2连接成一个连通分支，然后继续查看第连接成一个连通分支，然后继续查看第k+1条边；条边；n如果端点如果端点v和和w在当前的在当前的同一个连通分支中同一个连通分支中，就直接，就直接再查看第再查看第k+1条边。条边。n这个过程一直进行到这个过程一直进行到只剩下一个连通分支只剩下一个连通分支时为止。时为止。 60最小生成树最小生成树n例如，对前面的连通带权图，按例如，对前面的连通带权图，按Kruskal算法顺序算法顺序得到最小生成树上的边如下图所示。得到最小生成树上的边如下图