算法設計與分析 課件 許瑾晨 第六章 貪心算法

信息工程大學算法設計與分析貪心法國家級實驗教學示范中心計算機學科組規(guī)劃教材算法設計與分析Python案例詳解微課視頻版僅有動態(tài)規(guī)劃是不夠的動態(tài)規(guī)劃是對分治思想的一種改善，它在發(fā)現(xiàn)分解出來的子問題有重疊時，保存子問題的結果避免重復計算，從而提升了算法的效率。但避免重復計算并不是最高明的策略。

動態(tài)規(guī)劃的特點是在每次做選擇前，將所有可能的情況進行計算，在此基礎上選擇能夠達到最優(yōu)的選項。

本章學習的貪心算法策略：不考慮所有可能情況，只是做出當前看來是最好的選擇！引例找零錢問題原理和方法兩個重要性質最優(yōu)子結構貪心選擇貪心法正確性證明典型應用部分背包活動安排過河問題哈夫曼編碼最小生成樹多機調度信息工程大學算法設計與分析貪心法—引例—找零錢問題國家級實驗教學示范中心計算機學科組規(guī)劃教材算法設計與分析Python案例詳解微課視頻版假設要找給顧客6.3元，現(xiàn)在你手頭有面值為2.5元、1元、5角和1角的硬幣若干，試問如何找錢使得所找的硬幣總數最少？策略：優(yōu)先使用面值大的硬幣

2個2.5元的硬幣1個1元的硬幣3個1角的硬幣與其它找法相比，這種找法拿出來的硬幣個數最少。目標：找出的硬幣個數最少策略：優(yōu)先選用大面值硬幣思考：該策略總是可以得到最優(yōu)解嗎？貪心法假設要找給某顧客1.5元，現(xiàn)在你手頭有面值為1.1元、5角和1角的硬幣若干，試問如何找錢使得所找的硬幣總數最少？策略：優(yōu)先使用面值大的硬幣。

1個1.1元的硬幣

4個1角的硬幣最優(yōu)解：

3個5角的硬幣貪心策略不一定總是能夠得到最優(yōu)解！貪心策略從局部最優(yōu)出發(fā)，每次做一個選擇，問題規(guī)模就減小一些，重復該過程，直到問題解決。貪心策略不一定總是能夠得到最優(yōu)解。信息工程大學算法設計與分析貪心法—基本原理國家級實驗教學示范中心計算機學科組規(guī)劃教材算法設計與分析Python案例詳解微課視頻版求解最優(yōu)化問題的過程包含一系列步驟每一步都有多種選擇貪心法做出在當前看來最好的選擇希望通過局部最優(yōu)選擇達到全局最優(yōu)

貪心算法總是做出當前最好的選擇，不是從整體上考慮問題的最優(yōu)性，它所做出的選擇只是在某種意義上的局部最優(yōu)選擇，所以有時貪心算法的解不一定是整體最優(yōu)解。對于一個給定的問題，通常有多種貪心選擇策略，但不是每種策略都可以得到最優(yōu)解。因此，選擇能產生問題最優(yōu)解的貪心選擇策略是使用貪心法的核心問題。有些問題的貪心選擇策略比較直觀，有些問題則需要深入分析。適合用貪心法求解的問題一般具有兩個重要性質：貪心選擇性質（Greedy-choiceproperty）每步所做的貪心選擇最終可求得問題的最優(yōu)解最優(yōu)子結構性質（Optimalsubstructure）問題的最優(yōu)解包含子問題的最優(yōu)解1.證明所求解的問題具有最優(yōu)子結構性質。2.證明所求解的問題具有貪心選擇性質（證明每一步所做的貪心選擇最終導致問題的整體最優(yōu)解）。反之，只需要舉出一個反例，就可以說明貪心法不正確。貪心算法和動態(tài)規(guī)劃算法都要求問題具有最優(yōu)子結構性質，這是它們的共同點。

但對于具有最優(yōu)子結構的問題：選用貪心法還是動態(tài)規(guī)劃求解?能用動態(tài)規(guī)劃求解的問題是否也能用貪心法求解?

