第4章贪心算法

1、1计算机与信息工程学院2第4章 贪心算法 顾名思义，贪心算法总是作出在顾名思义，贪心算法总是作出在当前看来最好的选择当前看来最好的选择。也就是说贪心。也就是说贪心算法算法并不从整体最优考虑并不从整体最优考虑，它所作出的选择只是在某种意义上的，它所作出的选择只是在某种意义上的局部最优局部最优选择。决策一旦作出，就不可更改。选择。决策一旦作出，就不可更改。 当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解对许多问题它能产生整体最优解

2、。如单源最短路经问题，最小生成树问题等。如单源最短路经问题，最小生成树问题等。 在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的最优解的很好近似很好近似。 例：找零钱问题设有4种硬币，面值分别是25分、10分、5分、1分。现找给顾客67分，而且要使总的硬币数最少。蛮干法：穷举所有可能贪心法：每次加入一个面值不超过零钱数的最大硬币：25+25+10+5+1+1举例 例：找零钱问题贪心法并不能保证任何情况下都能得到最优解。如硬币面值改为1分、5分、11分；现在须找15分。若按贪心算法：11+1+1+1+1而实际最优解为

3、：5+5+5举例54.1 活动安排问题 活动安排问题就是要活动安排问题就是要在所给的活动集合中选出最大在所给的活动集合中选出最大的相容活动子集合的相容活动子集合，是可以用贪心算法有效求解的很好例子。，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列该问题要求高效地安排一系列争用某一公共资源争用某一公共资源的活动。的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。动能兼容地使用公共资源。64.1 活动安排问题 设有设有n n个活动的集合个活动的集合E=1,2,E=1,2,n,n，其中每个，其中每个活动

4、都要求使用同一资源，如演讲会场等，而在同活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。一时间内只有一个活动能使用这一资源。活动相容的定义：活动相容的定义： 每个活动每个活动i i都有一个要求使用该资源的都有一个要求使用该资源的起始时起始时间间s si i和一个和一个结束时间结束时间f fi i, ,且且s si i ffi i 。如果选择了活。如果选择了活动动i i，则它在半开时间区间，则它在半开时间区间ssi i, f, fi i) )内占用资源。内占用资源。若区间若区间ssi i, f, fi i) )与区间与区间ssj j, f, fj j) )不相交，

5、则称不相交，则称活动活动i i与活动与活动j j是相容的是相容的。也就是说，当。也就是说，当s si iffj j或或s sj jffi i时，时，活动活动i i与活动与活动j j相容。相容。74.1 活动安排问题 public static int greedySelector(int s, int f, boolean a) int n=s.length-1; a1=true; int j=1; int count=1; for (int i=2;i=fj) ai=true; j=i; count+; else ai=false; return count; 在下面所给出的解活动安排问题的

6、贪心算法greedySelector :各活动的起始时间和各活动的起始时间和结束时间存储于数组结束时间存储于数组s s和和f f中且中且按结束时间按结束时间的非减序排列的非减序排列 84.1 活动安排问题 由于输入的活动以其完成时间的由于输入的活动以其完成时间的非减序非减序排列，所以算法排列，所以算法greedySelectorgreedySelector每次总是选择每次总是选择具有最早完成时间具有最早完成时间的相容活的相容活动加入集合动加入集合A A中。直观上，按这种方法选择相容活动为未安中。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选排活动留下尽可

7、能多的时间。也就是说，该算法的贪心选择的意义是择的意义是使剩余的可安排时间段极大化使剩余的可安排时间段极大化，以便安排尽可，以便安排尽可能多的相容活动。能多的相容活动。 算法算法greedySelectorgreedySelector的效率极高。当输入的活动已按结的效率极高。当输入的活动已按结束时间的非减序排列，算法只需束时间的非减序排列，算法只需O(n)O(n)的时间安排的时间安排n n个活动，个活动，使最多的活动能相容地使用公共资源。如果所给出的活动使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用未按非减序排列，可以用O(nlogn)O(nlogn)的时间重排。的时

