引出最小生成樹(shù)，是提到電子線路設(shè)計(jì)時(shí)，要把數(shù)個(gè)元件的引腳連接在一起，使其電位相同。使n個(gè)引腳互相連通，可以使用n-1條連接線，每條連接線連接兩個(gè)引腳。尋求連接線最少的方案，是最小生成樹(shù)的應(yīng)用。將電子線路引腳接線連接問(wèn)題模型化求解一個(gè)無(wú)向帶權(quán)連通圖的頂點(diǎn)互聯(lián)最小代價(jià)。

一個(gè)無(wú)向帶權(quán)連通圖G=(V,E)，其中V是引腳集合（頂點(diǎn)），E是每個(gè)引腳之間可能互聯(lián)的集合（邊）。圖中每一條邊（u,v）∈E，都有一個(gè)權(quán)值w=(u,v)表示連接u和v的代價(jià)（引腳間接線數(shù)目）。

從這樣一個(gè)圖中找出一個(gè)無(wú)回路的子集T?E，這個(gè)子集T連接了所有頂點(diǎn)，且其邊權(quán)值之和最小。

T無(wú)回路且連接所有頂點(diǎn)，是一個(gè)樹(shù)，成為生成樹(shù)，權(quán)值最小，即是最小生成樹(shù)。求解圖G的T子集的問(wèn)題就是最小生成樹(shù)問(wèn)題。如何從一個(gè)圖中生成一顆最小生成樹(shù)，主要有Kruskal和Prim兩個(gè)算法，時(shí)間性能都是O(ElgV)。其中Prim算法通過(guò)采用斐波那契堆可將運(yùn)行時(shí)間減少到O(E+VlogV)，適用于|V|遠(yuǎn)小于|E|的圖求解最小生成樹(shù)。

不得不說(shuō)的，兩個(gè)算法的思想核心是貪心算法。在算法的每一步中，都必須在幾種可能性中選擇一種，動(dòng)態(tài)規(guī)劃是都選擇并求解最優(yōu)子解最后組合成最優(yōu)解；而貪心算法則是選擇可能性中最佳的一種來(lái)求解最優(yōu)子解。一般來(lái)說(shuō)，貪心算法這種策略不能保證找到全局最優(yōu)解，但在最小生成樹(shù)問(wèn)題上，通過(guò)貪心策略可以獲得最小權(quán)值的生成樹(shù)是可證的。

通用最小生成樹(shù)算法：

假設(shè)已知一個(gè)無(wú)向連通圖G=(V,E)，其權(quán)值函數(shù)w:E->R，目的是找出圖G的最小生成樹(shù)。

通用最小生成樹(shù)算法采用貪心策略，在每一個(gè)步驟都形成最小生成樹(shù)的一條邊。算法維護(hù)一個(gè)邊集合A，保持循環(huán)不變式：

在每一次循環(huán)迭代之前，A是某個(gè)最小生成樹(shù)的一個(gè)子集。

在算法的每一步中，確定一條邊(u,v)，是的將它加入集合A后，仍然不違反這個(gè)循環(huán)不變式，即AU{(u,v)}仍然是某一個(gè)最小生成樹(shù)的子集，這樣的邊(u,v)為A的安全邊。安全邊加入子集A后，A仍然保持是某一個(gè)最小生成樹(shù)的子集。

這是貪心算法思想，每一步尋找可能解中最優(yōu)。那問(wèn)題就是，怎么尋找安全邊，確保加入A后使A仍然是最小生成樹(shù)的子集。

算法導(dǎo)論中給出一個(gè)識(shí)別安全邊的規(guī)則，適用于無(wú)向圖。先給出這個(gè)規(guī)則的定理。

設(shè)圖G=(V,E)是一個(gè)無(wú)向連通圖，并且在E上定義了一個(gè)具有實(shí)數(shù)值的加權(quán)函數(shù)w。設(shè)A是E的一個(gè)子集，它包含于G的某個(gè)最小生成樹(shù)中。設(shè)割(S,V-S)是G的任意一個(gè)不妨害A的割，且邊(u,v)是通過(guò)割(S,V-S)的一條輕邊，則邊(u,v)對(duì)集合A來(lái)說(shuō)是安全的。

這個(gè)定理中關(guān)鍵有三點(diǎn)，第一：將圖分為兩個(gè)子圖S和V-S，即為割(S,V-S)；第二：割(S,V-S)的邊(u,v)是輕邊，就是連接子圖S和V-S所有邊中最小權(quán)值的一條；第三：已經(jīng)在子集A的邊不能是連接割的邊，稱(chēng)之為不妨害A的割；

算法導(dǎo)論中證明識(shí)別安全邊的規(guī)則就不具體展開(kāi)，主要是構(gòu)造一個(gè)通用圖，不失為普通的情況來(lái)證明。通俗地理解就是：將圖分割成兩個(gè)子圖，兩個(gè)子圖間的聯(lián)系的邊中最小權(quán)值的就是安全邊，前提是這些邊不能是集合A中的。這里按歸納法證明下：

假設(shè)圖G=(V,E)是一個(gè)無(wú)向連通圖，

割(1,V-1)，那1個(gè)頂點(diǎn)和V-1個(gè)頂點(diǎn)兩個(gè)子圖之間最小權(quán)值的邊就是安全邊了，A集合中有1個(gè)頂點(diǎn)，無(wú)邊；

