算法分析第4章

1、1 第4章 貪心算法 2 學(xué)習(xí)要點(diǎn)學(xué)習(xí)要點(diǎn) 理解貪心算法的概念。 掌握貪心算法的基本要素 （1）最優(yōu)子結(jié)構(gòu)性質(zhì) （2）貪心選擇性質(zhì) 理解貪心算法與動(dòng)態(tài)規(guī)劃算法的差異 理解貪心算法的一般理論 通過(guò)應(yīng)用范例學(xué)習(xí)貪心設(shè)計(jì)策略。 （1）活動(dòng)安排問(wèn)題；（2）最優(yōu)裝載問(wèn)題；（3）哈夫曼編碼； （4）單源最短路徑；（5）最小生成樹(shù)；（6）多機(jī)調(diào)度問(wèn)題。 3 顧名思義，貪心算法總是作出在當(dāng)前看來(lái)最好的選擇。 也就是說(shuō)貪心算法并不從整體最優(yōu)考慮，它所作出的選擇 只是在某種意義上的局部最優(yōu)局部最優(yōu)選擇。當(dāng)然，希望貪心算法 得到的最終結(jié)果也是整體最優(yōu)的。雖然貪心算法不能對(duì)所 有問(wèn)題都得到整體最優(yōu)解，但對(duì)許多問(wèn)題它能

2、產(chǎn)生整體最 優(yōu)解。如單源最短路經(jīng)問(wèn)題，最小生成樹(shù)問(wèn)題等。在一些 情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果 卻是最優(yōu)解的很好近似。 4 4.1 活動(dòng)安排問(wèn)題 活動(dòng)安排問(wèn)題就是要在所給的活動(dòng)集合中選出最 大的相容活動(dòng)子集合，是可以用貪心算法有效求解的 很好例子。該問(wèn)題要求高效地安排一系列爭(zhēng)用某一公 共資源的活動(dòng)。貪心算法提供了一個(gè)簡(jiǎn)單、漂亮的方 法使得盡可能多的活動(dòng)能兼容地使用公共資源。 5 4.1 活動(dòng)安排問(wèn)題 設(shè)有n個(gè)活動(dòng)的集合E=1,2,n，其中每個(gè)活動(dòng)都 要求使用同一資源，如演講會(huì)場(chǎng)等，而在同一時(shí)間內(nèi)只有 一個(gè)活動(dòng)能使用這一資源。每個(gè)活動(dòng)i都有一個(gè)要求使用 該資源的起始時(shí)間si和

3、一個(gè)結(jié)束時(shí)間fi,且si fi 。如果 選擇了活動(dòng)i，則它在半開(kāi)時(shí)間區(qū)間si, fi)內(nèi)占用資源。 若區(qū)間si, fi)與區(qū)間sj, fj)不相交，則稱(chēng)活動(dòng)i與活 動(dòng)j是相容的。也就是說(shuō)，當(dāng)sifj或sjfi時(shí)，活動(dòng)i與 活動(dòng)j相容。 6 4.1 活動(dòng)安排問(wèn)題 ntemplate nvoid GreedySelector(int n, Type s, Type f, bool A) n n A1=true; n int j=1; n for (int i=2;i=fj) Ai=true; j=i; n else Ai=false; n n 下面給出解活動(dòng)安排問(wèn)題的貪心算法GreedySelec

4、torGreedySelector : 各活動(dòng)的起始時(shí)間和結(jié)各活動(dòng)的起始時(shí)間和結(jié) 束時(shí)間存儲(chǔ)于數(shù)組束時(shí)間存儲(chǔ)于數(shù)組s s和和f f 中且按結(jié)束時(shí)間的非減中且按結(jié)束時(shí)間的非減 序排列序排列 7 4.1 活動(dòng)安排問(wèn)題 由于輸入的活動(dòng)以其完成時(shí)間的非減序非減序排列， 所以算法greedySelectorgreedySelector每次總是選擇具有最早具有最早 完成時(shí)間完成時(shí)間的相容活動(dòng)加入集合A中。直觀上，按這 種方法選擇相容活動(dòng)為未安排活動(dòng)留下盡可能多 的時(shí)間。也就是說(shuō)，該算法的貪心選擇的意義是 使剩余的可安排時(shí)間段極大化使剩余的可安排時(shí)間段極大化，以便安排盡可能 多的相容活動(dòng)。 算法greedy