8、间重排。 94.1 活动安排问题 例：例：设待安排的设待安排的1111个活动的开始时间和结束时间按结个活动的开始时间和结束时间按结束时间的非减序排列如下：束时间的非减序排列如下：i1234567891011Si 130535688212fi 45678910 11 12 13 14104.1 活动安排问题 算法算法greedySelector greedySelector 的计的计算过程算过程如左图所示。图中每如左图所示。图中每行相应于算法的一次迭代。行相应于算法的一次迭代。阴影长条表示的活动是已选阴影长条表示的活动是已选入集合入集合A A的活动，而空白长的活动，而空白长条表示的活动是当前正在

9、检条表示的活动是当前正在检查相容性的活动。查相容性的活动。114.1 活动安排问题 若被检查的活动若被检查的活动i i的开始时间的开始时间s si i小于最近选择的小于最近选择的活动活动j j的结束时间的结束时间f fj j，则不选择活动，则不选择活动i i，否则选择活，否则选择活动动i i加入集合加入集合A A中。中。 贪心算法并不总能求得问题的贪心算法并不总能求得问题的整体最优解整体最优解。但。但对于活动安排问题，贪心算法对于活动安排问题，贪心算法greedySelectorgreedySelector却总却总能求得整体最优解能求得整体最优解，即它最终所确定的相容活动集，即它最终所确定的相

10、容活动集合合A A的规模最大。这个结论可以用数学归纳法证明。的规模最大。这个结论可以用数学归纳法证明。4.1 活动安排问题 正确性证明（用数学归纳法证明）1、贪心选择性质即证明活动安排问题总存在一个最优解从贪心选择开始。4.1 活动安排问题 正确性证明（用数学归纳法证明）1、 贪心选择性质设E=1,2,n为所给的活动集合。由于E中的活动按结束时间的非递减排序，故活动1具有最早完成时间。首先证明活动安排问题有一个最优解以贪心选择开始，即该最优解中包含活动1.4.1 活动安排问题 正确性证明（用数学归纳法证明）1、 贪心选择性质设AE是所给活动安排问题的一个最优解，且A中的活动也按结束时间非递减排

11、序，A中的第一个活动是k。4.1 活动安排问题 正确性证明（用数学归纳法证明）1、 贪心选择性质若k1,则A就是以贪心选择开始的最优解。若k1,设B=A-k1。因为f1=fk且A中的活动是相容的。故B中的活动也是相容的。又由于B中的活动个数与A中的活动个数相同，故A是最优的，B也是最优的。即B是以选择活动1开始的最优活动安排。由此可见，总存在以贪心选择开始的最优活动安排方案。4.1 活动安排问题 正确性证明（用数学归纳法证明）2 、最优子结构性质在作出了贪心选择，即选择了活动1后，原问题简化为对E中所有与活动1相容的活动进行活动安排的子问题。即若A是原问题的最优解，则A=A-1是活动安排问题的

12、E=iE:Sif1的最优解。4.1 活动安排问题 正确性证明（用数学归纳法证明）2 、最优子结构性质反证法：若E中存在另一个解B，比A有更多的活动，则将1加入B中产生另一个解B，比A有更多的活动。与A的最优性矛盾。4.1 活动安排问题 正确性证明（用数学归纳法证明）因此，每一步所作出的贪心选择都将问题简化为一个更小的与原问题具有相同形式的子问题。对贪心选择次数用归纳法可知，贪心算法greedySelector产生问题的最优解。194.2 贪心算法的基本要素 本节着重讨论可以用贪心算法求解的问题的本节着重讨论可以用贪心算法求解的问题的一般特征。一般特征。 对于一个具体的问题，对于一个具体的问题，

