計(jì)算機(jī)算法設(shè)計(jì)與分析貪心算法PPT課件

1、2022-7-61提綱一、貪心算法的基本思想二、活動(dòng)安排問題三、最優(yōu)裝載四、哈夫曼編碼五、單源最短路徑六、最小生成樹七、多機(jī)調(diào)度問題第1頁/共107頁2022-7-62提綱一、貪心算法的基本思想二、活動(dòng)安排問題三、最優(yōu)裝載四、哈夫曼編碼五、單源最短路徑六、最小生成樹七、多機(jī)調(diào)度問題第2頁/共107頁2022-7-631.1 貪心算法總體思想 貪心算法總是作出在當(dāng)前看來最好的選擇。也貪心算法總是作出在當(dāng)前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的的選擇只是在某種意義上的局部最優(yōu)局部最優(yōu)選擇。貪心選擇。貪心法在解決

2、問題的策略上目光短淺，只根據(jù)當(dāng)前已法在解決問題的策略上目光短淺，只根據(jù)當(dāng)前已有的信息就做出選擇，而且一旦做出了選擇，不有的信息就做出選擇，而且一旦做出了選擇，不管將來有什么結(jié)果，這個(gè)選擇都不會(huì)改變。管將來有什么結(jié)果，這個(gè)選擇都不會(huì)改變。 這種局部最優(yōu)選擇并不總能獲得整體最優(yōu)解這種局部最優(yōu)選擇并不總能獲得整體最優(yōu)解（Optimal Solution），），但通常能獲得近似最優(yōu)但通常能獲得近似最優(yōu)解解（Near-Optimal Solution）。）。第3頁/共107頁2022-7-641.1 貪心算法總體思想例：用貪心法求解付款問題。例：用貪心法求解付款問題。假設(shè)有面值為假設(shè)有面值為5 5元、元

3、、2 2元、元、1 1元、元、5 5角、角、2 2角、角、1 1角的貨幣，角的貨幣，需要找給顧客需要找給顧客4 4元元6 6角現(xiàn)金，為使付出的貨幣的數(shù)量最角現(xiàn)金，為使付出的貨幣的數(shù)量最少，首先選出少，首先選出1 1張面值不超過張面值不超過4 4元元6 6角的最大面值的貨幣，角的最大面值的貨幣，即即2 2元，再選出元，再選出1 1張面值不超過張面值不超過2 2元元6 6角的最大面值的貨角的最大面值的貨幣，即幣，即2 2元，再選出元，再選出1 1張面值不超過張面值不超過6 6角的最大面值的貨角的最大面值的貨幣，即幣，即5 5角，再選出角，再選出1 1張面值不超過張面值不超過1 1角的最大面值的貨角

4、的最大面值的貨幣，即幣，即1 1角，總共付出角，總共付出4 4張貨幣。張貨幣。第4頁/共107頁2022-7-65 假設(shè)有面值為假設(shè)有面值為1 1分、分、5 5分、分、1 1角角1 1分的貨分的貨幣，需要找給顧客幣，需要找給顧客1 1角角5 5分現(xiàn)金，分現(xiàn)金，仍按貪心算法如何？仍按貪心算法如何？第5頁/共107頁2022-7-661.2 貪心算法的基本要素 貪心選擇性質(zhì) 所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達(dá)到。 對(duì)于一個(gè)具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導(dǎo)致問題的整體最優(yōu)解。 最優(yōu)子結(jié)構(gòu)性質(zhì) 當(dāng)一個(gè)問題的最優(yōu)

5、解包含其子問題的最優(yōu)解時(shí)，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。第6頁/共107頁2022-7-671.3 貪心算法正確性證明方法 證明算法所求解的問題具有貪心選擇性； 證明算法所求解的問題具有最優(yōu)子結(jié)構(gòu)； 證明算法確實(shí)按照貪心選擇性進(jìn)行局部優(yōu)化選擇。第7頁/共107頁2022-7-681.4 動(dòng)態(tài)規(guī)劃與貪心算法的比較 相同點(diǎn)： 都具有最優(yōu)子結(jié)構(gòu)性質(zhì)。 不同點(diǎn)： 貪心算法具有貪心選擇性質(zhì)； 動(dòng)態(tài)規(guī)劃算法具有子問題重疊性，子問題空間??； 動(dòng)態(tài)規(guī)劃算法通常以自底向上的方式解各子問題； 貪心算法則通常以自頂向下的方式進(jìn)行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。 可

6、用貪心算法時(shí)，動(dòng)態(tài)規(guī)劃方法可能不適用； 可用動(dòng)態(tài)規(guī)劃方法時(shí)，貪心算法可能不適用。第8頁/共107頁2022-7-691.5 0-1背包問題和背包問題 0-1背包問題： 給定n種物品和一個(gè)背包。物品i的重量是Wi，價(jià)值為Vi，背包容量為C。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大? 在選擇裝入背包的物品時(shí)，對(duì)每種物品i只有2種選擇，即裝入或不裝入。 背包問題： 與0-1背包問題類似，所不同的是在選擇物品i裝入背包時(shí)，可以選擇物品i i的一部分，而不一定要全部裝入背包，1in。第9頁/共107頁2022-7-6101.5 0-1背包問題和背包問題0-1背包問題的定義：背包問題定義：

7、niiixv1max這2類問題都具有最優(yōu)子結(jié)構(gòu)性質(zhì)，極為相似，但背包問題可以用貪心算法求解，而0-1背包問題卻不能用貪心算法求解。 niiixv1max nixCxwiniii11 , 01)1 (101nixCxwiniii第10頁/共107頁2022-7-6111.5 0-1背包問題和背包問題第11頁/共107頁2022-7-612 首先計(jì)算每種物品單位重量的價(jià)值首先計(jì)算每種物品單位重量的價(jià)值Vi/WiVi/Wi，然后，依，然后，依貪心選擇策略，將盡可能多的貪心選擇策略，將盡可能多的單位重量價(jià)值最高單位重量價(jià)值最高的物品裝的物品裝入背包。若將這種物品全部裝入背包后，背包內(nèi)的物品總?cè)氡嘲?。?/p>

8、將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超過重量未超過C C，則選擇單位重量價(jià)值次高的物品并盡可能，則選擇單位重量價(jià)值次高的物品并盡可能多地裝入背包。依此策略一直地進(jìn)行下去，直到背包裝滿多地裝入背包。依此策略一直地進(jìn)行下去，直到背包裝滿為止。為止。 具體算法可描述如下頁：具體算法可描述如下頁：用貪心算法解背包問題的基本步驟：第12頁/共107頁2022-7-613void 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=