5、SelectorgreedySelector的效率極高。當(dāng)輸入的 活動(dòng)已按結(jié)束時(shí)間的非減序排列，算法只需O(nO(n) ) 的時(shí)間安排n個(gè)活動(dòng)，使最多的活動(dòng)能相容地使用 公共資源。如果所給出的活動(dòng)未按非減序排列， 可以用O(nlognO(nlogn) )的時(shí)間重排。 8 4.1 活動(dòng)安排問(wèn)題 例：例：設(shè)待安排的11個(gè)活動(dòng)的開(kāi)始時(shí)間和結(jié)束時(shí)間按結(jié) 束時(shí)間的非減序排列如下： i1234567891 0 1 1 Si130535688212 fi45678910 11 12 13 14 9 4.1 活動(dòng)安排問(wèn)題 算法算法greedySelectorgreedySelector 的計(jì)算過(guò)程的計(jì)算過(guò)程如

6、左圖所示。 圖中每行相應(yīng)于算法的 一次迭代。陰影長(zhǎng)條表 示的活動(dòng)是已選入集合 A的活動(dòng)，而空白長(zhǎng)條 表示的活動(dòng)是當(dāng)前正在 檢查相容性的活動(dòng)。 10 4.1 活動(dòng)安排問(wèn)題 若被檢查的活動(dòng)i的開(kāi)始時(shí)間Si小于最近選擇的活 動(dòng)j的結(jié)束時(shí)間fi，則不選擇活動(dòng)i，否則選擇活動(dòng)i加 入集合A中。 貪心算法并不總能求得問(wèn)題的整體最優(yōu)解整體最優(yōu)解。但對(duì) 于活動(dòng)安排問(wèn)題，貪心算法greedySelector卻總能求 得的整體最優(yōu)解，即它最終所確定的相容活動(dòng)集合A的 規(guī)模最大。這個(gè)結(jié)論可以用數(shù)學(xué)歸納法證明。 11 4.2 貪心算法的基本要素 本節(jié)著重討論可以用貪心算法求解的問(wèn)題的一般 特征。 對(duì)于一個(gè)具體的問(wèn)題，

7、怎么知道是否可用貪心算 法解此問(wèn)題，以及能否得到問(wèn)題的最優(yōu)解呢?這個(gè)問(wèn)題 很難給予肯定的回答。 但是，從許多可以用貪心算法求解的問(wèn)題中看到 這類(lèi)問(wèn)題一般具有2個(gè)重要的性質(zhì)：貪心選擇性質(zhì)貪心選擇性質(zhì)和最最 優(yōu)子結(jié)構(gòu)性質(zhì)優(yōu)子結(jié)構(gòu)性質(zhì)。 12 4.2 貪心算法的基本要素 1 1、貪心選擇性質(zhì)、貪心選擇性質(zhì) 所謂貪心選擇性質(zhì)貪心選擇性質(zhì)是指所求問(wèn)題的整體最優(yōu)解整體最優(yōu)解可以 通過(guò)一系列局部最優(yōu)局部最優(yōu)的選擇，即貪心選擇來(lái)達(dá)到。這是 貪心算法可行的第一個(gè)基本要素，也是貪心算法與動(dòng)態(tài) 規(guī)劃算法的主要區(qū)別。 動(dòng)態(tài)規(guī)劃算法通常以自底向上自底向上的方式解各子問(wèn)題， 而貪心算法則通常以自頂向下自頂向下的方式進(jìn)行，