13、怎么知道是否可用贪怎么知道是否可用贪心算法解此问题心算法解此问题，以及，以及能否得到问题的最优解能否得到问题的最优解呢呢? ?这个问题很难给予肯定的回答。这个问题很难给予肯定的回答。 但是，从许多可以用贪心算法求解的问题中但是，从许多可以用贪心算法求解的问题中看到这类问题一般看到这类问题一般具有具有2 2个重要的性质个重要的性质：贪心选择贪心选择性质性质和和最优子结构性质最优子结构性质。 204.2 贪心算法的基本要素1、贪心选择性质 所谓所谓贪心选择性质贪心选择性质是指所求问题的是指所求问题的整体最优解整体最优解可以可以通过一系列通过一系列局部最优局部最优的选择，即贪心选择来达到。这是的选择

14、，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。规划算法的主要区别。 动态规划算法通常以自底向上的方式解各子问题，而动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以贪心算法则通常以自顶向下自顶向下的方式进行，的方式进行，以迭代的方式以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题简化为规模更小的子问题。 对于一个具体问题，要确定它是否具有贪心选择性质，对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每

15、一步所作的贪心选择最终导致问题的整体最必须证明每一步所作的贪心选择最终导致问题的整体最优解。优解。214.2 贪心算法的基本要素 当一个问题的最优解包含其子问题的最优当一个问题的最优解包含其子问题的最优解时，称此问题具有解时，称此问题具有最优子结构性质最优子结构性质。问题的。问题的最优子结构性质是该问题可用动态规划算法或最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。贪心算法求解的关键特征。 2、最优子结构性质224.2 贪心算法的基本要素 贪心算法和动态规划算法都要求问题具有最优子贪心算法和动态规划算法都要求问题具有最优子结构性质，这是结构性质，这是2 2类算法的一个共同点。

16、但是，对于具类算法的一个共同点。但是，对于具有有最优子结构最优子结构的问题应该选用贪心算法还是动态规划的问题应该选用贪心算法还是动态规划算法求解算法求解? ?是否能用动态规划算法求解的问题也能用贪是否能用动态规划算法求解的问题也能用贪心算法求解心算法求解? ?下面研究下面研究2 2个经典的个经典的组合优化问题组合优化问题，并以，并以此说明贪心算法与动态规划算法的主要差别。此说明贪心算法与动态规划算法的主要差别。3、贪心算法与动态规划算法的差异234.2 贪心算法的基本要素 0-1背包问题： 给定给定n n种物品和一个背包。物品种物品和一个背包。物品i i的重量是的重量是W Wi i，其，其价值

17、为价值为V Vi i，背包的容量为，背包的容量为C C。应如何选择装入背包的物。应如何选择装入背包的物品，使得装入背包中物品的总价值最大品，使得装入背包中物品的总价值最大? ? 在选择装入背包的物品时，对每种物品在选择装入背包的物品时，对每种物品i i只有只有2 2种种选择，即装入背包或不装入背包。不能将物品选择，即装入背包或不装入背包。不能将物品i i装入背装入背包多次，也不能只装入部分的物品包多次，也不能只装入部分的物品i i。244.2 贪心算法的基本要素 背包问题： 与与0-10-1背包问题类似，所不同的是在选择物品背包问题类似，所不同的是在选择物品i i装入装入背包时，背包时，可以选

18、择物品可以选择物品i i的一部分的一部分，而不一定要全部装，而不一定要全部装入背包，入背包，1in1in。 这这2 2类问题都具有最优子结构性质，极为相似，但类问题都具有最优子结构性质，极为相似，但背包问题可以用贪心算法求解，而背包问题可以用贪心算法求解，而0-10-1背包问题却不能背包问题却不能用贪心算法求解。用贪心算法求解。 254.2 贪心算法的基本要素 首先计算每种物品单位重量的价值首先计算每种物品单位重量的价值V Vi i/W/Wi i，然后，依贪心，然后，依贪心选择策略，将尽可能多的选择策略，将尽可能多的单位重量价值最高单位重量价值最高的物品装入背包。的物品装入背包。若将这种物品全