9、1;ic) break; xi=1; c-=wi; if (i=n) xi=c/wi; 算法算法knapsackknapsack的主要計(jì)算時(shí)間在的主要計(jì)算時(shí)間在于將各種物品依其于將各種物品依其單位重量的價(jià)值從單位重量的價(jià)值從大到小排序。因此，大到小排序。因此，算法的計(jì)算時(shí)間上算法的計(jì)算時(shí)間上界為界為O O（nlognnlogn）。）。為了證明算法的正為了證明算法的正確性，還必須證明確性，還必須證明背包問題具有貪心背包問題具有貪心選擇性質(zhì)選擇性質(zhì)。1.5 0-1背包問題和背包問題背包問題的貪心選擇性質(zhì)證明見文獻(xiàn)王曉東，傅清祥，葉東毅，算法與數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)指導(dǎo)與習(xí)題解析，P68-70。電子工業(yè)出版社

10、，2000.第13頁/共107頁2022-7-614 對(duì)于對(duì)于0-10-1背包問題背包問題，貪心選擇之所以不能得到最優(yōu)，貪心選擇之所以不能得到最優(yōu)解是因?yàn)樵谶@種情況下，它無法保證最終能將背包裝解是因?yàn)樵谶@種情況下，它無法保證最終能將背包裝滿，部分閑置的背包空間使每公斤背包空間的價(jià)值降滿，部分閑置的背包空間使每公斤背包空間的價(jià)值降低了。事實(shí)上，在考慮低了。事實(shí)上，在考慮0-10-1背包問題時(shí)，應(yīng)比較選擇該背包問題時(shí)，應(yīng)比較選擇該物品和不選擇該物品所導(dǎo)致的最終方案，然后再作出物品和不選擇該物品所導(dǎo)致的最終方案，然后再作出最好選擇。由此就導(dǎo)出許多互相重疊的子問題。這正最好選擇。由此就導(dǎo)出許多互相重疊

11、的子問題。這正是該問題可用是該問題可用動(dòng)態(tài)規(guī)劃算法動(dòng)態(tài)規(guī)劃算法求解的另一重要特征。求解的另一重要特征。實(shí)際上也是如此，動(dòng)態(tài)規(guī)劃算法的確可以有效地實(shí)際上也是如此，動(dòng)態(tài)規(guī)劃算法的確可以有效地解解0-10-1背包問題。背包問題。 第14頁/共107頁2022-7-6151.6 貪心算法的步驟 優(yōu)化解的結(jié)構(gòu)分析 算法設(shè)計(jì) 算法復(fù)雜性分析 算法正確性證明第15頁/共107頁2022-7-616提綱一、貪心算法的基本思想二、活動(dòng)安排問題三、最優(yōu)裝載四、哈夫曼編碼五、單源最短路徑六、最小生成樹七、多機(jī)調(diào)度問題第16頁/共107頁2022-7-6172.1 問題定義（ An activity-arrangin

12、g problem ） 活動(dòng) 相容活動(dòng)i和j不相容第17頁/共107頁2022-7-6182.1 問題定義 問題定義： 輸入輸入：E=1, 2, , n，s=si ，f=fi ，n i 1 輸出輸出：E的最大相容集合的最大相容集合第18頁/共107頁2022-7-6192.2 貪心選擇 由于活動(dòng)占用資源的時(shí)間沒有限制，因此，后一種貪心選由于活動(dòng)占用資源的時(shí)間沒有限制，因此，后一種貪心選擇更為合理。擇更為合理。 貪心法求解活動(dòng)安排問題的關(guān)鍵是如何選擇貪心策略，使貪心法求解活動(dòng)安排問題的關(guān)鍵是如何選擇貪心策略，使得按照一定的順序選擇相容活動(dòng)，并能安排盡量多的活動(dòng)。至得按照一定的順序選擇相容活動(dòng)，并

13、能安排盡量多的活動(dòng)。至少有兩種看似合理的貪心策略：少有兩種看似合理的貪心策略： （1 1）最早開始最早開始時(shí)間：可以增大資源的利用率。時(shí)間：可以增大資源的利用率。 （2 2）最早結(jié)束最早結(jié)束時(shí)間：可以使下一個(gè)活動(dòng)盡早開始。時(shí)間：可以使下一個(gè)活動(dòng)盡早開始。 貪心思想貪心思想: 為了選擇最多的相容活動(dòng)，每次選為了選擇最多的相容活動(dòng)，每次選fi最最小的活動(dòng)，使我們能夠選更多的活動(dòng)。小的活動(dòng)，使我們能夠選更多的活動(dòng)。第19頁/共107頁2022-7-620貪心算法將所有活動(dòng)按結(jié)束時(shí)間排序，得到活動(dòng)集合E=e1,e2en；先將e1選入結(jié)果集合A中，即A=e1；依次掃描每一個(gè)活動(dòng)ei：如果ei的開始時(shí)間晚

14、于最后一個(gè)選入A的活動(dòng)ej的結(jié)束時(shí)間，則將ei選入A中，否則放棄ei；第20頁/共107頁2022-7-621貪心算法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; 各活動(dòng)的起始時(shí)間和結(jié)各活動(dòng)的起始時(shí)間和結(jié)束時(shí)間存儲(chǔ)于數(shù)組束時(shí)間存儲(chǔ)于數(shù)組s s和和f f中且按結(jié)束時(shí)間的非減中且按結(jié)束時(shí)間的非減序排列序排列 第21頁/共107頁2022-7-622貪心算法isifi1142353064575386

15、59761088119812102131112140 1 2 3 4 5 6 7 8 9 10 11 12 13 14131214678910148114活動(dòng)2、活動(dòng)3與活動(dòng)1不相容活動(dòng)4與活動(dòng)1相容活動(dòng)5、活動(dòng)6、活動(dòng)7與活動(dòng)4不相容活動(dòng)8與活動(dòng)4相容活動(dòng)9、活動(dòng)10與活動(dòng)8不相容活動(dòng)11與活動(dòng)8相容5結(jié)果：選中的任務(wù)為：結(jié)果：選中的任務(wù)為：1、4、8、11第22頁/共107頁2022-7-6232.4 算法正確性證明 需要證明： 活動(dòng)安排問題有一個(gè)最優(yōu)解以貪心選擇開始； 活動(dòng)安排問題具有最優(yōu)子結(jié)構(gòu)； 算法每一步按照貪心選擇計(jì)算，最終可得到原問題的一個(gè)最優(yōu)解。第23頁/共107頁2022-7