8、以迭代的方 式作出相繼的貪心選擇，每作一次貪心選擇就將所求問(wèn) 題簡(jiǎn)化為規(guī)模更小的子問(wèn)題。 對(duì)于一個(gè)具體問(wèn)題，要確定它是否具有貪心選擇性 質(zhì)，必須證明每一步所作的貪心選擇最終導(dǎo)致問(wèn)題的整 體最優(yōu)解。 13 4.2 貪心算法的基本要素 當(dāng)一個(gè)問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解時(shí)， 稱(chēng)此問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)。問(wèn)題的最優(yōu)子結(jié)構(gòu)性 質(zhì)是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵 特征。 2 2、最優(yōu)子結(jié)構(gòu)性質(zhì)、最優(yōu)子結(jié)構(gòu)性質(zhì) 14 4.2 貪心算法的基本要素 貪心算法和動(dòng)態(tài)規(guī)劃算法都要求問(wèn)題具有最優(yōu)子 結(jié)構(gòu)性質(zhì)，這是2類(lèi)算法的一個(gè)共同點(diǎn)。但是，對(duì)于具 有最優(yōu)子結(jié)構(gòu)最優(yōu)子結(jié)構(gòu)的問(wèn)題應(yīng)該選用貪

9、心算法還是動(dòng)態(tài)規(guī)劃 算法求解?是否能用動(dòng)態(tài)規(guī)劃算法求解的問(wèn)題也能用貪 心算法求解?下面研究2個(gè)經(jīng)典的組合優(yōu)化問(wèn)題組合優(yōu)化問(wèn)題，并以 此說(shuō)明貪心算法與動(dòng)態(tài)規(guī)劃算法的主要差別。 3、貪心算法與動(dòng)態(tài)規(guī)劃算法的差異 15 4.2 貪心算法的基本要素 n0-10-1背包問(wèn)題背包問(wèn)題： 給定n種物品和一個(gè)背包。物品i的重量是Wi，其 價(jià)值為Vi，背包的容量為C。應(yīng)如何選擇裝入背包的物 品，使得裝入背包中物品的總價(jià)值最大? 在選擇裝入背包的物品時(shí)，對(duì)每種物品在選擇裝入背包的物品時(shí)，對(duì)每種物品i i只有只有2 2種選擇，即裝種選擇，即裝 入背包或不裝入背包。不能將物品入背包或不裝入背包。不能將物品i i裝入背

10、包多次，也不能只裝裝入背包多次，也不能只裝 入部分的物品入部分的物品i i。 16 4.2 貪心算法的基本要素 n背包問(wèn)題：背包問(wèn)題： 與0-1背包問(wèn)題類(lèi)似，所不同的是在選擇物品i裝 入背包時(shí)，可以選擇物品可以選擇物品i i的一部分的一部分，而不一定要全部 裝入背包，1in。 這2類(lèi)問(wèn)題都具有最優(yōu)子結(jié)構(gòu)最優(yōu)子結(jié)構(gòu)性質(zhì)，極為相似，但 背包問(wèn)題可以用貪心算法求解，而0-1背包問(wèn)題卻不能 用貪心算法求解。 17 4.2 貪心算法的基本要素 首先計(jì)算每種物品單位重量的價(jià)值Vi/Wi，然后，依貪心 選擇策略，將盡可能多的單位重量?jī)r(jià)值最高單位重量?jī)r(jià)值最高的物品裝入背包。 若將這種物品全部裝入背包后，背包內(nèi)

11、的物品總重量未超過(guò) C，則選擇單位重量?jī)r(jià)值次高的物品并盡可能多地裝入背包。 依此策略一直地進(jìn)行下去，直到背包裝滿(mǎn)為止。 具體算法可描述如下頁(yè)： 用貪心算法解背包問(wèn)題的基本步驟： 18 4.2 貪心算法的基本要素 nvoid Knapsack(int n,float M,float v,float w,float x) n n Sort(n,v,w); n int i; n for (i=1;i=n;i+) xi=0; n float c=M; n for (i=1;ic) break; n xi=1; n c-=wi; n n if (i=n) xi=c/wi; n 算法算法knapsackk