19、部装入背包后，背包内的物品总重量未超过若将这种物品全部装入背包后，背包内的物品总重量未超过C C，则选择单位重量价值次高的物品并尽可能多地装入背包。依则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。此策略一直地进行下去，直到背包装满为止。 具体算法可描述如下页：具体算法可描述如下页： 用贪心算法解背包问题的基本步骤：264.2 贪心算法的基本要素 public static float knapsack(float c,float w, float v,float x) int n=v.length; Element d = new Element

20、n; for (int i = 0; i n; i+) di = new Element(wi,vi,i); MergeSort.mergeSort(d); int i; float opt=0; for (i=0;in;i+) xi=0; for (i=0;ic) break; xdi.i=1; /可以完全装入； opt+=di.v; c-=di.w; if (in) /不能完全装入di.w; xdi.i=c/di.w; /装入部分； opt+=xdi.i*di.v; return opt; 算法算法knapsackknapsack的的主要计算时间在于将主要计算时间在于将各种物品依其单位重各

21、种物品依其单位重量的价值从大到小排量的价值从大到小排序。因此，算法的计序。因此，算法的计算时间上界为算时间上界为O O（nlognnlogn）。当然，）。当然，为了证明算法的正确为了证明算法的正确性，还必须证明背包性，还必须证明背包问题具有贪心选择性问题具有贪心选择性质质。270-1背包问题不适用贪心算法 背包容量50kg，三物品的容量和价值分别为(10kg, $60), (20kg, $100)和(30kg, $120)。 单位重量价值最高的是物品1。但是依照贪心算法首选物品1却不能获得最优解：物品1物品2物品3总价值为$160,空余20 kg总价值为$180,空余10 kg总价值为$220

22、,没有空余物品1物品2物品3284.2 贪心算法的基本要素 对于对于0-10-1背包问题背包问题，贪心选择之所以不能得到最优解，贪心选择之所以不能得到最优解是因为在这种情况下，是因为在这种情况下，它无法保证最终能将背包装满，它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。部分闲置的背包空间使每公斤背包空间的价值降低了。事实上，在考虑事实上，在考虑0-10-1背包问题时，应比较选择该物品和不背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。选择该物品所导致的最终方案，然后再作出最好选择。由此就导出许多互相重叠的子问题。这正是该问题可用由此

23、就导出许多互相重叠的子问题。这正是该问题可用动态规划算法动态规划算法求解的另一重要特征。求解的另一重要特征。实际上也是如此，动态规划算法的确可以有效地解实际上也是如此，动态规划算法的确可以有效地解0-0-1 1背包问题。背包问题。 294.3 单源最短路径给定带权有向图给定带权有向图G =(V,E)G =(V,E)，其中每条边的权是非，其中每条边的权是非负实数。另外，还给定负实数。另外，还给定V V中的一个顶点，称为中的一个顶点，称为源源。现在。现在要计算从要计算从源源到到所有其它各顶点所有其它各顶点的的最短路长度最短路长度。这里路。这里路的长度是指路上各边权之和。这个问题通常称为的长度是指路

24、上各边权之和。这个问题通常称为单源单源最短路径问题最短路径问题。1、算法基本思想DijkstraDijkstra算法是解单源最短路径问题的贪心算法。算法是解单源最短路径问题的贪心算法。304.3 单源最短路径其其基本思想基本思想是，设置顶点集合是，设置顶点集合S S并不断地作并不断地作贪心选择贪心选择来扩充来扩充这个集合。一个顶点属于集合这个集合。一个顶点属于集合S S当且仅当从源到该顶点的最短路当且仅当从源到该顶点的最短路径长度已知。径长度已知。初始时，初始时，S S中仅含有源。设中仅含有源。设u u是是G G的某一个顶点，把的某一个顶点，把从源到从源到u u且且中间只经过中间只经过S S中

