初衷：

最近在看算法相關(guān)的東西，看到貪心法解決mst的問題，可惜樹上講解的不是很清新，到網(wǎng)上找了很多資料講解的也不透徹

只是隨便帶過就草草了事、這幾天抽空看了下，總算基本思路理清楚了

主要還是得感謝強(qiáng)大的google，幫我找到一個(gè)很好的英文資料。（下面有鏈接，有興趣的同學(xué)可以看看）

理順了思路，就和大家分享下~希望對(duì)學(xué)習(xí)貪心法的同學(xué)會(huì)有所幫助。

 

這篇博客的主要內(nèi)容是貪心法求解Minimum Spanning Tree (MST)（最小生成樹）的問題

貪心法求解最小生成樹常用的有兩種算法，分別是Prim’s MST algorithm和Kruskal's MST algorithm(prim算法和kruskal算法)

這里主要說(shuō)的是kruskal算法

最小生成樹的簡(jiǎn)單定義：

給定一股無(wú)向聯(lián)通帶權(quán)圖G(V,E).E 中的每一條邊(v,w)權(quán)值位C(v,w)。如果G的子圖G'是一個(gè)包含G中所有定點(diǎn)的子圖，那么G'稱為G的生成樹，如果G'的邊的權(quán)值最小

那么G'稱為G的最小生成樹。

kruskal算法的基本思想：

1.首先將G的n個(gè)頂點(diǎn)看成n個(gè)孤立的連通分支（n個(gè)孤立點(diǎn)）并將所有的邊按權(quán)從小大排序。

2.按照邊權(quán)值遞增順序，如果加入邊后存在圈則這條邊不加，直到形成連通圖

對(duì)2的解釋：如果加入邊的兩個(gè)端點(diǎn)位于不同的連通支，那么這條邊可以順利加入而不會(huì)形成圈

本例中用到的圖：

權(quán)值遞增排序：

kruskal加邊后情況：

所以對(duì)于任意邊(u,v)要判斷這兩個(gè)點(diǎn)是不是存在于同一個(gè)連通支里。

　　如果是，則舍棄這條邊，接著判斷另一條邊

　　如果不是，則把這條邊加入到圖中，并且把u，v屬于的連通支合并

然后操作下一條邊

這個(gè)算法執(zhí)行的過程就是按照規(guī)定一個(gè)個(gè)連通支合并的過程，使最后只剩一個(gè)連通支。

What kind of data structure supports such operations?

這是一個(gè)值得思考的問題、、、逛社區(qū)的時(shí)候，有用鏈表的、二維數(shù)組的、、這里不討論這些存儲(chǔ)結(jié)構(gòu)的可行性

這里要討論的是有向樹的存儲(chǔ)

some implementation details（基本操作）

makeset(x): create a singleton set containing just x            //初始化的時(shí)候把整個(gè)圖分為n個(gè)獨(dú)立連通塊

find(x): to which set does x belong?                      　　//對(duì)于任意給定點(diǎn)x，判斷x屬于哪一個(gè)連通塊

union(x, y): merge the sets containing x and y    　　//合并兩個(gè)連通塊其中，x，y為某邊的兩個(gè)端點(diǎn)，如果通過上面的find操作屬于不同的連通塊才把他們合并

 

Algorithm（算法實(shí)現(xiàn)） ：                                   

Kruskal(G)

          makeset(u);            //初始化，讓每個(gè)點(diǎn)成為獨(dú)立的連通塊

2. X={?};                      

3. Sort the edges E by weight;             //按邊的權(quán)值大小排序

4. For all edges (u, v) ∈ E in increasing order of weight do           //對(duì)于條邊e(u,v)（權(quán)值遞增順序）判斷能否加入到圖中

       if find(u) ≠find(v) then                         //如兩個(gè)端點(diǎn)不在同一個(gè)連通塊，則合并這兩個(gè)連通塊

           add edge (u, v) to X;

           union(u, v);

下面是算法中的實(shí)現(xiàn)細(xì)節(jié)

How to store a set? （如何存儲(chǔ)連通塊）

例子;

{B, E}

      

{A, C, D, F, G, H}

對(duì)于每一個(gè)聯(lián)通塊，還有兩個(gè)需要保存的，也就是樹的根節(jié)點(diǎn)rank和樹高h(yuǎn)eight

Root: its parent pointer points to itself.

Rank: the height of subtree hanging from that node.

還有一個(gè)會(huì)用到的關(guān)系，對(duì)于樹中的點(diǎn)x，p(x)表示x的父節(jié)點(diǎn)

下面是函數(shù)實(shí)現(xiàn)

Makeset(x)

 執(zhí)行上述操作后的實(shí)例：

After makeset(A), makeset(B), …, makeset(G).（執(zhí)行makeset后）

 每個(gè)點(diǎn)成為了孤立的連通支，右上角的數(shù)字代表樹的rank

After union(A,D), union(B,E), union(C, F).（合并AD，BE，CF后）

After union(C,G), union(E,A).（合并CG，EA后）

注意看新的連通支右上角的rank有變化，合并的過程中盡量使得rank達(dá)到最小

After union(B,G).