12、napsack的的 主要計(jì)算時(shí)間在于將主要計(jì)算時(shí)間在于將 各種物品依其單位重各種物品依其單位重 量的價(jià)值從大到小排量的價(jià)值從大到小排 序。因此，算法的計(jì)序。因此，算法的計(jì) 算時(shí)間上界為算時(shí)間上界為 O O（nlognnlogn）。）。 為了證明算法的正確為了證明算法的正確 性，還必須證明背包性，還必須證明背包 問(wèn)題具有貪心選擇性問(wèn)題具有貪心選擇性 質(zhì)質(zhì)。 19 4.2 貪心算法的基本要素 對(duì)于0-10-1背包問(wèn)題背包問(wèn)題，貪心選擇之所以不能得到最優(yōu)解 是因?yàn)樵谶@種情況下，它無(wú)法保證最終能將背包裝滿(mǎn)，部 分閑置的背包空間使每公斤背包空間的價(jià)值降低了。事實(shí) 上，在考慮0-1背包問(wèn)題時(shí)，應(yīng)比較選擇該

13、物品和不選擇 該物品所導(dǎo)致的最終方案，然后再作出最好選擇。由此就 導(dǎo)出許多互相重疊的子問(wèn)題。這正是該問(wèn)題可用動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃 算法算法求解的另一重要特征。 實(shí)際上也是如此，動(dòng)態(tài)規(guī)劃算法的確可以有效地解0- 1背包問(wèn)題。 20 4.3 最優(yōu)裝載 有一批集裝箱要裝上一艘載重量為c的輪船。其中 集裝箱i的重量為Wi。最優(yōu)裝載問(wèn)題要求確定在裝載體 積不受限制的情況下，將盡可能多的集裝箱裝上輪船。 1 1、算法描述、算法描述 最優(yōu)裝載問(wèn)題可用貪心算法求解。采用重量最輕 者先裝的貪心選擇策略，可產(chǎn)生最優(yōu)裝載問(wèn)題的最優(yōu) 解。具體算法描述如下頁(yè)。 21 4.3 最優(yōu)裝載 ntemplate nvoid Loa

14、ding(int x, Type w, Type c, int n) n n int *t = new int n+1; n Sort(w, t, n); n for (int i = 1; i = n; i+) xi = 0; n for (int i = 1; i = n i+) xti = 1; c -= wti; n 22 4.3 最優(yōu)裝載 2 2、貪心選擇性質(zhì)、貪心選擇性質(zhì) 可以證明最優(yōu)裝載問(wèn)題具有貪心選擇性質(zhì)。 3 3、最優(yōu)子結(jié)構(gòu)性質(zhì)、最優(yōu)子結(jié)構(gòu)性質(zhì) 最優(yōu)裝載問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。 由最優(yōu)裝載問(wèn)題的貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)，容 易證明算法loadingloading的正確性。

15、 算法loadingloading的主要計(jì)算量在于將集裝箱依其重量從小到 大排序，故算法所需的計(jì)算時(shí)間為 O(nlognO(nlogn) )。 23 4.4 哈夫曼編碼 哈夫曼編碼哈夫曼編碼是廣泛地用于數(shù)據(jù)文件壓縮的十分有 效的編碼方法。其壓縮率通常在20%90%之間。哈夫 曼編碼算法用字符在文件中出現(xiàn)的頻率表來(lái)建立一個(gè) 用0，1串表示各字符的最優(yōu)表示方式。 給出現(xiàn)頻率高的字符較短的編碼，出現(xiàn)頻率較低 的字符以較長(zhǎng)的編碼，可以大大縮短總碼長(zhǎng)。 1、前綴碼 對(duì)每一個(gè)字符規(guī)定一個(gè)0,1串作為其代碼，并要求 任一字符的代碼都不是其它字符代碼的前綴。這種編 碼稱(chēng)為前綴碼前綴碼。 24 4.4 哈夫曼編