25、顶点中顶点的路称为的路称为从源到从源到u u的特殊路径的特殊路径，并用数组，并用数组distdist记录当前每个顶点所对应的最短特殊路径长度。记录当前每个顶点所对应的最短特殊路径长度。DijkstraDijkstra算法每算法每次次从从V-SV-S中取出具有最短特殊路长度的顶点中取出具有最短特殊路长度的顶点u u，将，将u u添加到添加到S S中，同中，同时对数组时对数组distdist作必要的修改。一旦作必要的修改。一旦S S包含了所有包含了所有V V中顶点，中顶点，distdist就就记录了从源到所有其它顶点之间的最短路径长度。记录了从源到所有其它顶点之间的最短路径长度。314.3 单源最

26、短路径例如例如，对右图中的，对右图中的有向图，应用有向图，应用DijkstraDijkstra算法计算从算法计算从源顶点源顶点1 1到其它顶点间到其它顶点间最短路径的过程列在最短路径的过程列在下页的表中。下页的表中。4.3 单源最短路径迭代迭代S Su udist2dist2 dist3dist3 dist4dist4 dist5dist5初始初始11- -1010maxintmaxint30301001001 11,21,22 21010606030301001002 21,2,41,2,44 410105050303090903 31,2,4,31,2,4,33 3101050503030

27、60604 41,2,4,3,51,2,4,3,5 5 51010505030306060DijkstraDijkstra算法的迭代过程：算法的迭代过程： 2.正确性证明1)贪心选择性质贪心选择：贪心选择：从从V-SV-S中选择具有最短特殊路径长度中选择具有最短特殊路径长度的顶点的顶点u u，从而确定源点到，从而确定源点到u u的最短路径长度的最短路径长度distudistu。这种选择为什么导致最优解？即为什么从源到这种选择为什么导致最优解？即为什么从源到u u没有更短的其它路径呢？没有更短的其它路径呢？4.3 单源最短路径2.正确性证明1)贪心选择性质反证法：若存在一条从源到反证法：若存在一

28、条从源到u u且长度且长度比比distudistu更短更短的路的路。设这条路初次走出。设这条路初次走出S S之外到达的顶点为之外到达的顶点为xV-xV-S S，然后徘徊于，然后徘徊于S S内外若干次，最后离开内外若干次，最后离开S S到达到达u u。distxdistxd(v,x)d(v,x)d(v,x)d(v,x)d(x,u)=d(v,u)d(x,u)=d(v,u)distudistu 得出矛盾。得出矛盾。4.3 单源最短路径Svux2.正确性证明2)最优子结构性质即在作出贪心选择后，如何保证剩余的问题仍是与原即在作出贪心选择后，如何保证剩余的问题仍是与原问题相似的子问题。问题相似的子问题。

29、关键是要确保关键是要确保distdist数组在将数组在将u u加入到加入到S S后仍使每个后仍使每个i i的的distidisti是当前最短的特殊路径长度。是当前最短的特殊路径长度。如何确保？如何确保？在在u u加入加入S S后，原来从源到后，原来从源到i i的最短特殊路径长度可的最短特殊路径长度可能会因为能会因为u u的加入而缩短，须进行的加入而缩短，须进行调整调整。4.3 单源最短路径2.正确性证明2)最优子结构性质将添加将添加u u之前的之前的S S称为老称为老S S。考虑三种可能：。考虑三种可能：i)disti-i)disti-原来的经过老的原来的经过老的S S直接到达直接到达i ii

30、i)distu+duiii)distu+dui经过老的经过老的S S到到u u，再从，再从u u经过经过一条边直接到达一条边直接到达i iiii)distu+d(u,x)+d(x,i)iii)distu+d(u,x)+d(x,i)经过老的经过老的S S到到u u，再，再从从u u回到老回到老S S中某个顶点中某个顶点x x，最后才到达，最后才到达i i4.3 单源最短路径Svixu2.正确性证明2)最优子结构性质考虑考虑iii)distu+d(u,x)+d(x,i)iii)distu+d(u,x)+d(x,i)经过老的经过老的S S到到u u，再从，再从u u回到老回到老S S中某个顶点中某个

