生成樹和最小生成樹均是在無向連通圖中進行的。
生成樹：含有連通圖的全部節點n，且含有n-1條邊。一個連通圖可以有多個生成樹。
最小生成樹：是基於帶權的無向連通圖，根據權值，按一定規則，代價最小的生成樹為最小生成樹。
找最小生成樹，經典的兩種算法，普利姆算法和克魯斯卡爾算法。
1、普利姆Prim）算法
最小生成樹是數據結構中圖的一種重要應用，它的要求是從一個帶權無向完全圖中選擇n－1條邊並使這個圖仍然連通也即得到了一棵生成樹）,同時還要考慮使樹的權最小。 為了得到最小生成樹，人們設計了很多算法，最著名的有prim算法和kruskal算法。教材中介紹了prim算法，但是講得不夠詳細，理解起來比較困難，為了幫助大家更好的理解這一算法，本文對書中的內容作了進一步的細化，希望能對大家有所幫助。
假設V是圖中頂點的集合，E是圖中邊的集合，TE為最小生成樹中的邊的集合，則prim算法通過以下步驟可以得到最小生成樹：1：初始化：U={u 0},TE={f}。此步驟設立一個只有結點u 0的結點集U和一個空的邊集TE作為最小生成樹的初始形態，在隨後的算法執行中，這個形態會不斷的發生變化，直到得到最小生成樹為止。2：在所有u∈U,v∈V－U的邊u,v）∈E中，找一條權最小的邊u 0,v 0），將此邊加進集合TE中，並將此邊的非U中頂點加入U中。此步驟的功能是在邊集E中找一條邊，要求這條邊滿足以下條件：首先邊的兩個頂點要分別在頂點集合U和V－U中，其次邊的權要最小。找到這條邊以後，把這條邊放到邊集TE中，並把這條邊上不在U中的那個頂點加入到U中。這一步驟在算法中應執行多次，每執行一次，集合TE和U都將發生變化，分別增加一條邊和一個頂點，因此，TE和U是兩個動態的集合，這一點在理解算法時要密切注意。3：如果U=V，則算法結束；否則重復步驟2。可以把本步驟看成循環終止條件。我們可以算出當U=V時，步驟2共執行了n－1次設n為圖中頂點的數目），TE中也增加了n－1條邊，這n－1條邊就是需要求出的最小生成樹的邊。2、克魯斯卡爾Kruskal）算法 求加權連通圖的最小生成樹的算法。kruskal算法每次選擇n- 1條邊，所使用的貪婪准則是：從剩下的邊中選擇一條不會產生環路的具有最小耗費的邊加入已選擇的邊的集合中。注意到所選取的邊若產生環路則不可能形成一棵生成樹。kruskal算法分e 步，其中e 是網絡中邊的數目。按耗費遞增的順序來考慮這e 條邊，每次考慮一條邊。當考慮某條邊時，若將其加入到已選邊的集合中會出現環路，則將其拋棄，否則，將它選入。克魯斯卡爾算法假設 WN=(V,{E}) 是一個含有 n 個頂點的連通網，則按照克魯斯卡爾算法構造最小生成樹的過程為：先構造一個只含 n 個頂點，而邊集為空的子圖，若將該子圖中各個頂點看成是各棵樹上的根結點，則它是一個含有 n 棵樹的一個森林。之後，從網的邊集 E 中選取一條權值最小的邊，若該條邊的兩個頂點分屬不同的樹，則將其加入子圖，也就是說，將這兩個頂點分別所在的兩棵樹合成一棵樹；反之，若該條邊的兩個頂點已落在同一棵樹上，則不可取，而應該取下一條權值最小的邊再試之。依次類推，直至森林中只有一棵樹，也即子圖中含有 n-1條邊為止。舉例：克魯斯卡爾算法(Kruskal's algorithm)是兩個經典的最小生成樹算法的較為簡單理解的一個。這裡面充分體現了貪心算法的精髓。大致的流程可以用一個圖來表示。這裡的圖的選擇借用了Wikipedia上的那個。非常清晰且直觀。首先第一步，我們有一張圖，有若干點和邊如下圖所示：
......第一步我們要做的事情就是將所有的邊的長度排序，用排序的結果作為我們選擇邊的依據。這裡再次體現了貪心算法的思想。資源排序，對局部最優的資源進行選擇。排序完成後，我們率先選擇了邊AD。這樣我們的圖就變成了
......第二步，在剩下的邊中尋找。我們找到了CE。這裡邊的權重也是5
......依次類推我們找到了6,7,7。完成之後，圖變成了這個樣子。
......下一步就是關鍵了。下面選擇那條邊呢？ BC或者EF嗎？都不是，盡管現在長度為8的邊是最小的未選擇的邊。但是他們已經連通了對於BC可以通過CE,EB來連接，類似的EF可以通過EB,BA,AD,DF來接連）。所以我們不需要選擇他們。類似的BD也已經連通了這裡上圖的連通線用紅色表示了）。最後就剩下EG和FG了。當然我們選擇了EG。最後成功的圖就是下圖：
......到這裡所有的邊點都已經連通了，一個最小生成樹構建完成。Kruskal算法的時間復雜度由排序算法決定，若采用快排則時間復雜度為O(N log N)。
本文出自 “李海川” 博客，請務必保留此出處http://lihaichuan.blog.51cto.com/498079/1293449