16、碼 編碼的前綴性質(zhì)可以使譯碼方法非常簡(jiǎn)單。 表示最優(yōu)前綴碼最優(yōu)前綴碼的二叉樹(shù)總是一棵完全二叉樹(shù)完全二叉樹(shù)， 即樹(shù)中任一結(jié)點(diǎn)都有2個(gè)兒子結(jié)點(diǎn)。 平均碼長(zhǎng)平均碼長(zhǎng)定義為： 使平均碼長(zhǎng)達(dá)到最小的前綴碼編碼方案稱(chēng)為給定 編碼字符集C的最優(yōu)前綴碼最優(yōu)前綴碼。 )()()(cdcfTB T Cc 25 4.4 哈夫曼編碼 2 2、構(gòu)造哈夫曼編碼、構(gòu)造哈夫曼編碼 哈夫曼提出構(gòu)造最優(yōu)前綴碼的貪心算法，由此產(chǎn) 生的編碼方案稱(chēng)為哈夫曼編碼哈夫曼編碼。 哈夫曼算法以自底向上的方式構(gòu)造表示最優(yōu)前綴 碼的二叉樹(shù)T。 算法以|C|個(gè)葉結(jié)點(diǎn)開(kāi)始，執(zhí)行|C|1次的“合并” 運(yùn)算后產(chǎn)生最終所要求的樹(shù)T。 26 4.4 哈夫曼編

17、碼 在書(shū)上給出的算法huffmanTree中，編碼字符集中 每一字符c的頻率是f(c)。以以f f為鍵值的優(yōu)先隊(duì)列為鍵值的優(yōu)先隊(duì)列Q Q用在 貪心選擇貪心選擇時(shí)有效地確定算法當(dāng)前要合并的2棵具有最小 頻率的樹(shù)。一旦2棵具有最小頻率的樹(shù)合并后，產(chǎn)生一 棵新的樹(shù)，其頻率為合并的2棵樹(shù)的頻率之和，并將新 樹(shù)插入優(yōu)先隊(duì)列Q。經(jīng)過(guò)n1次的合并后，優(yōu)先隊(duì)列中 只剩下一棵樹(shù)，即所要求的樹(shù)T。 算法huffmanTree用最小堆實(shí)現(xiàn)優(yōu)先隊(duì)列Q。初始 化優(yōu)先隊(duì)列需要O(n)計(jì)算時(shí)間，由于最小堆的 removeMin和put運(yùn)算均需O(logn)時(shí)間，n1次的合并 總共需要O(nlogn)計(jì)算時(shí)間。因此，關(guān)于n個(gè)

18、字符的哈 夫曼算法的計(jì)算時(shí)間計(jì)算時(shí)間為O(nlogn) 。 27 4.4 哈夫曼編碼 3 3、哈夫曼算法的正確性、哈夫曼算法的正確性 要證明哈夫曼算法的正確性，只要證明最優(yōu)前綴 碼問(wèn)題具有貪心選擇性質(zhì)貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)。 (1)貪心選擇性質(zhì) (2)最優(yōu)子結(jié)構(gòu)性質(zhì) 28 4.5 單源最短路徑 給定帶權(quán)有向圖G =(V,E)，其中每條邊的權(quán)是非 負(fù)實(shí)數(shù)。另外，還給定V中的一個(gè)頂點(diǎn)，稱(chēng)為源源?，F(xiàn)在 要計(jì)算從源到所有其它各頂點(diǎn)的最短路長(zhǎng)度最短路長(zhǎng)度。這里路 的長(zhǎng)度是指路上各邊權(quán)之和。這個(gè)問(wèn)題通常稱(chēng)為單源單源 最短路徑問(wèn)題最短路徑問(wèn)題。 1、算法基本思想 Dijkstra算法是解

