原文鏈接：
http://www.wutianqi.com/?p=1284
給定一個(gè)帶權(quán)的無(wú)向連通圖,如何選取一棵生成樹,使樹上所有邊上權(quán)的總和為最小,這叫最小生成樹.
求最小生成樹的算法
(1) 克魯斯卡爾算法
圖的存貯結(jié)構(gòu)采用邊集數(shù)組,且權(quán)值相等的邊在數(shù)組中排列次序可以是任意的.該方法對(duì)于邊相對(duì)比較多的不是很實(shí)用,浪費(fèi)時(shí)間.
(2) 普里姆算法
圖的存貯結(jié)構(gòu)采用鄰接矩陣.此方法是按各個(gè)頂點(diǎn)連通的步驟進(jìn)行,需要用一個(gè)頂點(diǎn)集合,開始為空集,以后將以連通的頂點(diǎn)陸續(xù)加入到集合中,全部頂點(diǎn)加入集合后就得到所需的最小生成樹 .
下面來具體講下：
克魯斯卡爾算法
方法:將圖中邊按其權(quán)值由小到大的次序順序選取,若選邊后不形成回路,則保留作為一條邊,若形成回路則除去.依次選夠(n-1)條邊,即得最小生成樹.(n為頂點(diǎn)數(shù))
第一步:由邊集數(shù)組選第一條邊
第二步:選第二條邊,即權(quán)值為2的邊
第三步:選第三條邊,即權(quán)值為3的邊
第四步:選第四條邊,即權(quán)值為4的邊
第五步:選第五條邊
普里姆算法
方法:從指定頂點(diǎn)開始將它加入集合中,然后將集合內(nèi)的頂點(diǎn)與集合外的頂點(diǎn)所構(gòu)成的所有邊中選取權(quán)值最小的一條邊作為生成樹的邊,并將集合外的那個(gè)頂點(diǎn)加入到集合中,表示該頂點(diǎn)已連通.再用集合內(nèi)的頂點(diǎn)與集合外的頂點(diǎn)構(gòu)成的邊中找最小的邊,并將相應(yīng)的頂點(diǎn)加入集合中,如此下去直到全部頂點(diǎn)都加入到集合中,即得最小生成樹.
例在下圖中從1點(diǎn)出發(fā)求出此圖的最小生成樹,并按生成樹的邊的順序?qū)㈨旤c(diǎn)與權(quán)值填入表中.
———————>先寫出其鄰接矩陣
第一步:從①開始，①進(jìn)集合，用與集合外所有頂點(diǎn)能構(gòu)成的邊中找最小權(quán)值的一條邊
①——②權(quán)6
①——③權(quán)1 -> 取①——③邊
①——④權(quán)5
第二步:③進(jìn)集合，①，③與②,④,⑤,⑥構(gòu)成的最小邊為
①——④權(quán)5
③——⑥權(quán)4 -> 取③——⑥邊
第三步:⑥進(jìn)集合，①，③,⑥與②,④,⑤構(gòu)成的各最小邊
①——②權(quán)6
③——②權(quán)5
⑥——④權(quán)2 -> 取⑥——④邊
第四步:④進(jìn)集合，①，③,⑥,④與②,⑤構(gòu)成的各最小邊
①——②權(quán)6
③——②權(quán)5 -> 取③——②邊
⑥——⑤權(quán)6
第四步:②進(jìn)集合，①，③,⑥,②,④與⑤構(gòu)成的各最小邊
②——⑤權(quán)3 -> 取②——⑤邊
這也是在網(wǎng)上找到的一個(gè)Kruskal和Prim構(gòu)造過程圖，貼出來：
這題的模版我暫時(shí)沒找到好的。我覺得這題主要還是思想，當(dāng)然，給一些題目來練習(xí)是必不可少的。
HDOJ 1233 還是暢通工程
HDOJ 1863 暢通工程
HDOJ 1879 繼續(xù)暢通工程
http://www.wutianqi.com/?p=1286
HDOJ 1102 Constructing Roads
http://www.wutianqi.com/?p=1313
HDOJ 1875 暢通工程再續(xù)
http://www.wutianqi.com/?p=1300