1、University of Science and Technology of China主讲人：主讲人： 吕敏吕敏Email: Spring 2012，USTC算法基础算法基础University of Science and Technology of China2022-6-42第十讲第十讲 贪心算法贪心算法内容提要：内容提要：p 理解贪心算法的概念理解贪心算法的概念p 掌握贪心算法的基本要素掌握贪心算法的基本要素p 理解贪心算法与动态规划算法的差异理解贪心算法与动态规划算法的差异p 通过范例学习贪心算法设计策略通过范例学习贪心算法设计策略University of Science an
2、d Technology of China10.1 活动安排问题活动安排问题2022-6-43l当一个问题具有当一个问题具有最优子结构最优子结构性质时，可用动态规划法性质时，可用动态规划法求解，但有时用贪心算法求解会更加的简单有效。求解，但有时用贪心算法求解会更加的简单有效。l顾名思义，顾名思义，贪心算法总是作出在当前看来最好的选择贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的的选择只是在某种意义上的局部最优局部最优选择。当然，希选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪
3、望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似得到整体最优解，其最终结果却是最优解的很好近似。University of Science and Technology of China10.1 活动安排问题活动安排问题2022-6-44l设有设有n n个活动的集合个活动的集合E
4、=1,2,nE=1,2,n，l每个活动都要求使用同一资源，如演讲会场等，而每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。在同一时间内只有一个活动能使用这一资源。l每个活动每个活动i i都有一个要求使用该资源的起始时间都有一个要求使用该资源的起始时间s si i和和一个结束时间一个结束时间f fi i, ,且且s si i f fi i 。如果选择了活动。如果选择了活动i i，则它在，则它在半开时间区间半开时间区间 s si i, , f fi i) )内占用资源。内占用资源。l若区间若区间 s si i, , f fi i) )与区间与区间 s sj j,
5、 , f fj j) )不相交，则称不相交，则称活动活动i i与活动与活动j j是相容的是相容的。即当。即当s si iffj j或或s sj jffi i时，活动时，活动i i与活动与活动j j相容相容. .l问题：选出最大的相容活动子集合。问题：选出最大的相容活动子集合。University of Science and Technology of China10.1 活动安排问题活动安排问题2022-6-45p（用动态规划方法）（用动态规划方法）l步骤步骤1 1：分析最优解的结构特征：分析最优解的结构特征 构造子问题空间构造子问题空间: :S Sij ij= = a ak kSS: :
6、f fi issk kf fk kssj j S Sij ij包含了所有与包含了所有与a ai i和和a aj j相兼容的活动，并且与不迟于相兼容的活动，并且与不迟于a ai i结束和不早于结束和不早于a aj j开始的活动兼容。此外，虚构活动开始的活动兼容。此外，虚构活动a a0 0和和a an+1n+1，其中，其中f f0 0=0, S=0, Sn+1n+1=。原问题即为寻找。原问题即为寻找S S0,n+10,n+1中最大中最大兼容活动子集。兼容活动子集。University of Science and Technology of China10.1 活动安排问题活动安排问题2022-6
7、-46 证明原问题具有最优子结构性质。即：证明原问题具有最优子结构性质。即：若已知问题若已知问题S Sij ij的最优解的最优解A Aij ij中包含活动中包含活动a ak k，则在，则在S Sij ij最优解中的针对最优解中的针对S Sik ik的的解解A Aik ik和针对和针对S Skj kj的解的解A Akj kj也必定是最优的。（反证法即可也必定是最优的。（反证法即可！）！） 证明可以根据子问题的最优解来构造出原问题的最优证明可以根据子问题的最优解来构造出原问题的最优解。解。一个非空子问题一个非空子问题S Sij ij的任意解中必包含了某项活动的任意解中必包含了某项活动a ak k，
8、而，而S Sij ij的任一最优解中都包含了其子问题实例的任一最优解中都包含了其子问题实例S Sik ik和和S Skj kj的的最优解（根据最优子结构性质！）。因此，可以构造最优解（根据最优子结构性质！）。因此，可以构造出出S Sij ij的最大兼容子集。的最大兼容子集。University of Science and Technology of China10.1 活动安排问题活动安排问题2022-6-47p步骤步骤2 2：递归地定义最优解的值：递归地定义最优解的值 设设cici, j, j为为S Sij ij中最大兼容子集中的活动数。当中最大兼容子集中的活动数。当S Sij ij=时，
9、时，cici, j = 0, j = 0。对于一个非空子集。对于一个非空子集S Sij ij，如果，如果a ak k在在S Sij ij的最大兼容子集中被使用，则的最大兼容子集中被使用，则子问题子问题S Sik ik和和S Skj kj的最大兼容子集也被使用。从而：的最大兼容子集也被使用。从而： cici, j = , j = cici, k + , k + ckck, j + 1, j + 1 由于由于S Sij ij的最大子集一定使用了的最大子集一定使用了i i到到j j中的某个值中的某个值k k，通过检查所有可，通过检查所有可能的能的k k值，就可以找到最好的一个。因此，值，就可以找到最
10、好的一个。因此，cici, j, j的完整递归定义的完整递归定义为：为：SijjkckicSijjicjki?1,max0,University of Science and Technology of China10.1 活动安排问题活动安排问题2022-6-48p问题：问题： k k有有j-i-1j-i-1种选择，每种选择会导致种选择，每种选择会导致2 2个完全不同的子问个完全不同的子问题产生，因此，动态规划算法的计算量比较大！题产生，因此，动态规划算法的计算量比较大！一个直观想法是一个直观想法是直接选择直接选择k k的值的值，使得一个子问题为空，使得一个子问题为空，从而加快计算速度！这就
11、导致了贪心算法！，从而加快计算速度！这就导致了贪心算法！University of Science and Technology of China10.1 活动安排问题活动安排问题2022-6-49p（用贪心算法）（用贪心算法） 贪心策略贪心策略：对输入的活动以其完成时间的：对输入的活动以其完成时间的非减序非减序排列，算法每次排列，算法每次总是选择总是选择具有最早完成时间具有最早完成时间的相容活动加入最优解集中。直观上的相容活动加入最优解集中。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。，按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是
12、也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极使剩余的可安排时间段极大化大化，以便安排尽可能多的相容活动。，以便安排尽可能多的相容活动。 例：例：设待安排的设待安排的11 11个活动的开始时间和结束时间按结束时间的非减个活动的开始时间和结束时间按结束时间的非减序排列如下：序排列如下：i1234567891011Si130535688212fi4567891011121314University of Science and Technology of China10.1 活动安排问题活动安排问题2022-6-410University of Science and Technolog
13、y of China10.1 活动安排问题活动安排问题2022-6-411Recursive-Activity-Recursive-Activity-Selector(sSelector(s, f, i, j) , f, i, j) m i+1; m i+1; while mj and while mj and smsmfi fi do m m+1 do m m+1 if mj if mj then return am U Recursive-Activity- then return am U Recursive-Activity-Selector(sSelector(s, f, m, j)
14、, f, m, j) else return else return 说明：说明： 1 1）数组）数组s s和和f f表示活动的开始和结束时间，表示活动的开始和结束时间，n n个输入活动已经按照活动结束时个输入活动已经按照活动结束时间进行单调递增顺序排序；间进行单调递增顺序排序； 2 2）算法）算法 目的是寻找目的是寻找S Sij ij中最早结束的第一个活动，即找到与中最早结束的第一个活动，即找到与a ai i兼容的兼容的第一个活动第一个活动a amm，利用，利用a amm与与S Smjmj的最优子集的并集构成的最优子集的并集构成S Sij ij的最优子集；的最优子集；3 3）时间复杂度）时间
15、复杂度O(nO(n) )。University of Science and Technology of China10.1 活动安排问题活动安排问题2022-6-412lRecursive-Activity-SelectorRecursive-Activity-Selector属于递归性贪心算法，它以对自己的递属于递归性贪心算法，它以对自己的递归调用的并操作结束，几乎就是归调用的并操作结束，几乎就是“尾递归调用尾递归调用”，因此可以转化，因此可以转化为迭代形式：为迭代形式：Greedy-Activity-Selector( s, f )Greedy-Activity-Selector( s,
16、 f ) n n lengthslengths; ; A a A a1 1 i 1 / i 1 /下标下标i i记录了最近加入记录了最近加入A A的活动的活动a ai i for m 2 to n / for m 2 to n /寻找寻找S Si,n+1i,n+1中最早结束的兼容活动中最早结束的兼容活动 do if do if s smm f fi i then A A U a then A A U amm i m i m return A; return A; University of Science and Technology of China10.1 活动安排问题活动安排问题2022
17、-6-413p贪心算法的正确性证明：贪心算法的正确性证明： 定理定理16.116.1：对于任意非空子问题对于任意非空子问题S Sij ij，设，设a amm是是S Sij ij中具有最中具有最早结束时间的活动，即早结束时间的活动，即 f fmm = min = min f fk k : : a ak kSSij ij ，则：，则： 1 1）活动）活动a amm在在S Sij ij的某最大兼容活动子集中被使用；的某最大兼容活动子集中被使用； 2 2）子问题）子问题S Simim为空，所以选择为空，所以选择a amm将使子问题将使子问题S Smjmj为唯一为唯一可能非空的子问题。可能非空的子问题。
18、University of Science and Technology of China10.1 活动安排问题活动安排问题2022-6-414定理定理16.116.1：对于任意非空子问题对于任意非空子问题S Sij ij，设，设a amm是是S Sij ij中具有最早中具有最早结束时间的活动，即结束时间的活动，即 f fmm = min = min f fk k : : a ak kSSij ij ，则：，则： 1 1）活动）活动a amm在在S Sij ij的某最大兼容活动子集中被使用；的某最大兼容活动子集中被使用； 2 2）子问题）子问题S Simim为空，所以选择为空，所以选择a am
19、m将使子问题将使子问题S Smjmj为唯一为唯一可能非空的子问题。可能非空的子问题。证明：证明： 先证第先证第2 2部分。假设部分。假设S Simim非空，因此有活动非空，因此有活动a ak k满足满足f fi issk kf fk kssmmf c) break; c) break; xixi=1;=1; c-= c-=wiwi; ; if( if( inin) ) xixi = = c/wic/wi; /; /使物品使物品i i是选择的最后一项是选择的最后一项 p时间复杂度时间复杂度: : T(nT(n) = ) = O(nlgnO(nlgn) )University of Science
20、 and Technology of China10.3 小数背包问题小数背包问题2022-6-427p贪心选择的最优性证明贪心选择的最优性证明 定理：定理：如果如果v v1 1/w/w1 1 v v2 2/w/w2 2 v vn n/w/wn n ，则，则GreedyKnapsackGreedyKnapsack算算法对于给定的背包问题实例生成一个最优解法对于给定的背包问题实例生成一个最优解 证明基本思想证明基本思想： 把贪心解与任一最优解相比较，如果这两个解不同，就去找把贪心解与任一最优解相比较，如果这两个解不同，就去找开始不同的第一个开始不同的第一个x xi i，然后设法用贪心解的，然后设
21、法用贪心解的x xi i去代换最优解的去代换最优解的x xi i，并证明最优解在分量代换之后其总价值保持不变，反复进行下去并证明最优解在分量代换之后其总价值保持不变，反复进行下去，直到新产生的最优解与贪心解完全一样，从而证明了贪心解是，直到新产生的最优解与贪心解完全一样，从而证明了贪心解是最优解。最优解。University of Science and Technology of China10.3 小数背包问题小数背包问题2022-6-428University of Science and Technology of China10.3 小数背包问题小数背包问题2022-6-429Uni
22、versity of Science and Technology of China10.3 小数背包问题小数背包问题2022-6-430p特殊的特殊的0-10-1背包问题：背包问题： 如果如果 ww1 1ww2 2 wwn n, v, v1 1 v v2 2 v vn n, , 则则 v v1 1/w/w1 1 v v2 2/w/w2 2 v vn n/w/wn n，此时可以用贪心法求最优解。，此时可以用贪心法求最优解。0-1-Knapsack( v, w, n, c )0-1-Knapsack( v, w, n, c ) / /输出输出x1nx1n for i=1 to n do for
23、i=1 to n do xixi=0;=0; value = 0.0; value = 0.0; for i=1 to n do for i=1 to n do if ( if ( wiwic )c ) xixi = 1; c-= = 1; c-= wiwi; value +=; value +=vivi; ; else break; else break; return value; return value; University of Science and Technology of China10.4 最优装载最优装载2022-6-431p问题的描述问题的描述: : 轮船载重为轮船载
24、重为c c，集装箱重量为，集装箱重量为wwi i( i = 1, 2, , n)( i = 1, 2, , n)，在装载体积，在装载体积不受限制的情况下，将尽可能多的集装箱装上船。不受限制的情况下，将尽可能多的集装箱装上船。p形式化定义形式化定义：University of Science and Technology of China10.4 最优装载最优装载2022-6-432p贪心策略：贪心策略：从剩下的货箱中，选择重量最小的货箱。这种选择次从剩下的货箱中，选择重量最小的货箱。这种选择次序可以保证所选的货箱总重量最小，从而可以装载更多的货箱。序可以保证所选的货箱总重量最小，从而可以装载更
25、多的货箱。根据这种贪心策略，首先选择最轻的货箱，然后选择次轻的货箱根据这种贪心策略，首先选择最轻的货箱，然后选择次轻的货箱，如此下去直到所有货箱均装上船或者船上不能容纳其他任何一，如此下去直到所有货箱均装上船或者船上不能容纳其他任何一个货箱。个货箱。p计算实例：计算实例：假设假设 n =8, wn =8, w1 1,w,w2 2, w, w8 8 = 100,200, 50, 90, 150, = 100,200, 50, 90, 150, 50, 20, 80, c=40050, 20, 80, c=400。 利用贪心算法时，所考察货箱的顺序为利用贪心算法时，所考察货箱的顺序为7, 3, 6
26、, 8, 4, 1, 5, 27, 3, 6, 8, 4, 1, 5, 2。 货箱货箱7, 3, 6, 8, 4, 17, 3, 6, 8, 4, 1的总重量为的总重量为390390个单位且已被装载，剩下的装个单位且已被装载，剩下的装载能力为载能力为1010个单位，小于剩下的任何一个货箱。个单位，小于剩下的任何一个货箱。 在这种贪心解决算法中得到在这种贪心解决算法中得到xx1 1,x ,x2 2,x,x8 8 = 1,0,1,1,0,1,1,1 = 1,0,1,1,0,1,1,1，且，且x xi i = 6 = 6University of Science and Technology of
27、China10.4 最优装载最优装载2022-6-433p算法描述：算法描述：ContainerLoadingContainerLoading( x, w, c, n)( x, w, c, n) / /xixi=1=1当且仅当货箱当且仅当货箱i i被装载，对重量按间接寻址方式排序被装载，对重量按间接寻址方式排序 new tn+1; / new tn+1; /产生数组产生数组t t，用于间接寻址，用于间接寻址 IndirectSort(wIndirectSort(w, t, n); /, t, n); /此时，此时，wtiwti wti+1, 1 i n wti+1, 1 i n for i =
28、 1 to n do / for i = 1 to n do /初始化初始化x x x i =0; x i =0; for( i=1; i n & for( i=1; i n & wtiwti c; i+ ) c; i+ ) / /按重量次序选择物品按重量次序选择物品 xtixti = 1; = 1; c = c- c = c- wtiwti; /c; /c为剩余容量为剩余容量 delete t; delete t; 时间复杂度：时间复杂度：O(nlgnO(nlgn) )University of Science and Technology of China10.4 最优装载最优装载2022
29、-6-434p贪心性质证明：贪心性质证明： 不失一般性，假设货箱都排好序，即不失一般性，假设货箱都排好序，即wwi iwwi+1i+1 (1 i (1 i n) n)。 令令x=xx=x1 1,x xn n 为用贪心算法获得的解，为用贪心算法获得的解，y=yy=y1 1,y yn n 为一个最优解，分若干步可以将为一个最优解，分若干步可以将y y转化为转化为x x，转换过程，转换过程中每一步都产生一个可行的新中每一步都产生一个可行的新y y，且，且y yi i（ 1 i n 1 i n ）的值不变（即仍为最优解），从而证明了）的值不变（即仍为最优解），从而证明了x x为最优解为最优解。Univ
30、ersity of Science and Technology of China10.5 找钱问题找钱问题2022-6-435p问题定义：问题定义： 使用使用2 2角角5 5分，分，1 1角，角，5 5分和分和1 1分四种面值的硬币时（各种硬币分四种面值的硬币时（各种硬币数量不限），设计一个找数量不限），设计一个找A A分钱的贪心算法，并证明算法能产生分钱的贪心算法，并证明算法能产生一个最优解。设货币种类一个最优解。设货币种类P=pP=p1 1,p,p2 2,p,p3 3,p,p4 4 ，d di i和和x xi i分别是分别是p pi i的货币的货币单位和选择数量，问题的形式描述为：单位和
31、选择数量，问题的形式描述为：University of Science and Technology of China10.5 找钱问题找钱问题2022-6-436University of Science and Technology of China10.5 找钱问题找钱问题2022-6-437p最优子结构性质证明：University of Science and Technology of China10.5 找钱问题找钱问题2022-6-438p贪心选择性质证明：University of Science and Technology of China10.5 找钱问题找钱问题202
32、2-6-439p 思考：思考： 如果硬币面值改为如果硬币面值改为1 1分、分、5 5分和分和1 1角角1 1分，要找给顾客的是分，要找给顾客的是1 1角角5 5分，分，是否可以用贪心算法？是否可以用贪心算法？University of Science and Technology of China10.6 单源最短路径单源最短路径2022-6-440p问题描述问题描述: : 给定带权有向图给定带权有向图G =(V,E)G =(V,E)，其中每条边的权是非负实数。另外，其中每条边的权是非负实数。另外，还给定还给定V V中的一个顶点，称为中的一个顶点，称为源源。现在要计算从源到所有其它各。现在要计
33、算从源到所有其它各顶点的顶点的最短路长度最短路长度。这里路的长度是指路上各边权之和。这个问。这里路的长度是指路上各边权之和。这个问题通常称为题通常称为单源最短路径问题单源最短路径问题。如：如：计算顶点计算顶点1 1（源）到所有其他顶点之间的最短路径。（源）到所有其他顶点之间的最短路径。University of Science and Technology of China10.6 单源最短路径单源最短路径2022-6-441p迪杰斯特拉迪杰斯特拉( (DijkstraDijkstra) )算法：算法： 基本思想：基本思想：设置顶点集合设置顶点集合S S并不断地作并不断地作贪心选择贪心选择来扩
34、充这个集合。来扩充这个集合。一个顶点属于集合一个顶点属于集合S S当且仅当从源到该顶点的最短路径长度已知。当且仅当从源到该顶点的最短路径长度已知。p步骤：步骤：初始时，初始时，S S中仅含有源。设中仅含有源。设u u是是G G的某一个顶点，把从源到的某一个顶点，把从源到u u且中间且中间只经过只经过S S中顶点的路称为从源到中顶点的路称为从源到u u的特殊路径，并用数组的特殊路径，并用数组distdist记录记录当前每个顶点所对应的最短特殊路径长度。当前每个顶点所对应的最短特殊路径长度。每次从每次从V-SV-S中取出具有最短特殊路长度的顶点中取出具有最短特殊路长度的顶点u u ( (贪心策略贪
35、心策略) )，将，将u u添添加到加到S S中，同时对数组中，同时对数组distdist作必要的修改。作必要的修改。直到直到S S包含了所有包含了所有V V中顶点，此时，中顶点，此时，distdist就记录了从源到所有其它就记录了从源到所有其它顶点之间的最短路径长度。顶点之间的最短路径长度。University of Science and Technology of China10.6 单源最短路径单源最短路径2022-6-442例如例如，对右图中的有向图，应用迪杰斯特，对右图中的有向图，应用迪杰斯特拉算法计算从源顶点拉算法计算从源顶点1 1到其它顶点间最短到其它顶点间最短路径的过程列如下表
36、所示。路径的过程列如下表所示。迭代Sudist2dist3dist4dist5初始1-10maxint3010011,2210603010021,2,441050309031,2,4,331050306041,2,4,3,5510503060University of Science and Technology of China10.6 单源最短路径单源最短路径2022-6-443p算法描述：University of Science and Technology of China10.6 单源最短路径单源最短路径2022-6-444p算法的运算时间：算法的运算时间： 对于一个具有对于一个具
37、有n n个顶点和个顶点和e e条边的带权有向图，如果用带权邻接矩条边的带权有向图，如果用带权邻接矩阵表示这个图，那么阵表示这个图，那么DijkstraDijkstra算法的主循环体需要算法的主循环体需要O(nO(n) )时间。这个时间。这个循环需要执行循环需要执行n-1n-1次，所以完成循环需要次，所以完成循环需要O(nO(n2 2) )时间。算法的其余时间。算法的其余部分所需要时间不超过部分所需要时间不超过O(nO(n2 2) )。University of Science and Technology of China10.6 单源最短路径单源最短路径2022-6-445p贪心策略为：贪心
38、策略为：从从V-SV-S中选择具有最短特殊路径的顶点中选择具有最短特殊路径的顶点u u，从而确定从源到从而确定从源到u u的最短路径长度的最短路径长度distudistu 。p贪心选择性质证明：贪心选择性质证明： 证明证明: :（反证法）（反证法）即证明从源到即证明从源到u u没有更短的其他路径。没有更短的其他路径。假设存在一条从源到假设存在一条从源到u u且长度比且长度比distudistu 更短的路，设这条路初次走出更短的路，设这条路初次走出S S之之外到达顶点为外到达顶点为x#Vx#V-S -S，然后徘徊于，然后徘徊于S S内外若干内外若干 次，最后离开达到次，最后离开达到u u，如，如
39、上图所示。上图所示。在这条路径上，分别记在这条路径上，分别记d(v,xd(v,x) )，d(x,ud(x,u) )和和d(v,ud(v,u) )为顶点为顶点v v到顶点到顶点x x，顶点，顶点x x到顶点到顶点u u和顶点和顶点v v到顶点到顶点u u的路长，那么的路长，那么 distxdistx=d (=d (v,xv,x) ) d(vd(v, x) + , x) + d(xd(x, u) = , u) = d(v,ud(v,u) ) =0)=0，从而推得，从而推得distxdistxdistudistu 。此为。此为矛盾。这就证明了矛盾。这就证明了distudistu 是从源到顶点是从源到
40、顶点u u的最短路径长度。的最短路径长度。 S Sv vu ux xUniversity of Science and Technology of China10.7 最小生成树最小生成树p 问题描述：问题描述： 设设G =(V,E)G =(V,E)是无向连通带权图，即一个是无向连通带权图，即一个网络网络。E E中每条中每条边边( (v,wv,w) )的权为的权为cvwcvw 。如果。如果G G的子图的子图GG是一棵包含是一棵包含G G的所有顶点的树，则称的所有顶点的树，则称GG为为G G的生成树。生成树上的生成树。生成树上各边权的总和称为该生成树的各边权的总和称为该生成树的耗费耗费。在。在G
41、 G的所有生成的所有生成树中，耗费最小的生成树称为树中，耗费最小的生成树称为G G的的最小生成树最小生成树。2022-6-446University of Science and Technology of Chinap 应用实例：通信线路设计、电子线路设计等应用实例：通信线路设计、电子线路设计等 网络的最小生成树在实际中有广泛应用。网络的最小生成树在实际中有广泛应用。例如例如，在设，在设计通信网络时，用图的顶点表示城市，用边计通信网络时，用图的顶点表示城市，用边( (v,wv,w) )的权的权cvwcvw 表示建立城市表示建立城市v v和城市和城市w w之间的通信线路所需的之间的通信线路所需
42、的费用，则最小生成树就给出了建立通信网络的最经济费用，则最小生成树就给出了建立通信网络的最经济的方案。的方案。2022-6-44710.7 最小生成树最小生成树University of Science and Technology of Chinap 最小生成树性质：最小生成树性质：设设G=(V,E)G=(V,E)是连通带权图，是连通带权图，U U是是V V的真子集。如果的真子集。如果( (u,v)u,v) E E，且，且u u U U，v v V V-U-U，且在所有这样的边中，且在所有这样的边中，( (u,vu,v) )的权的权cuvcuv 最小，那么最小，那么一定存在一定存在G G的一
43、棵最小生成树，它以的一棵最小生成树，它以( (u,vu,v) )为其中一条边。这个性为其中一条边。这个性质有时也称为质有时也称为MSTMST性质性质。 用贪心算法设计策略可以设计出构造最小生成树的有效算法。常用贪心算法设计策略可以设计出构造最小生成树的有效算法。常用的构造最小生成树的用的构造最小生成树的PrimPrim算法算法和和KruskalKruskal算法算法都可以看作是应都可以看作是应用贪心算法设计策略的例子。尽管这用贪心算法设计策略的例子。尽管这2 2个算法做贪心选择的方式个算法做贪心选择的方式不同，它们都利用了上面的不同，它们都利用了上面的最小生成树性质最小生成树性质。2022-6
44、-44810.7 最小生成树最小生成树University of Science and Technology of Chinap PrimPrim算法基本思想：算法基本思想： 设设G=(V,E)G=(V,E)是连通带权图，是连通带权图，V=1,2,V=1,2,n,n，PrimPrim算法算法首先置首先置S=1S=1，然后，只要，然后，只要S S是是V V的真子集，就作如下的的真子集，就作如下的贪心选择：贪心选择：选取满足条件选取满足条件i i S S，j j V V-S-S，且，且cijcij 最最小的边，将顶点小的边，将顶点j j添加到添加到S S中。这个过程一直进行到中。这个过程一直进行
45、到S=VS=V时为止。时为止。 在这个过程中选取到的所有边恰好构成在这个过程中选取到的所有边恰好构成G G的一棵的一棵最小最小生成树生成树。2022-6-44910.7 最小生成树最小生成树Prim算法算法University of Science and Technology of China 利用最小生成树性质和数学利用最小生成树性质和数学归纳法容易证明，上述算法归纳法容易证明，上述算法中的中的边集合边集合T T始终包含始终包含G G的某的某棵最小生成树中的边棵最小生成树中的边。因此。因此，在算法结束时，在算法结束时，T T中的所中的所有边构成有边构成G G的一棵最小生成的一棵最小生成树。
46、树。 例如例如，对于右图中的带权图，对于右图中的带权图，按，按PrimPrim算法算法选取边的过程选取边的过程如下页图所示。如下页图所示。2022-6-45010.7 最小生成树最小生成树Prim算法算法University of Science and Technology of China2022-6-45110.7 最小生成树最小生成树Prim算法算法)lg()lglg(VEOVEVVOp Prim算法：参见教材P351p时间复杂度：University of Science and Technology of Chinap 基本思想：基本思想： 首先将首先将G G的的n n个顶点看成个
47、顶点看成n n个孤立的连通分支。将所有的边按个孤立的连通分支。将所有的边按权从小到大排序。然后从第一条边开始，权从小到大排序。然后从第一条边开始，依边权递增的顺序查看依边权递增的顺序查看每一条边每一条边，并按下述方法连接，并按下述方法连接2 2个不同的连通分支：个不同的连通分支： 当查看到第当查看到第k k条边条边( (v,wv,w) )时，如果端点时，如果端点v v和和w w分别是当前分别是当前2 2个不同的个不同的连通分支连通分支T1T1和和T2T2中的顶点时，就用边中的顶点时，就用边( (v,wv,w) )将将T1T1和和T2T2连接成一个连接成一个连通分支，然后继续查看第连通分支，然后
48、继续查看第k+1k+1条边；条边； 如果端点如果端点v v和和w w在当前的同一个连通分支中，就直接再查看第在当前的同一个连通分支中，就直接再查看第k+1k+1条边。这个过程一直进行到只剩下一个连通分支时为止。条边。这个过程一直进行到只剩下一个连通分支时为止。2022-6-45210.7 最小生成树最小生成树Kruskal算法算法University of Science and Technology of Chinap 例如，例如，对前面的连通带权图，按对前面的连通带权图，按KruskalKruskal算法顺序得到的最小生算法顺序得到的最小生成树上的边如下图所示。成树上的边如下图所示。202
49、2-6-45310.7 最小生成树最小生成树Kruskal算法算法University of Science and Technology of Chinap 实现细节：实现细节： 关于关于集合的一些基本运算集合的一些基本运算可用于实现可用于实现KruskalKruskal算法。按权的递算法。按权的递增顺序查看等价于对增顺序查看等价于对优先队列优先队列执行执行removeMinremoveMin运算。可以用运算。可以用堆堆实实现这个优先队列。现这个优先队列。 对一个由连通分支组成的集合不断进行修改对一个由连通分支组成的集合不断进行修改，需要用到抽象数据类型，需要用到抽象数据类型并查集并查集Un
50、ionFindUnionFind所支持的基本运算。所支持的基本运算。p KruskalKruskal算法算法：参见教材参见教材P348P348p 时间复杂度：时间复杂度： 当当 时，时，KruskalKruskal算法比算法比PrimPrim算法差；算法差； 当当 时，时，KruskalKruskal算法却比算法却比PrimPrim算法好得多。算法好得多。2022-6-45410.7 最小生成树最小生成树Kruskal算法算法)log(EEO2|VE 2|VE University of Science and Technology of China谢谢！谢谢！2022-6-455Q & A