給定n個物品和一個背包。物品i的重量是wi，其價值為vi，背包的容量為c。應如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?物品i要么全部裝入要么不裝。0-1背包問題：與0-1背包問題不同的是，在選擇物品i裝入背包時，可以選擇物品i的一部分xi，不一定要全部裝入背包，0≤xi≤1。部分背包問題：選擇題。你覺得以下哪種貪心選擇策略可以得到部分背包問題的最優(yōu)解？A.重量輕的物品優(yōu)先裝入B.價值大的物品優(yōu)先裝入C.單位重量價值大的物品優(yōu)先裝入D.以上都不對部分背包問題的貪心選擇策略有：1.重量輕優(yōu)先2.價值大優(yōu)先3.單位重量價值大優(yōu)先反例：n=2，c=5，w=(2,5)，v=(2,10)，優(yōu)先裝入物品1，再裝入物品2的一部分，得到價值總和為8；而把物品2全部裝入背包得到價值10是最優(yōu)解。反例：n=2，c=5，w=(2,5)，v=(6,10)，優(yōu)先裝入物品2，得到價值10；而先全部裝入物品1再裝入物品2的一部分，得到價值12是最優(yōu)解。錯誤錯誤該策略綜合考慮到物品重量和價值兩個因素，可以得到最優(yōu)解。正確對物品按單位重量價值vi/wi從大到小排序；根據貪心選擇策略，將盡可能多的單位重量價值最高的物品裝入背包；若背包內的物品總重量未超過c，則選擇單位重量價值次高的物品并盡可能多地裝入背包；依此策略進行下去，直到背包裝滿為止。貪心法求解部分背包問題的步驟：貪心法求解部分背包問題的代碼：voidKnapsack(intn,floatc,float*v,float*w,float*x){knap_sort(n,v,w);/*按單位重量價值從大到小排序*/for(i=1;i<=n;i++)x[i]=0;floatleft=c;/*逐一判斷每件物品*/for(i=1;i<=n;i++){if(w[i]>left)break;x[i]=1;left-=w[i];}if(i<=n)x[i]=left/w[i];/*可能有部分裝入的物品*/}時間復雜度為O(nlogn)例：c=7,(w1,w2,w3)=(3,4,5),(v1,v2,v3)=(5,6,10)。貪心法得到的最大價值為10，裝入物品3。實際最大價值為11，裝入物品1和2。貪心法不能正確求解0-1背包問題。原因：無法保證最終能將背包裝滿，部分閑置的背包空間使背包的單位空間的價值降低。在考慮0-1背包問題時，應比較選擇該物品和不選擇該物品所導致的最終方案，然后再做出最好的選擇。由此就出現(xiàn)許多互相重疊的子問題。0-1背包問題可用動態(tài)規(guī)劃求解。貪心法不能正確求解0-1背包問題。動態(tài)規(guī)劃貪心共同點最優(yōu)子結構性質不同點重疊子問題貪心選擇性質求解思路對所有選擇比較后決定最優(yōu)的只考慮一種選擇，因而更高效解題過程通常采取自底而上，從小問題推出大問題從大問題逐步求解，不斷減少問題規(guī)模，直至結束代碼結構通常是多重循環(huán)通常是排序后一遍掃描貪心法簡單、高效。選擇正確的貪心選擇策略是關鍵。兩個重要性質：最優(yōu)子結構和貪心選擇性質。貪心算法是否產生最優(yōu)解，需嚴格證明；反之，要證明某種貪心選擇策略是錯誤的，只需要找出一個反例即可。信息工程大學算法設計與分析貪心法—活動安排問題國家級實驗教學示范中心計算機學科組規(guī)劃教材算法設計與分析Python案例詳解微課視頻版活動安排問題：

設有n個活動的集合S={1,2,…,n}，其中每個活動都要求使用同一資源，如教室、會場等，而在同一時間內只有一個活動能使用這個資源。si，fi分別為活動i的開始和結束時間，且si<fi

?；顒觟與j相容

si

fj或sjfi。求：最大的兩兩相容的活動集A。

問題的解需要滿足以下條件：是n個活動的一個子集任何兩個活動都是相容的活動個數最多活動的屬性：開始時間、結束時間、持續(xù)時間可能的貪心策略：盡早開始，優(yōu)先安排開始時間早的活動占用時間短，優(yōu)先安排持續(xù)時間短的活動使剩余時間更多，優(yōu)先安排結束時間早的活動思考：活動安排問題可以用貪心法求解嗎？選擇題。你覺得以下哪種貪心選擇策略可以得到活動安排問題的最優(yōu)解？A.優(yōu)先安排開始時間早的活動B.優(yōu)先安排持續(xù)時間短的活動C.優(yōu)先安排結束時間早的活動D.以上都不對策略1：優(yōu)先安排開始時間早的活動錯誤該策略得到的解：活動1最優(yōu)解：活動2、活動3策略2：