31、顶点x x，最后才到达，最后才到达i i：d(v,x)=distxdistu=d(v,u)d(v,x)=distxdistu=d(v,u) d(v,x)d(v,u)+d(u,x) d(v,x)d(v,u)+d(u,x) distidisti d(v,x)+d(x,i)d(v,u)+d(u,x)+d(x,i)d(v,x)+d(x,i)d(v,u)+d(u,x)+d(x,i) 故不必考虑这种路径故不必考虑这种路径4.3 单源最短路径Svixu2.正确性证明如此调整后，使得在加入如此调整后，使得在加入u u到到S S后，后，distdist数组中存放数组中存放的仍然是从源到的仍然是从源到V-SV-S

32、中顶点的最短特殊路径长度。中顶点的最短特殊路径长度。问题变为与加入问题变为与加入u u前同样的子问题。前同样的子问题。如此继续，由归纳可知当如此继续，由归纳可知当V-SV-S为空时，为空时，distdist数组中将数组中将存放所有从源到该顶点的最短路径。存放所有从源到该顶点的最短路径。4.3 单源最短路径void dijkstra(int v, float a, float dist, int prev) int n = dist.length-1; boolean s=new boolean n+1; if(vn) return;for(i=1;i=n;i+)disti=avi; si=fa

33、lse;if(disti=MAX_VALUE)previ=0;elseprevi=v;distv=0;sv=true;for(i=1;in;i+)u=v; temp=MAX_VALUE;for(j=1;j=n;j+) if ( (!sj) & (distjtemp) ) u=j; temp=distj; su=true;for(j=1;jn;j+) if ( (!sj) & (aujMAX_VALUE) )if(distu+aujdistj) distj=distu+auj; prevj=u;输入的带权有向图G=（V，E），v是源点，a是一个二维数组，aij表示边（i，j）的权

34、。404.3 单源最短路径计算复杂性对于具有对于具有n n个顶点和个顶点和e e条边的带权有向图，如果用带条边的带权有向图，如果用带权邻接矩阵表示这个图，那么权邻接矩阵表示这个图，那么DijkstraDijkstra算法的主循环体算法的主循环体需要需要 时间。这个循环需要执行时间。这个循环需要执行n-1n-1次，所以完成次，所以完成循环需要循环需要 时间。算法的其余部分所需要时间不时间。算法的其余部分所需要时间不超过超过 。414.4 最小生成树 设G = (V, E)是无向连通带权图，即一个网络。E的每条边(v, w)的权为cvw。如果G的一个子图G是一棵包含G的所有顶点的树，则称G为G的生

35、成树。生成树各边权的总和称为其耗费。在G的所有生成树中，耗费最小的生成树称为G的最小(优)生成树。 424.4 最小生成树最小生成树性质用贪心算法设计策略可以设计出构造最小生成树的有效算用贪心算法设计策略可以设计出构造最小生成树的有效算法。本节介绍的构造最小生成树的法。本节介绍的构造最小生成树的PrimPrim算法算法和和KruskalKruskal算法算法都都可以看作是应用贪心算法设计策略的例子。尽管这可以看作是应用贪心算法设计策略的例子。尽管这2 2个算法做贪个算法做贪心选择的方式不同，它们都利用了下面的心选择的方式不同，它们都利用了下面的最小生成树性质最小生成树性质：设设G=(V,E)G

36、=(V,E)是连通带权图，是连通带权图，U U是是V V的真子集。如果的真子集。如果(u,v)(u,v)E E，且且u uU U，v vV-UV-U，且在所有这样的边中，且在所有这样的边中，(u,v)(u,v)的权的权cuvcuv最最小，那么一定存在小，那么一定存在G G的一棵最小生成树，它以的一棵最小生成树，它以(u,v)(u,v)为其中一条为其中一条边。这个性质有时也称为边。这个性质有时也称为MSTMST性质性质。 43树的基本性质 连通无回路的图G称为树。 树是点比边多一且连通， q=p1且连通 。 树是点比边多一且无回路： q=p1且无回路。 树若添条边就有回路：G无回路，若u, vG