16、-624定理定理1 1說明：活動(dòng)安排問題有一個(gè)最優(yōu)說明：活動(dòng)安排問題有一個(gè)最優(yōu)解以貪心選擇開始解以貪心選擇開始第24頁/共107頁2022-7-625定理定理2 2說明：活動(dòng)安排問題具有最優(yōu)子結(jié)構(gòu)說明：活動(dòng)安排問題具有最優(yōu)子結(jié)構(gòu)第25頁/共107頁2022-7-626kiil1kiil2kiil1定理定理3 3說明：貪心選擇最終可得到活動(dòng)安排問說明：貪心選擇最終可得到活動(dòng)安排問題的一個(gè)最優(yōu)解題的一個(gè)最優(yōu)解第26頁/共107頁2022-7-627提綱一、貪心算法的基本思想二、活動(dòng)安排問題三、最優(yōu)裝載四、哈夫曼編碼五、單源最短路徑六、最小生成樹七、多機(jī)調(diào)度問題第27頁/共107頁2022-7-62

17、83.1 問題定義 有一批集裝箱要裝上一艘載重量為c的輪船。其中集裝箱i的重量為Wi。最優(yōu)裝載問題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。niix1max nixCxwiniii11 , 01第28頁/共107頁2022-7-6293.2 貪心選擇 采用重量最輕者先裝的貪心選擇策略，可產(chǎn)生最優(yōu)裝載問題的最優(yōu)解。第29頁/共107頁2022-7-6303.3 貪心算法templatevoid Loading(int x, Type w, Type c, int n) int *t = new int n+1; Sort(w, t, n); /*一維數(shù)組t按照重量從小到大存

18、儲(chǔ)集裝箱的號(hào)碼*/ for (int i = 1; i = n; i+) xi = 0; for (int i = 1; i = n & wti = c; i+) xti = 1; c -= wti;算法算法loading的主要計(jì)算量在于將集裝箱依其重量從小到的主要計(jì)算量在于將集裝箱依其重量從小到大排序，故算法所需的計(jì)算時(shí)間為大排序，故算法所需的計(jì)算時(shí)間為 O(nlogn)。第30頁/共107頁2022-7-631貪心算法小結(jié)貪心算法小結(jié) 貪心算法每次選擇目前最優(yōu)的解，即通過一貪心算法每次選擇目前最優(yōu)的解，即通過一系列局部最優(yōu)來獲得整體最優(yōu)。系列局部最優(yōu)來獲得整體最優(yōu)。貪心算法只有在具

19、有貪心選擇性質(zhì)時(shí)才能保證貪心算法只有在具有貪心選擇性質(zhì)時(shí)才能保證獲得整體最優(yōu)。獲得整體最優(yōu)。證明貪心選擇性質(zhì)：證明貪心選擇性質(zhì)：第一個(gè)選擇是對(duì)的；第一個(gè)選擇是對(duì)的；在作出貪心選擇后原問題轉(zhuǎn)化為同樣的子問題；在作出貪心選擇后原問題轉(zhuǎn)化為同樣的子問題；由歸納法知問題具有貪心選擇性質(zhì)。由歸納法知問題具有貪心選擇性質(zhì)。若原問題是求帶權(quán)擬陣的最優(yōu)獨(dú)立子集問題，若原問題是求帶權(quán)擬陣的最優(yōu)獨(dú)立子集問題，則必滿足貪心選擇性質(zhì)。則必滿足貪心選擇性質(zhì)。第31頁/共107頁2022-7-632提綱一、貪心算法的基本思想二、活動(dòng)安排問題三、最優(yōu)裝載四、哈夫曼編碼五、單源最短路徑六、最小生成樹七、多機(jī)調(diào)度問題第32頁/

20、共107頁2022-7-633哈夫曼編碼哈夫曼編碼是廣泛地用于數(shù)據(jù)文件壓縮的十分是廣泛地用于數(shù)據(jù)文件壓縮的十分有效的編碼方法。其壓縮率通常在有效的編碼方法。其壓縮率通常在20%20%90%90%之之間。哈夫曼編碼算法用字符在文件中出現(xiàn)的頻間。哈夫曼編碼算法用字符在文件中出現(xiàn)的頻率表來建立一個(gè)用率表來建立一個(gè)用0 0，1 1串表示各字符的最優(yōu)表串表示各字符的最優(yōu)表示方式。示方式。 給出現(xiàn)頻率高的字符較短的編碼，出現(xiàn)給出現(xiàn)頻率高的字符較短的編碼，出現(xiàn)頻率較低的字符以較長的編碼，可以大大縮短頻率較低的字符以較長的編碼，可以大大縮短總碼長。總碼長。第33頁/共107頁2022-7-634 例如一個(gè)包含

21、100,000個(gè)字符的文件，各字符出現(xiàn)頻率不同，如下表所示。定長變碼需要300,000位，而按表中變長編碼方案，文件的總碼長為：（451+133+123+163+94+54）1000=224,000。 比用定長碼方案總碼長較少約45%。abcdef頻率(千次)4513121695定長碼000001010011100101變長碼010110011111011100第34頁/共107頁2022-7-635例如，在英文中，例如，在英文中，e e的出現(xiàn)概率很高，而的出現(xiàn)概率很高，而z z的的出現(xiàn)概率則最低。當(dāng)利用哈夫曼編碼對(duì)一篇出現(xiàn)概率則最低。當(dāng)利用哈夫曼編碼對(duì)一篇英文進(jìn)行壓縮時(shí)，英文進(jìn)行壓縮時(shí)，e