19、單源最短路徑問(wèn)題的貪心算法。 29 4.5 單源最短路徑 其基本思想基本思想是，設(shè)置頂點(diǎn)集合S并不斷地作貪心選貪心選 擇擇來(lái)擴(kuò)充這個(gè)集合。一個(gè)頂點(diǎn)屬于集合S當(dāng)且僅當(dāng)從源 到該頂點(diǎn)的最短路徑長(zhǎng)度已知。 初始時(shí)，S中僅含有源。設(shè)u是G的某一個(gè)頂點(diǎn)，把 從源到u且中間只經(jīng)過(guò)S中頂點(diǎn)的路稱(chēng)為從源到u的特殊 路徑，并用數(shù)組dist記錄當(dāng)前每個(gè)頂點(diǎn)所對(duì)應(yīng)的最短 特殊路徑長(zhǎng)度。Dijkstra算法每次從V-S中取出具有最 短特殊路長(zhǎng)度的頂點(diǎn)u，將u添加到S中，同時(shí)對(duì)數(shù)組 dist作必要的修改。一旦S包含了所有V中頂點(diǎn)，dist 就記錄了從源到所有其它頂點(diǎn)之間的最短路徑長(zhǎng)度。 30 4.5 單源最短路徑 例如

20、例如，對(duì)右圖中的 有向圖，應(yīng)用Dijkstra 算法計(jì)算從源頂點(diǎn)1到 其它頂點(diǎn)間最短路徑的 過(guò)程列在下頁(yè)的表中。 31 4.5 單源最短路徑 迭代迭代S Su udist2dist2 dist3dist3 dist4dist4 dist5dist5 初始初始1-10maxint30100 1 11,22106030100 2 21,2,4410503090 3 31,2,4,3310503060 4 41,2,4,3,5510503060 Dijkstra算法的迭代過(guò)程： 32 4.5 單源最短路徑 2、算法的正確性和計(jì)算復(fù)雜性 (1)貪心選擇性質(zhì) (2)最優(yōu)子結(jié)構(gòu)性質(zhì) (3)計(jì)算復(fù)雜性 對(duì)于