37、且uv E(G)，则G+uv中恰有一条回路。 树若减条边就不连通：G连通，对eE(G), Ge不连通。 n个顶点的连通图的生成树含有n 1条边。44求最小生成树的思路 一个很直观的简单想法：依次选出依据图G的权重较轻的n 1条边。这样得到的n 1条边的权重之和肯定是最小的。但是这样是否就得到了G的一棵最小生成树呢？不行！因为不能保证这n 1条边构成树？怎样才能保证这n 1条边构成树呢？生成树是含有n个顶点和n 1条边的连通并且无回路的图。45求最小生成树的两种策略 策略一：在保证连通的前提下依次选出权重较小的n 1条边(在实现中体现为n个顶点的选择)。 策略二： 在保证无回路的前提下依次选择权

38、重较小的n 1条边。Prim算法的做法Kruskal算法的做法46Prim算法 基本思想：设G=(V, E)为无向连通带权图，令V=1, , n。在保证连通的前提下依次选出权重较小的n 1条边。 设置一个集合S ，初始化S = 1，T = 。 如果VS中的顶点j与S中的某点i连接且(i, j)是E-T中的权重最小的边，于是就选择j(将j加入S)，并将(i, j) 加入T中 。 重复执行贪心策略，直至VS为空。 47Prim算法的示例 给定一个连通带权图如下：1234561655536624初始时S=1，T= ；1第一次选择：(1, 3)权最小 S=1, 3T= (1, 3) ；348Prim算

39、法的示例 给定一个连通带权图如下：1234561655536624初始时S=1，T= ；136第二次选择：(3, 6)权最小 S=1, 3, 6， T= (1, 3), (3, 6) ；49Prim算法的示例 给定一个连通带权图如下：1234561655536624初始时S=1，T= ；136第三次选择：(6, 4)权最小 S=1, 3, 6, 4，T= (1, 3), (3, 6), (6, 4) ；450Prim算法的示例 给定一个连通带权图如下：1234561655536624初始时S=1，T= ；1364第四次选择：(2, 3)权最小 S=1, 3, 6, 4, 2，T= (1, 3)

40、, (3, 6), (6, 4), (2, 3)251Prim算法的示例 给定一个连通带权图如下：1234561655536624初始时S=1，T= ；13642第五次选择：(5, 2)权最小 S=1, 3, 6, 4, 2, 5， T= (1, 3), (3, 6), (6, 4), (3, 2) (2, 5) 552Prim算法中的数据结构 图用邻接矩阵Cij给出，即Cij为结点i到结点j的权重。 为了有效地找出VS中满足与S中的某个点i连接且(i, j) 权重最小的顶点j，对其中每个顶点j设立两个数组closestj和lowcostj： closestj是S中与j最近的顶点，(close

41、stj, j)即为选中的边，而lowcostj是相应这条边的权重。53Prim算法的实现 Prim(int n, Type *c) 执行以下操作n1次：依据lowcost找出与S最近的点j并放入S； 调整lowcost和closest； 初始化：结点1放入S；并初始化lowcost和 closest；54Prim算法的实现 Prim(int n, Type *c) 执行以下操作n1次：int j = 1; sj = true; for (int i = 2; i = n; i+) si=false; closesti = 1; lowcosti = c1i;依据lowcost找出与S最近的点j

42、并放入S； 调整lowcost和closest；将结点1放入S中其余结点都不在S中且与S的最近距离是与结点1的距离。55Prim算法的实现 Prim(int n, Type *c) int j = 1; sj = true; for (int i = 2; i = n; i+) si=false; closesti = 1; lowcosti=c1i; 调整lowcost和closest；for (int i = 1; i n; i+) min = inf; for (int k = 2; k = n; k+) if (lowcostk min&!sk) min = lowcostk;