22、e極有可能用一個(gè)位極有可能用一個(gè)位(bit)(bit)來表示，而來表示，而z z則可能花去則可能花去2525個(gè)位（不是個(gè)位（不是2626）。）。用普通的表示方法時(shí)，每個(gè)英文字母均占用用普通的表示方法時(shí)，每個(gè)英文字母均占用一個(gè)字節(jié)（一個(gè)字節(jié)（bytebyte），即），即8 8個(gè)位。二者相比，個(gè)位。二者相比，e e使用了一般編碼的使用了一般編碼的1/81/8的長度，的長度，z z則使用了則使用了3 3倍倍多。倘若我們能實(shí)現(xiàn)對(duì)于英文中各個(gè)字母出多。倘若我們能實(shí)現(xiàn)對(duì)于英文中各個(gè)字母出現(xiàn)概率的較準(zhǔn)確的估算，就可以大幅度提高現(xiàn)概率的較準(zhǔn)確的估算，就可以大幅度提高無損壓縮的比例。無損壓縮的比例。 第35頁/

23、共107頁2022-7-636通訊中常需要將文字轉(zhuǎn)換成二進(jìn)制字符串電文進(jìn)行傳通訊中常需要將文字轉(zhuǎn)換成二進(jìn)制字符串電文進(jìn)行傳送。文字電文，稱為編碼。反之，收到電文后要將電文送。文字電文，稱為編碼。反之，收到電文后要將電文轉(zhuǎn)換成原來的文字，電文文字，稱為譯碼。轉(zhuǎn)換成原來的文字，電文文字，稱為譯碼。 例如：需將文字例如：需將文字“ABACCDA”ABACCDA”轉(zhuǎn)換成電文。文之中有四轉(zhuǎn)換成電文。文之中有四種字符，用種字符，用2 2位二進(jìn)制便可分辨。位二進(jìn)制便可分辨。問題的提出問題的提出 則上述文字的電文為：共則上述文字的電文為：共1414位。位。 譯碼時(shí)，只需每譯碼時(shí)，只需每2 2位一位一譯即可。譯

24、即可。 特點(diǎn)：等長等頻率編碼，譯碼容易，但電文不特點(diǎn)：等長等頻率編碼，譯碼容易，但電文不一定最短一定最短. .。 編碼方案1：第36頁/共107頁2022-7-637編碼方案2：采用不等長編碼，讓出現(xiàn)次數(shù)多的字符用短碼。采用不等長編碼，讓出現(xiàn)次數(shù)多的字符用短碼。 則則上述文字的電文為：上述文字的電文為：000011010 000011010 共共9 9位。位。 但無法譯碼，但無法譯碼，它即可譯為它即可譯為BBCCACABBCCACA，也可譯為，也可譯為AAAACCDAAAAACCDA等。等。第37頁/共107頁2022-7-638編碼方案3：采用不等長編碼，讓出現(xiàn)次數(shù)多的字符用短碼，且任采用不

25、等長編碼，讓出現(xiàn)次數(shù)多的字符用短碼，且任一編碼不能是另一編碼的前綴。一編碼不能是另一編碼的前綴。 則上述文字的電文為：則上述文字的電文為：共共1313位。位。 第38頁/共107頁2022-7-639設(shè)有設(shè)有n n種字符，每種字符出現(xiàn)的次數(shù)為種字符，每種字符出現(xiàn)的次數(shù)為Wi ,Wi ,其編碼長其編碼長度為度為Li ( i=1,2,n)Li ( i=1,2,n)，則整個(gè)電文總長度為，則整個(gè)電文總長度為 Wi Wi Li Li ，要得到最短的電文，即使得，要得到最短的電文，即使得 Wi Li Wi Li最小。也最小。也就是以字符出現(xiàn)的次數(shù)為權(quán)值，構(gòu)造一棵就是以字符出現(xiàn)的次數(shù)為權(quán)值，構(gòu)造一棵 Huf

26、fmanHuffman樹，樹，并規(guī)定左分支編碼位并規(guī)定左分支編碼位0 0，右分支編碼為，右分支編碼為1 1，則字符的編，則字符的編碼就是從根到該字符所在的葉結(jié)點(diǎn)的路徑上的分支編碼就是從根到該字符所在的葉結(jié)點(diǎn)的路徑上的分支編號(hào)序列。號(hào)序列。 用構(gòu)造用構(gòu)造HuffmanHuffman樹編出來的碼，稱為樹編出來的碼，稱為HuffmanHuffman編碼。編碼。利用哈夫曼樹可以構(gòu)造一種不等長的二進(jìn)制編碼，并且利用哈夫曼樹可以構(gòu)造一種不等長的二進(jìn)制編碼，并且構(gòu)造所得的哈夫曼編碼是一種最優(yōu)前綴編碼，即使所傳構(gòu)造所得的哈夫曼編碼是一種最優(yōu)前綴編碼，即使所傳電文的總長度最短電文的總長度最短 第39頁/共107

27、頁2022-7-640根據(jù)給定的根據(jù)給定的 n n 個(gè)權(quán)值個(gè)權(quán)值 w1, w2, , wnw1, w2, , wn，構(gòu)造，構(gòu)造 n n 棵棵二叉樹的集合二叉樹的集合 F = T1, T2, , TnF = T1, T2, , Tn， 其中每棵二叉其中每棵二叉樹中均只含一個(gè)帶權(quán)值樹中均只含一個(gè)帶權(quán)值 為為 wi wi 的根結(jié)點(diǎn)，其左、右子樹的根結(jié)點(diǎn)，其左、右子樹為空樹；為空樹； 在在 F F 中選取其根結(jié)點(diǎn)的權(quán)值為最小的兩棵二叉樹，分中選取其根結(jié)點(diǎn)的權(quán)值為最小的兩棵二叉樹，分別作為左、右子樹構(gòu)造一棵新的二叉樹，并置這棵新的別作為左、右子樹構(gòu)造一棵新的二叉樹，并置這棵新的二叉樹根結(jié)點(diǎn)的權(quán)值為其左、

28、右子樹根結(jié)點(diǎn)的權(quán)值之和；二叉樹根結(jié)點(diǎn)的權(quán)值為其左、右子樹根結(jié)點(diǎn)的權(quán)值之和； 從從F F中刪去這兩棵樹，同時(shí)加入剛生成的新樹；中刪去這兩棵樹，同時(shí)加入剛生成的新樹；重復(fù)重復(fù) (2) (2) 和和 (3) (3) 兩步，直至兩步，直至 F F 中只含一棵樹為止。中只含一棵樹為止。 哈夫曼算法哈夫曼算法第40頁/共107頁2022-7-641問題定義 二進(jìn)制字符編碼 每個(gè)字符用一個(gè)二進(jìn)制0 0、1 1串來表示。 固定長編碼 每個(gè)字符都用相同長的0 0、1 1串表示。 可變長編碼 給出現(xiàn)頻率高的字符較短的編碼，出現(xiàn)頻率較低的字符以較長的編碼，可以大大縮短總碼長。 前綴碼 對(duì)每一個(gè)字符規(guī)定一個(gè)0,10,