優(yōu)先安排持續(xù)時間短的活動錯誤該策略得到的解：活動4、5最優(yōu)解：活動1、2、3策略3：優(yōu)先安排結束時間早的活動問題：該策略對所有實例都能得到最優(yōu)解嗎？該策略對兩個實例都得到了最優(yōu)解。

時間復雜度為O(nlogn)S={1,2,…,n}是活動集，且f1

…

fn

。

定理：算法GreedySelect執(zhí)行到第k步，選擇k項活動i1=1,i2,…,ik，那么存在最優(yōu)解A包含i1=1,i2,…,ik。證明：歸納基礎：k=1,存在最優(yōu)解包含活動1。任取最優(yōu)解A,A中的活動按結束時間遞增排列。如果A的第一個活動為j，j

1,由于f1

fj，則有A′=(A

{j})

{1}，且A′也是最優(yōu)解，并含有活動1。

j…A1…A’歸納步驟：假設命題對k為真，證明對k+1也為真。算法執(zhí)行到第k步，選擇了活動i1=1,i2,…,ik，根據歸納假設存在最優(yōu)解A包含i1=1,i2,…,ik。

最優(yōu)解A中剩下的活動子集B來自集合S′={i|i

S,si

fk}，且A={i1,i2,…,ik}B。其中B是S′的最優(yōu)解。若不然,設S′的最優(yōu)解為B*,B*的活動比B多，那么B*

{1,i2,…,ik}是S的最優(yōu)解，且比A的活動多,與A的最優(yōu)性矛盾。待選集合S′1,i2,…,ik不相容活動集BAB*B={ik+1,…}?將S′看做一個子問題，根據歸納基礎，存在S′的最優(yōu)解B′含有S′中的第一個活動，即ik+1,且|B′|=|B|,于是也是原問題的最優(yōu)解.待選集合S′1,i2,…,ikBB’ik+1活動安排問題的主要特征：使用一個共享資源，安排盡可能多的活動。在日常生活中這樣的應用場景很多，比如給一個教室安排盡可能多的課程、一個會場安排盡量多的會議等。信息工程大學算法設計與分析貪心法—過河問題國家級實驗教學示范中心計算機學科組規(guī)劃教材算法設計與分析Python案例詳解微課視頻版一群人在河的右岸，想通過唯一的一根獨木橋走到河的左岸，過橋時必須借助燈光照明。獨木橋最多能承受兩個人，由于只有一盞燈，因此過橋時間等于較慢的那個人單獨過橋所需要的時間。給定N個人(2<=N<1000)人單獨過橋需要的時間，

請計算最少需要多少時間，他們才能全部到達河左岸。每個人的過河時間從小到大存儲在t[i]中，i=0~n-1。按照問題規(guī)模從小到大進行分析：當n=1,2時，直接過河；當n=3時，需要兩趟；n=3時，用時：t[0]+t[1]+t[2]1.最快的和最慢的(t[2])2.最快的返回(t[0])3.最快的和次慢的(t[1])按照問題規(guī)模從小到大進行分析：當n=1,2,3時，容易求解；當n較大時，把若干人送到對岸，再有人把燈拿回來，就可以轉換為規(guī)模更小的過河問題?；谟脮r最少的要求，選擇過河時間較快的人把燈拿回來。按照問題規(guī)模從小到大進行分析。當n=1,2,3時，容易求解；當n≥4時，將過河所需時間最多的兩個人送到河對岸，有兩種方式：方式一：用最快的逐人送用時：2*t[0]+t[n-1]+t[n-2]方式二：最慢和次慢的一起過河用時：t[0]+2*t[1]+t[n-1]1.最快的和最慢的(t[n-1])2.最快的返回(t[0])3.最快的和次慢的(t[n-2])4.最快的返回(t[0])1.最快的和次快的(t[1])2.最快的返回(t[0])3.最慢的和次慢的(t[n-1])4.次快的返回(t[1])貪心法求解過河問題的步驟：按從小到大的順序對過河時間排序，存儲到數組t中；當n>=4時，比較方式一和方式二的時間，選擇用時少的（貪心選擇策略），同時n=n-2；重復步驟2，直到人數不足4時，直接求解。sort(t,t+num);/*對過河時間從小到大排序*/voidwork(intn)/*貪心法求解n個人的過河問題*/{if(n==1){ans+=t[0];return;}if(n==2){ans+=t[1];return;}if(n==3){ans+=t[0]+t[1]+t[2];return;}if(n>=4){if((t[1]*2)>=(t[0]+t[n-2]))ans+=t[0]*2+t[n-2]+t[n-1];/*選擇方式一*/elseans+=t[1]*2+t[0]+t[n-1];

/*選擇方式二*/work(n-2);/*遞歸調用*/return;}}時間復雜度為O(nlogn)信息工程大學算法設計與分析貪心法—哈夫曼編碼國家級實驗教學示范中心計算機學科組規(guī)劃教材算法設計與分析Python案例詳解微課視頻版二進制編碼問題：