43、 j = k; sj = true; 依据lowcost找出与S最近的点j并放入S。56Prim算法的实现 Prim(int n, Type *c) int j = 1; sj = true; for (int i = 2; i = n; i+) si=false; closesti = 1; lowcosti=c1i;for (int i = 1; i n; i+) min= inf; for (int k = 2; k = n; k+) if (lowcostkmin&!sk) min = lowcostk; j = k; sj = true; s中仅加入了一个新成员j，因此只需要

44、依据结点j 调整lowcost和closest； 57Prim算法的实现 Prim(int n, Type *c) int j = 1; sj = true; for (int i = 2; i = n; i+) si=false; closesti = 1; lowcosti=c1i;for (int i = 1; i n; i+) min= inf; for (int k = 2; k = n; k+) if (lowcostkmin&!sk) min = lowcostk; j = k; sj = true; for (int k = 2; k = n; k+) if (cjk

45、lowcostk&!sk) lowcostk = cjk; closestk = j; 58Kruskal算法 基本思想：在保证无回路的前提下依次选出权重较小的n 1条边。 具体做法：若(i, j)是E中尚未被选的边中权重最小的，且(i, j)不会与已经选择的边构成回路，于是就选择 (i, j)。问题：如何知道问题：如何知道(i, j)不会造成回路？不会造成回路？59Kruskal算法 基本思想：在保证无回路的前提下依次选出权重较小的n 1条边。 具体做法：若(i, j)是E中尚未被选的边中权重最小的，且(i, j)不会与已经选择的边构成回路，于是就选择 (i, j)。若边(i, j)

46、 的端点i和j属于同一个连通分支，则选择(i, j) 造成回路，否则不造成回路。初始时将图的n个顶点看成n个孤立分支。60Kruskal算法的数据结构 数组e表示图的边，eiu、eiv和eiw分别表示边i的两个端点及其权重。 函数Sort(e, w)对数组e按权重w排序。 一个连通分支中的顶点表示为一个集合。 函数Initialize(n)将每个顶点作为一个集合。 函数Find(u)给出顶点u所在的集合。 函数Union(a, b)给出集合a和集合b的并集。 重载算符!=判断集合的不相等。61Kruskal算法的实现 Kruskal(int n, *e) Sort(e, w); initial

47、ize(n); k = 1; j = 1; while (k n) a = Find(eju); b = Find(ejv); if (a != b) tk+ = j; Union(a, b); j+; 将边按权重从小到大排序。将边按权重从小到大排序。初始时每个顶点为一个集合。初始时每个顶点为一个集合。k k累计已选的边数，累计已选的边数，j j为边在为边在e e中序号，从权重最小的边开始中序号，从权重最小的边开始选取。选取。选择了选择了n 1条边后终止循环。条边后终止循环。找出第找出第j j条边两端点所在集合。条边两端点所在集合。若两端点属于不同集合，则若两端点属于不同集合，则将第将第j条边

48、放入树中并把这条边放入树中并把这两个集合合并。两个集合合并。继续考察下一条边。继续考察下一条边。62Kruskal算法的例子1234561655536624131462253364145235345126356566初始时为6个孤立点。123456uvw63Kruskal算法的例子1234561655536624131462253364145235345126356566123456选择了边1，于是1、3点合并为同一个集合。uvw64Kruskal算法的例子1234561655536624131462253364145235345126356566123456选择了边2，于是4、6点合并为同一个集合。uvw65Kruskal算法的例子1234561655536624131462253364145235345126356566123456uvw选择了边3，于是2、5点合并为同一个集合。66Kruskal算法的例子1234561655536624131462253364145235345126356566123456uvw选择了边4，于是1、3、4、6点合并为同一集合。67Kruskal算法的例子1234561655536624131462253364145235345126356566123456uvw考察边5，因为1、4点属于同一个集合，被放弃。68Kruskal算法的