割(2,V-2)，引入第二個(gè)頂點(diǎn)時(shí)，2和V-2割之間的邊顯然不會(huì)妨害A集合，找出兩個(gè)割之間的最小權(quán)值也容易，加入安全邊，集合A有一條邊，就是(1,2)；

如此類(lèi)推，n個(gè)頂點(diǎn)加入時(shí)，割(n,V-n)中n個(gè)頂點(diǎn)之間的構(gòu)成子圖就是集合A的輕邊，就是最小生成樹(shù)。通用算法之上改良的有Kruskal和Prim算法。

Kruskal算法將集合A（最小生成樹(shù)的頂點(diǎn)集和邊集）是一個(gè)森林，加入集合A中的安全邊總是途中連接兩個(gè)不同連通分支的最小權(quán)邊。而Prim算法則將集合A形成單顆樹(shù)，加入集合A的安全邊總是連接樹(shù)與一個(gè)不在樹(shù)中的頂點(diǎn)的最小權(quán)邊。

實(shí)際，二者思想是一致，只不過(guò)通過(guò)不同的數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)，時(shí)間性能分析中還涉及到增長(zhǎng)極為緩慢的函數(shù)。Prim算法應(yīng)用二叉最小堆和斐波那契堆保存最小優(yōu)先隊(duì)列Q也有不同的性能效果。

Kruskal算法描述如下：

1）圖G=(V,E)中的每個(gè)頂點(diǎn)都是一棵樹(shù)，這樣初始有V顆樹(shù)，按照E的權(quán)值大小排序邊集。初始化最小生成樹(shù)，即集合A為空集；

2）按順序找出權(quán)限的邊集中的安全邊，如果該邊的兩個(gè)頂點(diǎn)屬于不同樹(shù)，那么可以合并兩棵樹(shù)，并把邊加入到集合A中；

3）直到所有的頂點(diǎn)都已在集合A中，其邊權(quán)值最小。

核心思想就是貪心算法的，找出森林中權(quán)值的最小的邊，然后合并該邊聯(lián)系的兩棵樹(shù)。或者從因到果的過(guò)程來(lái)看，要找出最小生成樹(shù)，我就把所有邊按順序排序，依次將最小權(quán)值的邊納入集合A中。

Prim算法描述如下：

1）集合A是一顆正在成長(zhǎng)的單棵樹(shù)，樹(shù)從任意頂點(diǎn)開(kāi)始，逐漸生成直到覆蓋所有頂點(diǎn)；

2）生成過(guò)程是將連接樹(shù)A和G-A中最小權(quán)值的邊加入A；

通俗地說(shuō)，就是從圖中的任意一個(gè)頂點(diǎn)出發(fā)，找到該頂點(diǎn)所有的邊，把最小權(quán)值的邊放入集合A中即可。實(shí)現(xiàn)該算法，要借助一個(gè)變量：最下優(yōu)先級(jí)隊(duì)列Q。Q保存所有頂點(diǎn)中與頂點(diǎn)相連的邊中的最小權(quán)值。Q二叉最小堆實(shí)現(xiàn)，時(shí)間性能和Krusal算法一樣，但若使用斐波那契堆可以改善。

兩個(gè)算法基本都是將最小權(quán)值的邊找出來(lái)，然后將安全邊的頂點(diǎn)加入集合A中，從而逐步構(gòu)成一棵正在成長(zhǎng)的最小生成樹(shù)。

這里給出平攤分析中提到的增長(zhǎng)極快函數(shù)及其增長(zhǎng)極慢的逆函數(shù)，有助于理解在時(shí)間性能分析中引入增長(zhǎng)極慢函數(shù)的意義。

增長(zhǎng)極快的函數(shù)：

10的80次方已經(jīng)是可觀察到的宇宙中估計(jì)的原子數(shù)量。

有點(diǎn)像2的64次方的故事，數(shù)學(xué)的魔力在于此，簡(jiǎn)單這樣的一個(gè)函數(shù)設(shè)計(jì)，只要k=4就已經(jīng)大到無(wú)邊，大到目今我們所認(rèn)知宇宙的數(shù)量極限。

對(duì)應(yīng)增長(zhǎng)極慢的函數(shù)，就是該函數(shù)的逆函數(shù)。對(duì)整數(shù)j≥0，定義函數(shù)A_k(j)的逆函數(shù)為：

a(j)=min{k: A_k(1)≥j}

a(j)是的函數(shù)A_k(1)至少為j的最低級(jí)別k。根據(jù)增長(zhǎng)極快函數(shù)A_k(1)的值，可知：

a(j)=0，當(dāng)0≤j≤2

a(j)=1，當(dāng)j=3

a(j)=2，當(dāng)4≤j≤7

a(j)=3，當(dāng)8≤j≤2047

a(j)=4，當(dāng)2048≤j≤A₄(1)

可見(jiàn)如此，在實(shí)際應(yīng)用中的數(shù)字一般都是只有a(j)≤4，是一個(gè)增長(zhǎng)極為緩慢的函數(shù)，變量超級(jí)無(wú)敵大，我依舊小于4。讓人不禁想起阿基米德的豪言壯語(yǔ)：給我一個(gè)支點(diǎn)，我就能支起地球。宇宙之極大又或者是極小，未可知啊。

總結(jié)

以上是生活随笔為你收集整理的算法导论之图的最小生成树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。