關(guān)于Rank的幾點(diǎn)說(shuō)明：

Property 1: For any x, rank(x) < rank(P(x)).                         對(duì)于任意x，x的rank小于他的父節(jié)點(diǎn)的rank

Property 2: Any root node of rank k has at least 2^k nodes in its tree.    任何rank 為k 的連通支至少有2^k個(gè)節(jié)點(diǎn)

Property 3: If there are n elements overall, there can be at most n/2^k nodes of rank k.         如果一共有n個(gè)節(jié)點(diǎn)，那么rank 為k的連通支一共有n/2^k個(gè)

對(duì)property2的解釋：因?yàn)閡nion的原則是讓union后的樹rank最小，所以u(píng)nion后的樹至少是二叉樹，也就是說(shuō)除葉子節(jié)點(diǎn)外的節(jié)點(diǎn)至少有兩個(gè)孩子。

對(duì)property3的解釋：因?yàn)閞ank為k 的樹至少有2^k 個(gè)節(jié)點(diǎn)，所以最多有n/2^k個(gè)

算法效率分析：

Kruskal(G)

          makeset(u);            //初始化，讓每個(gè)點(diǎn)成為獨(dú)立的連通塊

2. X={?};                      

3. Sort the edges E by weight;             //按邊的權(quán)值大小排序

4. For all edges (u, v) ∈ E in increasing order of weight do           //對(duì)于條邊e(u,v)（權(quán)值遞增順序）判斷能否加入到圖中

       if find(u) ≠find(v) then                         //如兩個(gè)端點(diǎn)不在同一個(gè)連通塊，則合并這兩個(gè)連通塊

           add edge (u, v) to X;

           union(u, v);

上面的算法中

makeset():可以在常數(shù)時(shí)間內(nèi)完成

sort edges :對(duì)邊的權(quán)值進(jìn)行排序的效率O(|E|log|V|)   （排序算法的時(shí)間效率、自己google不啰嗦）

find():由給定的點(diǎn)往上查找，直到樹根為止所花時(shí)間為樹的高度即log|V|。

注意：如何確定find()執(zhí)行的次數(shù)是一個(gè)值得考慮的問題

如果從點(diǎn)的角度，是很難得到準(zhǔn)確答案的，因?yàn)槊總€(gè)對(duì)于某一個(gè)點(diǎn)，和他相連的點(diǎn)是不確定的， 即不通過的點(diǎn)情況不同，要逐一考慮豈不很麻煩

其實(shí)find()執(zhí)行的次數(shù)是和邊數(shù)緊密相連的。請(qǐng)看算法中，循環(huán)的體是依據(jù)邊的權(quán)值順序展開的。而對(duì)于每一條我們考慮的邊，都要考慮它連接的兩個(gè)點(diǎn)

所以，find()的執(zhí)行次數(shù)就是邊數(shù)的兩倍。執(zhí)行一個(gè)finad()的效率是log|V|，而union基本可在常數(shù)時(shí)間內(nèi)完成

所以

Union and Find operations: O(|E|log|V|)

 

 其實(shí)這個(gè)算法的思想很簡(jiǎn)單、每一次選最小的，如果符合條件就把它加入到我們的結(jié)果中，如果不滿足條件，則選下一個(gè)最小的

只是實(shí)現(xiàn)起來(lái)考慮的需要多一些、比如用何種數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)、判斷兩個(gè)點(diǎn)是不是屬于同一個(gè)連通支等等

可見，貪心法只是提供一種解決的基本思路，要真正解決問題還要考慮如何實(shí)現(xiàn)、這也是很關(guān)鍵的一點(diǎn)。

 

如果你看到這里，可能會(huì)發(fā)現(xiàn)這個(gè)算法的效率不是很可觀、在最后的union and find 中所用的時(shí)間和點(diǎn)的數(shù)量n有很大的關(guān)系。

如果n很大的話，就會(huì)花很多時(shí)間。

那么、這個(gè)算法的效率可以提高嗎？

答案是肯定的。用到的技術(shù)為

Amortized Analysis   平攤分析（也叫攤銷分析），這可以說(shuō)是一種很神奇的思想，先透露一下吧

對(duì)于這個(gè)問題的union and find 操作，本文中的效率為O(|E|log|V|)。Amortized Analysis后，可以讓復(fù)雜度為：O(|E|Log*n)

Log*n是個(gè)什么東西呢？當(dāng)n為宇宙中所有物質(zhì)的數(shù)量的時(shí)候，Log*n<=8

也就是讓上文中的log(n)的最大值降到8.

如何？是不是很客觀的效率提升。。。。

 有興趣的同學(xué)可以關(guān)注我的下一篇博客、會(huì)針對(duì)本文的問題詳細(xì)解釋Amortized Analysis ！！

參考資料：

http://en.wikipedia.org/wiki/Minimum_spanning_tree

http://www.cs.berkeley.edu/~vazirani/algorithms/chap5.pdf

 

如果有不對(duì)的地方、希望各位能指出。

 

本文博主原創(chuàng)如有轉(zhuǎn)載請(qǐng)注明出處http://www.rzrgm.cn/yanlingyin/

 

thanks！