29、1串作為其代碼，并要求任一字符的代碼都不是其它字符代碼的前綴。這種編碼稱為前綴碼。 編碼的前綴性質(zhì)可以使譯碼方法非常簡單。第41頁/共107頁2022-7-642前綴碼 表示最優(yōu)前綴碼的二叉樹總是一棵完全二叉樹，即樹中任一結(jié)點(diǎn)都有2個(gè)兒子結(jié)點(diǎn)。 平均碼長定義為： 使平均碼長達(dá)到最小的前綴碼編碼方案稱為給定編碼字符集C的最優(yōu)前綴碼。第42頁/共107頁2022-7-643l編碼樹第43頁/共107頁2022-7-644問題定義編碼樹T的代價(jià)：設(shè)設(shè)C是字母表是字母表, , c Cf(c)是是c在文件中出現(xiàn)的頻率在文件中出現(xiàn)的頻率dT(c)是葉子是葉子c在樹在樹T中的深度，即中的深度，即c的編碼的編

30、碼長度長度T的平均碼長（代價(jià)）是編碼一個(gè)文件的的平均碼長（代價(jià)）是編碼一個(gè)文件的所有字符的平均代碼位數(shù)所有字符的平均代碼位數(shù): :使平均碼長達(dá)到最小的前綴碼編碼方案使平均碼長達(dá)到最小的前綴碼編碼方案稱為給定編碼字符集稱為給定編碼字符集C的最優(yōu)前綴碼。的最優(yōu)前綴碼。f c dcTc C( )( )第44頁/共107頁2022-7-645問題定義 最優(yōu)編碼樹問題最優(yōu)編碼樹問題第45頁/共107頁2022-7-6464.2 貪心選擇 哈夫曼提出一種構(gòu)造最優(yōu)前綴碼的貪心算法，由此產(chǎn)生的編碼方案稱為哈夫曼編碼哈夫曼編碼。第46頁/共107頁2022-7-6474.3 貪心算法第47頁/共107頁2022

31、-7-6484.3 貪心算法c:12b:13f:5e:9d:16a:4514第一步:01c:12b:13d:16a:45f:5e:914第二步:250101d:16a:45第三步:f:5e:91401c:12b:13250130a:45第四步:c:12b:132501d:16f:5e:9140130550101a:45第五步:c:12b:132501d:16f:5e:914013055010110001Huffman編碼樹算法復(fù)雜性：T(n)=O(nlogn) 第48頁/共107頁2022-7-649 第49頁/共107頁2022-7-650第50頁/共107頁2022-7-651第51頁/共

32、107頁2022-7-652在書上給出的算法在書上給出的算法huffmanTreehuffmanTree中，編碼字符集中，編碼字符集中每一字符中每一字符c c的頻率是的頻率是f(c)f(c)。以以f f為鍵值的優(yōu)先為鍵值的優(yōu)先隊(duì)列隊(duì)列Q Q用在用在貪心選擇貪心選擇時(shí)有效地確定算法當(dāng)前要合時(shí)有效地確定算法當(dāng)前要合并的并的2 2棵具有最小頻率的樹。一旦棵具有最小頻率的樹。一旦2 2棵具有最小棵具有最小頻率的樹合并后，產(chǎn)生一棵新的樹，其頻率為頻率的樹合并后，產(chǎn)生一棵新的樹，其頻率為合并的合并的2 2棵樹的頻率之和，并將新樹插入優(yōu)先隊(duì)棵樹的頻率之和，并將新樹插入優(yōu)先隊(duì)列列Q Q。經(jīng)過。經(jīng)過n n1 1

33、次的合并后，優(yōu)先隊(duì)列中只剩下次的合并后，優(yōu)先隊(duì)列中只剩下一棵樹，即所要求的樹一棵樹，即所要求的樹T T。第52頁/共107頁2022-7-653算法算法huffmanTreehuffmanTree用最小堆實(shí)現(xiàn)優(yōu)先隊(duì)列用最小堆實(shí)現(xiàn)優(yōu)先隊(duì)列Q Q。初始。初始化優(yōu)先隊(duì)列需要化優(yōu)先隊(duì)列需要O(n)O(n)計(jì)算時(shí)間，由于最小堆的計(jì)算時(shí)間，由于最小堆的DeleteMinDeleteMin和和InsertInsert運(yùn)算均需運(yùn)算均需O(logn)O(logn)時(shí)間，時(shí)間，n n1 1次的合并總共需要次的合并總共需要O(nlogn)O(nlogn)計(jì)算時(shí)間。因此，計(jì)算時(shí)間。因此，關(guān)于關(guān)于n n個(gè)字符的哈夫曼算

34、法的個(gè)字符的哈夫曼算法的計(jì)算時(shí)間計(jì)算時(shí)間為為O(nlogn)O(nlogn)第53頁/共107頁2022-7-6544.4 算法正確性分析 需要證明： 最優(yōu)前綴碼問題具有貪心選擇性質(zhì)； 最優(yōu)前綴碼問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)； 算法每一步按照貪心選擇構(gòu)造二叉樹，最終可得到前綴碼問題的一個(gè)最優(yōu)解（即生成一顆哈夫曼編碼樹）。第54頁/共107頁2022-7-6554.4 算法正確性分析定理1. 1. 設(shè)C是字母表，cC，c具有頻率f(c), x、y是C中具有最小頻率的兩個(gè)字符，則存在一個(gè)C的最優(yōu)前綴編碼樹，x與y的編碼具有相同長度，且僅在最末一位不同。定理定理1 1說明：最優(yōu)編碼問題有一個(gè)最優(yōu)解說明：最

35、優(yōu)編碼問題有一個(gè)最優(yōu)解以貪心選擇開始以貪心選擇開始第55頁/共107頁2022-7-6564.4 算法正確性分析設(shè)T是C的最優(yōu)前綴編碼樹，且b和c是具有最大深度的兩個(gè)兄弟字符:不失一般性，設(shè)f(b)f(c), f(x)f(y). 因x與y是具有最低頻率的字符, f(b)f(x), f(c)f(y).交換T的b和x,從T構(gòu)造T : 第56頁/共107頁2022-7-6574.4 算法正確性分析第57頁/共107頁2022-7-6584.4 算法正確性分析f c dcf c dcTc CTc C( )( )( )( )第58頁/共107頁2022-7-6594.4 算法正確性分析定理2. 2. 設(shè)