21、具有n個(gè)頂點(diǎn)和e條邊的帶權(quán)有向圖，如果用 帶權(quán)鄰接矩陣表示這個(gè)圖，那么Dijkstra算法的主循 環(huán)體需要 時(shí)間。這個(gè)循環(huán)需要執(zhí)行n-1次，所以完 成循環(huán)需要 時(shí)間。算法的其余部分所需要時(shí)間不 超過(guò) 。 )(nO )( 2 nO )( 2 nO 33 4.6 最小生成樹(shù) 設(shè)G =(V,E)是無(wú)向連通帶權(quán)圖，即一個(gè)網(wǎng)絡(luò)網(wǎng)絡(luò)。E中 每條邊(v,w)的權(quán)為cvw。如果G的子圖G是一棵 包含G的所有頂點(diǎn)的樹(shù)，則稱(chēng)G為G的生成樹(shù)。生成樹(shù) 上各邊權(quán)的總和稱(chēng)為該生成樹(shù)的耗費(fèi)耗費(fèi)。在G的所有生成 樹(shù)中，耗費(fèi)最小的生成樹(shù)稱(chēng)為G的最小生成樹(shù)最小生成樹(shù)。 網(wǎng)絡(luò)的最小生成樹(shù)在實(shí)際中有廣泛應(yīng)用。例如例如， 在設(shè)計(jì)通信網(wǎng)

22、絡(luò)時(shí)，用圖的頂點(diǎn)表示城市，用邊(v,w) 的權(quán)cvw表示建立城市v和城市w之間的通信線(xiàn)路所 需的費(fèi)用，則最小生成樹(shù)就給出了建立通信網(wǎng)絡(luò)的最 經(jīng)濟(jì)的方案。 34 4.6 最小生成樹(shù) 1、最小生成樹(shù)性質(zhì) 用貪心算法設(shè)計(jì)策略可以設(shè)計(jì)出構(gòu)造最小生成樹(shù) 的有效算法。本節(jié)介紹的構(gòu)造最小生成樹(shù)的PrimPrim算法算法 和KruskalKruskal算法算法都可以看作是應(yīng)用貪心算法設(shè)計(jì)策略的 例子。盡管這2個(gè)算法做貪心選擇的方式不同，它們都 利用了下面的最小生成樹(shù)性質(zhì)最小生成樹(shù)性質(zhì)： 設(shè)G=(V,E)是連通帶權(quán)圖，U是V的真子集。如果 (u,v)E，且uU，vV-U，且在所有這樣的邊中， (u,v)的權(quán)cu

23、v最小，那么一定存在G的一棵最小生 成樹(shù)，它以(u,v)為其中一條邊。這個(gè)性質(zhì)有時(shí)也稱(chēng)為 MSTMST性質(zhì)性質(zhì)。 35 4.6 最小生成樹(shù) 2 2、PrimPrim算法算法 設(shè)G=(V,E)是連通帶權(quán)圖，V=1,2,n。 構(gòu)造G的最小生成樹(shù)的Prim算法的基本思想基本思想是：首 先置S=1，然后，只要S是V的真子集，就作如下的貪貪 心選擇心選擇：選取滿(mǎn)足條件iS，jV-S，且cij最小 的邊，將頂點(diǎn)j添加到S中。這個(gè)過(guò)程一直進(jìn)行到S=V時(shí) 為止。 在這個(gè)過(guò)程中選取到的所有邊恰好構(gòu)成G的一棵最最 小生成樹(shù)小生成樹(shù)。 36 4.6 最小生成樹(shù) 利用最小生成樹(shù)性質(zhì) 和數(shù)學(xué)歸納法容易證明， 上述算法中

24、的邊集合邊集合T T始終始終 包含包含G G的某棵最小生成樹(shù)中的某棵最小生成樹(shù)中 的邊的邊。因此，在算法結(jié)束 時(shí)，T中的所有邊構(gòu)成G的 一棵最小生成樹(shù)。 例如例如，對(duì)于右圖中的 帶權(quán)圖，按PrimPrim算法算法選取 邊的過(guò)程如下頁(yè)圖所示。 37 4.6 最小生成樹(shù) 38 4.6 最小生成樹(shù) 在上述Prim算法中，還應(yīng)當(dāng)考慮如何有效地找出如何有效地找出 滿(mǎn)足條件滿(mǎn)足條件i i S,jS,j V V-S-S，且權(quán)，且權(quán)cijcij 最小的邊最小的邊( (i,ji,j) )。 實(shí)現(xiàn)這個(gè)目的的較簡(jiǎn)單的辦法是設(shè)置2個(gè)數(shù)組closest 和lowcost。 在Prim算法執(zhí)行過(guò)程中，先找出V-S中使lo

25、wcost 值最小的頂點(diǎn)j，然后根據(jù)數(shù)組closest選取邊 (j,closestj)，最后將j添加到S中，并對(duì)closest 和lowcost作必要的修改。 用這個(gè)辦法實(shí)現(xiàn)的Prim算法所需的計(jì)算時(shí)間計(jì)算時(shí)間為 )( 2 nO 39 4.6 最小生成樹(shù) 3 3、KruskalKruskal算法算法 Kruskal算法構(gòu)造G的最小生成樹(shù)的基本思想基本思想是， 首先將G的n個(gè)頂點(diǎn)看成n個(gè)孤立的連通分支。將所有的 邊按權(quán)從小到大排序。然后從第一條邊開(kāi)始，依邊權(quán) 遞增的順序查看每一條邊，并按下述方法連接2個(gè)不同 的連通分支：當(dāng)查看到第k條邊(v,w)時(shí)，如果端點(diǎn)v和 w分別是當(dāng)前2個(gè)不同的連通分支T1和T2中的頂點(diǎn)時(shí)， 就用邊(v,w)將T1和T2連接成一個(gè)連通分支，然后繼續(xù) 查看第k+1條邊；如果端點(diǎn)v和w在當(dāng)前的同一個(gè)連通分 支中，就直接再查看第k+1條邊。這個(gè)過(guò)程一直進(jìn)行到 只剩下一個(gè)連通分支時(shí)為止。 40 4.6 最小生成樹(shù) 例如，例如，對(duì)前面的連通帶權(quán)圖，按Kruskal算法順序得到的 最小生成樹(shù)上的