給定字符集D={d1,d2,...,dn}，字符出現(xiàn)的頻率為{w1,w2,…,wn}，要求為每個字符確定一種由0、1構成的二進制編碼方案，使得編碼后的文件長度最短。字符編碼轉換01編碼譯碼轉換字符

編碼方案：等長編碼存在的問題：字符頻率不等時，得到的編碼總長度可能不是最短的。非等長編碼潛在的問題：如00表示E，01表示T，0001表示W，收到的編碼是0001，那么這組編碼是W還是ET呢？無法區(qū)分!!原因是E的編碼和W的編碼的開始部分（前綴）相同。2.非等長編碼：采用非等長的二進制串表示。頻度高的字符采用較短的二進制串表示，頻度低的字符采用較長的二進制串表示，從而達到縮短報文總長的目的。前綴碼：任一字符的編碼都不是其它字符編碼的前綴。因此，對字符集進行不等長編碼，則要求這種不等長編碼必須是前綴碼。判斷題。等長編碼一定是前綴碼。A.正確B.錯誤

戴維?哈夫曼提出了利用二叉樹構造最優(yōu)前綴碼的方法。相應的二叉樹稱為哈夫曼樹，對應的編碼稱為哈夫曼編碼。設二叉樹具有n個帶權值的葉子結點，從根結點到各個葉子結點的路徑長度li與葉子結點權值wi的乘積的和稱為該二叉樹的帶權路徑長度(WeightedPathLength，WPL)。

WPL最小的二叉樹稱為哈夫曼樹。字符出現(xiàn)的頻率根結點到字符結點的路徑長度二進制編碼問題本質上是構造哈夫曼樹的問題。基于出現(xiàn)頻率越高的字符、編碼長度越短的貪心思想，哈夫曼提出了構造哈夫曼樹的貪心法，優(yōu)先選擇頻率低的字符，以自下而上的方式構造哈夫曼樹。哈夫曼樹的構造過程：初始時，每個結點作為一棵樹，共有n棵樹；新建一個結點v，選擇具有最低頻率的兩個根結點作為結點v的左、右孩子，形成一棵樹，v的權值為其左、右孩子的權值之和；重復步驟2，直到只剩下一棵樹為止。選擇題。已知n個葉子結點，構造哈夫曼樹需要執(zhí)行（）次合并操作（合并操作指步驟2）。A.nB.n-1C.以上都不對c:14b:15d:17a:38f:6e:101601第一步例子：a:38，b:15，c:14，d:17，f:6，e:10c:14b:15d:17a:38f:6e:10初始化c:14b:15d:17a:38f:6e:101601第二步2901c:14b:152901f:6e:101601d:1733a:3801620110001第五步c:14b:152901f:6e:101601d:1733a:38016201第四步c:14b:152901f:6e:101601d:1733a:3801第三步字符對應的編碼：f：1100e：1101d：111c：100b：101a：0c:14b:152901f:6e:101601d:1733a:3801620110001選擇題。下圖所示的哈夫曼樹，密文“010110111111001101100111”對應的明文是（）。A.abdffecdB.abbdfecdC.以上都不對Huffman(C)/*構建哈夫曼樹*/輸入：C={x1,x2,…,xn}，n,

f(xi),i=1,2,…,n輸出：C’1.復制C到C’中，初始化C’中每個字符的左、右孩子為-1；2.Q