36、T是字母表C的最優(yōu)前綴編碼樹，cC，f(c)是c在文件中出現(xiàn)的頻率。設(shè)x、y是T中任意兩個(gè)相鄰葉結(jié)點(diǎn)，z是它們的父結(jié)點(diǎn)，則z作為頻率是f(z)=f(x)+f(y)的字符，T=T-x,y是字母表C=C-x,yz的最優(yōu)前綴編碼樹。定理定理2 2說明：最優(yōu)編碼問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)說明：最優(yōu)編碼問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)第59頁/共107頁2022-7-6604.4 算法正確性分析第60頁/共107頁2022-7-6614.4 算法正確性分析第61頁/共107頁2022-7-6624.4 算法正確性分析第62頁/共107頁2022-7-6634.4 算法正確性分析3. 3. 第63頁/共107頁2022

37、-7-664提綱一、貪心算法的基本思想二、活動(dòng)安排問題三、最優(yōu)裝載四、哈夫曼編碼五、單源最短路徑六、最小生成樹七、多機(jī)調(diào)度問題第64頁/共107頁2022-7-6655.1 問題定義 給定帶權(quán)有向圖G =(V,E)，其中每條邊的權(quán)是非負(fù)實(shí)數(shù)。另外，還給定V中的一個(gè)頂點(diǎn)，稱為源。計(jì)算從源到所有其它各頂點(diǎn)的最短路長度。路的長度是指路上各邊權(quán)之和。這個(gè)問題通常稱為單源最短路徑問題。第65頁/共107頁2022-7-666V0V1V4V2V338254122053010從V0到V4共有三條路徑： V0,V4, V0, V1, V3, V4 V0, V1, V2, V4302338第66頁/共107頁2

38、022-7-6670 1 2 3 4 01234 20 1 4 0 12 0 3 2 3 30 0 0 25 8 4 0 1 0 3 10 5 1 2 3 0 88888888888第67頁/共107頁2022-7-668貪心算法 設(shè)S是已經(jīng)對(duì)其生成了最短路徑的結(jié)點(diǎn)集合（包括v0)。 對(duì)于當(dāng)前不在S中的結(jié)點(diǎn)w，記DIST(w)是從v0開始，只經(jīng)過S中的結(jié)點(diǎn)而在w結(jié)束的那條最短路徑的長度。則有，SW第68頁/共107頁2022-7-669 如果下一條最短路徑是到結(jié)點(diǎn)u u，則這條路徑是從結(jié)點(diǎn)v v0 0出發(fā)，在u u處終止，且只經(jīng)過那些在S S中的結(jié)點(diǎn), ,即由v v0 0至u u的這條最短路徑

39、上的所有中間結(jié)點(diǎn)都是S S中的結(jié)點(diǎn)，證明如下： 設(shè)w w是這條路徑上的任意中間結(jié)點(diǎn)，則從v v0 0到u u的路徑也包含了一條從v v0 0到w w的路徑，且其長度小于從v v0 0到u u的路徑長度。 v v0 0,s,s1 1,s,s2 2,w w,s,sm-1m-1,u,u 均在S S中 根據(jù)生成規(guī)則：最短路徑是按照路徑長度的非降次序生成的，因此從v v0 0到w w的最短路徑應(yīng)該已經(jīng)生成。從而w w也應(yīng)該在S S中。 故, ,不存在不在S S中的中間結(jié)點(diǎn)。第69頁/共107頁2022-7-670 所生成的下一條路徑的終點(diǎn)所生成的下一條路徑的終點(diǎn)u u必定是所有不在必定是所有不在S S內(nèi)

40、的內(nèi)的結(jié)點(diǎn)中具有最小結(jié)點(diǎn)中具有最小DIST(u)DIST(u)值的結(jié)點(diǎn)。值的結(jié)點(diǎn)。如果選出了這樣結(jié)點(diǎn)如果選出了這樣結(jié)點(diǎn)u u并生成了從并生成了從v0v0到到u u的最短路徑之的最短路徑之后，結(jié)點(diǎn)后，結(jié)點(diǎn)u u將成為將成為S S中的一個(gè)成員。此時(shí)，那些從中的一個(gè)成員。此時(shí)，那些從v0v0出發(fā)，出發(fā)，只經(jīng)過只經(jīng)過S S中的結(jié)點(diǎn)并且在中的結(jié)點(diǎn)并且在S S外的結(jié)點(diǎn)外的結(jié)點(diǎn)w w處結(jié)束的最短路徑處結(jié)束的最短路徑長度可能會(huì)減小長度可能會(huì)減小DIST(w)DIST(w)的值變?。旱闹底冃。?這些長度發(fā)生改變的路徑，必定是一條從這些長度發(fā)生改變的路徑，必定是一條從v0v0出發(fā)，出發(fā)，經(jīng)過經(jīng)過u u然后到然后到

41、w w的更短的路徑。的更短的路徑。第70頁/共107頁2022-7-671 根據(jù)DIST(w)的定義， DIST(w)所表示的最短路徑上，所有中間結(jié)點(diǎn)都在S中；故只考慮E和 的情況 對(duì)于從v0至w，且經(jīng)過最后一個(gè)中間結(jié)點(diǎn)為u的最短路徑，有： DIST(w) = DIST(u) + c(u,w) 隨著u的加入， DIST(w)調(diào)整為 DIST(w) = min(DIST(w),DIST(u) + c(u,w)SWuv0第71頁/共107頁2022-7-672貪心選擇 其基本思想是，設(shè)置頂點(diǎn)集合S并不斷地作貪心選擇來擴(kuò)充這個(gè)集合。一個(gè)頂點(diǎn)屬于集合S當(dāng)且僅當(dāng)從源到該頂點(diǎn)的最短路徑長度已知。初始時(shí)，S

42、中僅含有源。設(shè)u是G的某一個(gè)頂點(diǎn)，把從源到u且中間只經(jīng)過S中頂點(diǎn)的路稱為從源到u的特殊路徑，并用數(shù)組dist記錄當(dāng)前每個(gè)頂點(diǎn)所對(duì)應(yīng)的最短特殊路徑長度。Dijkstra算法每次從V-S中取出具有最短特殊路長度的頂點(diǎn)u，將u添加到S中，同時(shí)對(duì)數(shù)組dist作必要的修改。一旦S包含了所有V中頂點(diǎn)，dist就記錄了從源到所有其它頂點(diǎn)之間的最短路徑長度。第72頁/共107頁2022-7-6735.3 貪心算法例如，對(duì)右圖中的有向圖，應(yīng)用Dijkstra算法計(jì)算從源頂點(diǎn)1到其它頂點(diǎn)間最短路徑的過程列在下面的表中。迭代迭代Sudist2dist3dist4dist5初始初始1-10maxint3010011,

43、2210603010021,2,441050309031,2,4,331050306041,2,4,3,5510503060第73頁/共107頁2022-7-674 ) () () (cdc fTBTCc第74頁/共107頁2022-7-675第75頁/共107頁2022-7-676第76頁/共107頁2022-7-677算法正確性證明 證明Dijkstra算法具有貪心選擇性質(zhì)； 證明Dijkstra算法具有最優(yōu)子結(jié)構(gòu)性質(zhì)； 證明Dijkstra算法確實(shí)能得到一個(gè)最優(yōu)解。第77頁/共107頁2022-7-678計(jì)算復(fù)雜性 對(duì)于具有n個(gè)頂點(diǎn)和e條邊的帶權(quán)有向圖，如果用帶權(quán)鄰接矩陣表示這個(gè)圖，那么

44、Dijkstra算法的主循環(huán)體需要O(n)時(shí)間。這個(gè)循環(huán)需要執(zhí)行n-1次，所以完成循環(huán)需要O(n2)時(shí)間。算法的其余部分所需要時(shí)間不超過O(n2)。第78頁/共107頁2022-7-679提綱一、貪心算法的基本思想二、活動(dòng)安排問題三、最優(yōu)裝載四、哈夫曼編碼五、單源最短路徑六、最小生成樹七、多機(jī)調(diào)度問題第79頁/共107頁2022-7-680煤氣管道的鋪設(shè) 某新建小區(qū)著手鋪設(shè)煤氣管道，已知每一幢樓的接入位置和距離，請(qǐng)求出最短的鋪設(shè)方案。第80頁/共107頁2022-7-681最優(yōu)布線問題最優(yōu)布線問題 學(xué)校有學(xué)校有n n臺(tái)計(jì)算機(jī)，為了方便數(shù)據(jù)傳輸，現(xiàn)臺(tái)計(jì)算機(jī)，為了方便數(shù)據(jù)傳輸，現(xiàn)要將它們用數(shù)據(jù)線連

45、接起來。兩臺(tái)計(jì)算機(jī)被連接要將它們用數(shù)據(jù)線連接起來。兩臺(tái)計(jì)算機(jī)被連接是指它們時(shí)間有數(shù)據(jù)線連接。由于計(jì)算機(jī)所處的是指它們時(shí)間有數(shù)據(jù)線連接。由于計(jì)算機(jī)所處的位置不同，因此不同的兩臺(tái)計(jì)算機(jī)的連接費(fèi)用往位置不同，因此不同的兩臺(tái)計(jì)算機(jī)的連接費(fèi)用往往是不同的。往是不同的。第81頁/共107頁2022-7-682若要在若要在n n個(gè)城市之間建設(shè)通信網(wǎng)絡(luò)，只需個(gè)城市之間建設(shè)通信網(wǎng)絡(luò)，只需要架設(shè)要架設(shè)n-1n-1條線路即可。如何以最低的經(jīng)條線路即可。如何以最低的經(jīng)濟(jì)代價(jià)建設(shè)這個(gè)通信網(wǎng)，是一個(gè)網(wǎng)的最小濟(jì)代價(jià)建設(shè)這個(gè)通信網(wǎng)，是一個(gè)網(wǎng)的最小生成樹問題。生成樹問題。第82頁/共107頁2022-7-6836.1 問題定義

46、第83頁/共107頁2022-7-6846.1 問題定義 實(shí)例：第84頁/共107頁2022-7-6856.2 貪心選擇 最小生成樹性質(zhì)： 設(shè)G=(V,E)是連通帶權(quán)圖，U是V的真子集。如果(u,v)E，且uU，vV-U，且在所有這樣的邊中，(u,v)的權(quán)cuv最小，那么一定存在G的一棵最小生成樹，它以(u,v)為其中一條邊。這個(gè)性質(zhì)也稱為MST性質(zhì)性質(zhì)。第85頁/共107頁2022-7-6866.2 貪心選擇最小生成樹問題至少有兩種合理的貪心策略：（1）最近頂點(diǎn)策略：任選一個(gè)頂點(diǎn)，并以此建立起生成樹，每一步的貪心選擇是簡單地把不在生成樹中的最近頂點(diǎn)添加到生成樹中。 Prim算法就應(yīng)用了這個(gè)貪

47、心策略,它使生成樹以一種自然的方式生長，即從任意頂點(diǎn)開始，每一步為這棵樹添加一個(gè)分枝，直到生成樹中包含全部頂點(diǎn)。第86頁/共107頁2022-7-6876.2 貪心選擇（2）最短邊策略：設(shè)G=(V，E)是一個(gè)無向連通網(wǎng)，令T=(U，TE)是G的最小生成樹。最短邊策略從TE=開始，每一次貪心選擇都是在邊集E中選取最短邊(u, v)，如果邊(u, v)加入集合TE中不產(chǎn)生回路，則將邊(u, v)加入邊集TE中，并將它在集合E中刪去。 Kruskal算法就應(yīng)用了這個(gè)貪心策略，它使生成樹以一種隨意的方式生長，先讓森林中的樹木隨意生長，每生長一次就將兩棵樹合并，到最后合并成一棵樹。第87頁/共107頁2

48、022-7-6886.3 Prim算法設(shè)G=(V,E)是連通帶權(quán)圖，V=1,2,n。構(gòu)造G的最小生成樹的Prim算法的基本思想基本思想是：首先置S=1，然后，只要S是V的真子集，就作如下的貪心選擇：貪心選擇：選取滿足條件iS，jV-S，且cij最小的邊，將頂點(diǎn)j添加到S中。這個(gè)過程一直進(jìn)行到S=V時(shí)為止。在這個(gè)過程中選取到的所有邊恰好構(gòu)成G的一棵最小生成樹最小生成樹第88頁/共107頁2022-7-689實(shí)例：第89頁/共107頁2022-7-690 在上述Prim算法中，還應(yīng)當(dāng)考慮如何有效如何有效地找出滿足條件地找出滿足條件i i S,jS,j V-SV-S，且權(quán)，且權(quán)cijcij最小最小的

49、邊的邊(i,j)(i,j)。實(shí)現(xiàn)這個(gè)目的的較簡單的辦法是設(shè)置2個(gè)數(shù)組closest和lowcost。 closestj表示j在S中的鄰接頂點(diǎn)； lowcostj表示j與S中的鄰接頂點(diǎn)最小的權(quán)值。 在Prim算法執(zhí)行過程中，先找出V-S中使lowcost值最小的頂點(diǎn)j，然后根據(jù)數(shù)組closest選取邊(j,closestj)，最后將j添加到S中，并對(duì)closest和lowcost作必要的修改。第90頁/共107頁2022-7-691 設(shè)圖G中頂點(diǎn)的編號(hào)為0n-1，Prim算法如下： 1. 1. 初始化兩個(gè)輔助數(shù)組初始化兩個(gè)輔助數(shù)組lowcost和和closest；2. 2. S=v; 輸出頂點(diǎn)輸

50、出頂點(diǎn)v v; / /將頂點(diǎn)將頂點(diǎn)v加入生成樹中加入生成樹中3. 3. 重復(fù)執(zhí)行下列操作重復(fù)執(zhí)行下列操作n-1次次 3.1 3.1 在在lowcost中選取最短邊，取中選取最短邊，取closest中對(duì)應(yīng)的頂點(diǎn)序號(hào)中對(duì)應(yīng)的頂點(diǎn)序號(hào)j； 3.2 3.2 輸出頂點(diǎn)輸出頂點(diǎn)j和對(duì)應(yīng)的權(quán)值；和對(duì)應(yīng)的權(quán)值； 3.3 3.3 S=S+j； 3.4 3.4 調(diào)整數(shù)組調(diào)整數(shù)組lowcost和和closest ；第91頁/共107頁2022-7-692算法描述： Template void prim(int n,Type * c) Type lowcostmaxint; int closestmaxint； bo

51、ol smaxint; s1=true; for(int i=2;i=n;i+) lowcosti=c1i; closesti=1; si=false;初始化兩個(gè)輔助數(shù)組lowcost和closest第92頁/共107頁2022-7-693 for (int i=1;in;i+) Type min=inf; int j=1; for (int k=2;k=n;k+) if (lowcostkmin)&(!sk) min= lowcostk; j=k;coutjclosest jlowcostjend1; sj=true; / S=S+j for(int k=2;k=n;k+) if(c

52、jk lowcostk&(!sk) lowcostk= cjk; closestk=j;/在lowcost中選取最短邊，取closest中對(duì)應(yīng)的頂點(diǎn)序號(hào)j；/輸出頂點(diǎn)j和對(duì)應(yīng)的權(quán)值調(diào)整數(shù)組lowcost和closest第93頁/共107頁2022-7-694算法分析 設(shè)連通網(wǎng)中有n個(gè)頂點(diǎn)，則第一個(gè)進(jìn)行初始化的循環(huán)語句需要執(zhí)行n-1次，第二個(gè)循環(huán)共執(zhí)行n-1次，內(nèi)嵌兩個(gè)循環(huán)，其一是在長度為n的數(shù)組中求最小值，需要執(zhí)行n-1次，其二是調(diào)整輔助數(shù)組，需要執(zhí)行n-1次，所以，Prim算法的時(shí)間復(fù)雜度為O(n2)。 第94頁/共107頁2022-7-6956.4 Kruskal算法 克魯斯卡爾算

53、法的基本思想為：為使生成樹上總的權(quán)值之和達(dá)到最小，則應(yīng)使每一條邊上的權(quán)值盡可能地小，自然應(yīng)從權(quán)值最小的邊選起，直至選出 n-1 條互不構(gòu)成回路的權(quán)值最小邊為止。具體作法如下：首先構(gòu)造一個(gè)只含 n 個(gè)頂點(diǎn)的森林，然后依權(quán)值從小到大從連通網(wǎng)中選擇不使森林中產(chǎn)生回路的邊加入到森林中去，直至該森林變成一棵樹為止，這棵樹便是連通網(wǎng)的最小生成樹。 第95頁/共107頁2022-7-696 由于生成樹上不允許有回路，因此并非每一條居當(dāng)前權(quán)值最小的邊都可選，那么在算法中如何判別當(dāng)前權(quán)值最小邊的兩個(gè)頂點(diǎn)之間是否已經(jīng)連通？從生成樹的構(gòu)造過程可見，初始態(tài)為 n 個(gè)頂點(diǎn)分屬 n 棵樹，互不連通，每加入一條邊，就將兩棵

54、樹合并為一棵樹，在同一棵樹上的兩個(gè)頂點(diǎn)之間自然相連通。由此判別當(dāng)前權(quán)值最小邊是否可取只要判別它的兩個(gè)頂點(diǎn)是否在同一棵樹上即可。 第96頁/共107頁2022-7-6976.4 Kruskal算法第97頁/共107頁2022-7-6986.4 Kruskal算法 1. 1. 初始化：初始化：U=V； TE= ； 2. 2. 循環(huán)直到循環(huán)直到T中的連通分量個(gè)數(shù)為中的連通分量個(gè)數(shù)為1 2.1 2.1 在在E中尋找最短邊中尋找最短邊(u，v); 2.2 2.2 如果頂點(diǎn)如果頂點(diǎn)u、v位于位于T的兩個(gè)不同連通分量，則的兩個(gè)不同連通分量，則 2.2.1 2.2.1 將邊將邊(u，v)并入并入TE； 2.2.2 2.2.2 將這兩個(gè)連通分量合為一個(gè)；將這兩個(gè)連通分量合為一個(gè)； 2.3 2.3 E=E-(u，v)； Kruskal算法為了提高每次貪心選擇時(shí)查找最短邊的效率，可以算法為了提高每次貪心選擇時(shí)查找最短邊的效率，可以先將圖先將圖G中的邊按代價(jià)從小到大排序，則這個(gè)操作的時(shí)間復(fù)雜度中的邊按代價(jià)從小到大排序，