C’;/*用字符頻率集構建小根堆*/3.for(i=1;i<=n-1;i++){4.z=Allocate-Node();/*生成新結點z加入C’中*/5.z.left=pop(Q);/*取出Q最小元為z的左兒子*/6.z.right=pop(Q);/*取出Q次小元為z的右兒子*/

7.f(z)=f(x)+f(y);8.push(Q,z);/*將z插入Q*/9.}10.returnC’;時間復雜度為O(nlogn)石子合并問題：有n堆石子排成一排，依次編號為1~n。現(xiàn)要將石子兩兩合并為一堆，并將新的一堆石子數記為本次合并的代價。計算將n堆石子合并成一堆的最小代價。

結點i的權值wi根結點到結點i的路徑長度li

*3465101518合并代價=10+15+18=43=3*1+4*3+6*3+5*2哈夫曼樹是WPL最小的二叉樹，不僅可以解決最優(yōu)前綴碼問題，還可以解決很多類似的問題。

應用：生活中，把常用的物品放在容易拿到的地方。深入理解WPL的含義是關鍵。信息工程大學算法設計與分析貪心法--哈夫曼算法的正確性證明國家級實驗教學示范中心計算機學科組規(guī)劃教材算法設計與分析Python案例詳解微課視頻版定理：Huffman算法對任意規(guī)模為n（n2）的字符集C都能得到關于C的最優(yōu)前綴碼的二叉樹。

該定理的證明需要兩個引理。則T與T’的WPL之差為其中dT(i)為i在T中的層數（i到根的距離）,引理1成立。引理1：設C是字符集，

c

C,f(c)為頻率，x,y

C,f(x),f(y)頻率最小，那么存在最優(yōu)二元前綴碼使得x,y的編碼長度相等，且僅在最后一位不同。f(x)

f(a)f(y)

f(b)a與x交換b與y交換

TT’yabxTbxyaT’證明:設T是C的最優(yōu)前綴樹，且a和b是具有最大深度的兩個兄弟字符:引理2：設T是最優(yōu)二元前綴碼所對應的二叉樹，

x,y

T,x,y是樹葉兄弟，z是x,y的父親，令T’=T

{x,y},且令z的頻率f(z)=f(x)+f(y)，T’是對應于二元前綴碼C’=(C

{x,y})

{z}的二叉樹，那么WPL(T)=WPL

(T’)+f(x)+f(y)。bczT’0011f(c)f(b)f(x)+f(y)bcxyT000111f(x)f(c)f(y)f(b)z定理：Huffman算法對任意規(guī)模為n（n2）的字符集C都能得到關于C的最優(yōu)前綴碼的二叉樹。

歸納基礎

n=2，字符集C={x1,x2}，Huffman算法得到的編碼是0和1，是最優(yōu)前綴碼。歸納步驟

假設Huffman算法對于規(guī)模為k的字符集能得到最優(yōu)前綴碼?？紤]規(guī)模為k+1的字符集C={x1,x2,...,xk+1},其中x1,x2

C是頻率最小的兩個字符。

令

C’=(C－{x1,x2})

{z}，

f(z)=f(x1)+f(x2)根據歸納假設，Huffman算法得到一棵關于字符集C’、頻率f(z)和f(xi)（i=3,4,...,k+1）的最優(yōu)前綴碼的二叉樹T’。把x1和x2作為z的兒子附加到T’上，得到樹T，那么T是關于字符集C=(C’－{z})

{x1,x2}的最優(yōu)前綴碼的二叉樹。

zT’x2x1T

zx1T*x2T*‘

z如若不然，存在更優(yōu)的樹T*。根據引理1，其最深層樹葉是x1,

x2，且WPL(T*)<WPL(T)。去掉T*中的x1和x2，根據引理2，所得二叉樹T*’滿足WPL(T*’)＝WPL(T*)－(f(x1)+f(x2))<WPL(T)－(f(x1)+f(x2))=WPL(T’)與T’是一棵關于C’的最優(yōu)前綴碼的二叉樹矛盾。

信息工程大學算法設計與分析貪心法—最小生成樹國家級實驗教學示范中心計算機學科組規(guī)劃教材算法設計與分析Python案例詳解微課視頻版最小生成樹(Minimum-costSpanningTree)：設G=(V,E)是無向連通帶權圖，即一個網絡。如果G的子圖G’是一棵包含G的所有頂點的樹，則稱G’為G的生成樹。

生成樹的性質：包含n個頂點；有且僅有(n-1)條邊；任兩點都是有路可達的。生成樹上各邊權的總和稱為該生成樹的耗費。耗費最小的生成樹稱為G的最小生成樹。1234566515366425

最小生成樹有廣泛應用。比如建立城市間的通信網絡、鄉(xiāng)村間的道路連通等問題，最小生成樹可以給出最優(yōu)的建設方案。最小生成樹問題的本質：求無向連通帶權圖的最小連通代價。判斷題。對于一個無向連通帶權圖，最小生成樹可能是不唯一的。A.不正確B.正確Prim算法和Kruskal算法都是用貪心思想構造的最小生成樹。盡管它們的貪心策略不同，但都利用了最小生成樹性質。

uv頂點集U頂點集V-UMST性質證明：（反證法）假設G的任何一棵最小生成樹中都不包含邊(u,v)。設T是G的一棵最小生成樹，但不包含邊(u,v)。由于T是樹，且是連通的，因此必有一條從u到v的路徑，且該路徑上必有一條連接兩個頂點集U和V-U的邊(u',v')，其中u'屬于U，v'屬于V-U。將邊(u,v)加入到T中，得到一個含邊(u,v)的回路。當刪除邊(u',v')時，回路被消除。由此得到另一棵生成樹T’，T’和T的區(qū)別僅在于用邊(u,v)取代了T中的邊(u’,v’)。因為(u,v)的權<=(u’,v’)的權，故T‘的權值<=T的權值。因此，T’也是G的最小生成樹，并包含邊（u,v），與假設矛盾。uu'vv'頂點集U頂點集V-U

1234566515366425123456112345614123456142123456154212345615342①②③④⑤⑥

需要的數據結構：標識頂點i是否屬于集合S：使用數組s如何有效地找出滿足條件i

S，j

V-S，且權值c[i][j]最小的邊(i,j)？

對于V-S中每個頂點j，把S到j權值最小的點i存入parent[j]，權值c[i][j]存入dist[j]，當有新的點加入S時，更新parent[j]和dist[j]。1234566515366425迭代Sjp[2]d[2]p[3]d[3]p[4]d[4]p[5]d[5]p[6]d[6]初始{1}161115—∞—∞1{1,3}335111536342{1,3,6}635116236343{1,3,6,4}435116236344{1,3,6,4,2}235116223345{1,3,6,4,2,5}3511622334Prim算法執(zhí)行過程中相關數組的變化情況（parent[j]簡寫為p[j]，dist[j]簡寫為d[j]）1234561(1)5(4)3(5)4(2)2(3)voidprim(){/*prim算法構建最小生成樹*//*初始化*/s[1]=1;s[2~n]=0;forj=2ton ifc[1][j]!=INF{parent[j]=1;dist[j]=c[j][1]；}/*循環(huán)n-1次，依次加入點和邊*/for(k=1;k<=n-1;k++){/*找出V-S中dist值最小的頂點j*/inttmin=INF;j=-1;fori=2ton if(s[i]==0)&&dist[i]<tmin){tmin=dist[i];j=i;}s[j]=1;/*將j添加到S中*//*依次判斷和j相鄰且在V-S中的點，判斷該邊權值是否更小，如果是，則修改parent和dist*/fori=2tonif(s[i]==0)&&dist[i]<c[j][i]){dist[i]=c[j][i];parent[i]=j;}}}時間復雜度：O(n2)最小生成樹性質：只要是連接兩個集合的權值最小的邊，一定在某棵最小生成樹中。Kruskal算法基本思想：1.

n個頂點看成n個孤立的連通分支，將所有的邊按權值從小到大排序；

2.依次查看每一條邊(i,j)，如果i和j分別來自不同的連通分支T1和T2時，就用邊(i,j)將T1和T2連接成一個連通分支；3.重復步驟2，直到只剩下一個連通分支時為止。1234561212345611234561534212345612312345665153664251234561423①②③④⑤⑥Kruskal算法中的關鍵步驟：邊按權值從小到大排序逐一判斷邊的兩個鄰接點是否在同一個連通分支中，如不是1）合并兩個端點所在的分支2）把邊加入最小生成樹中用并查集高效實現(xiàn)查找元素屬于哪個集合合并兩個集合Prim算法和Kruskal算法比較：共同點：根據MST性質做貪心選擇不同點：Prim算法：不斷加點，時間復雜度為O(n2)Kr