圖的克魯斯卡爾演算法

『壹』 如何實現克魯斯卡爾演算法

最好結合具體題目實現，我這里有個題目，裡面有完整的代碼，慢慢理解就是了 http://blog.csdn.net/aihahaheihei/article/details/6751786
裡面還有很多，感興趣也可以看看

『貳』 數據結構中圖的克魯斯卡爾演算法的基本思想是

基本思想是：設有一個有n個頂點的連通網路N=｛V，E｝，最 初先構造一個只有n個頂點，沒有邊的非連通圖 T=｛ V，￠｝，圖中每個頂點自成一個 連通分量。當在E中選到一條具有最小權值的邊時，若該邊的兩個頂點落在不同的連通 分量上，則將此邊加人到T中；否則將此邊捨去，重新選擇一條權值最小的邊。如此重復 下去，直到所有頂點在同一個連通分量上為止。

『叄』 克魯斯卡爾時間復雜度怎麼算出來的

Kruskal演算法的時間復雜度由排序演算法決定，若採用快排則時間復雜度為O(N log N)。

kruskal演算法：

求加權連通圖的最小生成樹的演算法。kruskal演算法總共選擇n- 1條邊，（共n個點）所使用的貪婪准則是：從剩下的邊中選擇一條不會產生環路的
具有最小耗費的邊加入已選擇的邊的集合中。注意到所選取的邊若產生環路則不可能形成一棵生成樹。kruskal演算法分e 步，其中e
是網路中邊的數目。按耗費遞增的順序來考慮這e
條邊，每次考慮一條邊。當考慮某條邊時，若將其加入到已選邊的集合中會出現環路，則將其拋棄，否則，將它選入。
假設WN=(V,{E})是一個含有 n 個頂點的連通網，則按照克魯斯卡爾演算法構造最小生成樹的
過程為：先構造一個只含 n 個頂點，而邊集為空的子圖，若將該子圖中各個頂點看成是各棵樹上的根結點，則它是一個含有 n
棵樹的一個森林。之後，從網的邊集 E
中選取一條權值最小的邊，若該條邊的兩個頂點分屬不同的樹，則將其加入子圖，也就是說，將這兩個頂點分別所在的兩棵樹合成一棵樹；反之，若該條邊的兩個頂
點已落在同一棵樹上，則不可取，而應該取下一條權值最小的邊再試之。依次類推，直至森林中只有一棵樹，也即子圖中含有 n-1條邊為止。

『肆』 克魯斯卡爾演算法是求圖的什麼

求圖的最小生成樹啊，你上面不是也講了么？
求最小生成樹還有另一種prim演算法
prim適合用於稠密圖，kruskal適合用於稀疏圖
兩種演算法都是以貪心為基本思想的~
滿意望採納謝謝！！！！

『伍』 克魯斯卡爾演算法的時間復雜度為多少

時間復雜度為O(|E|log|E|)，其中E和V分別是圖的邊集和點集。

基本思想是先構造一個只含 n 個頂點、而邊集為空的子圖，把子圖中各個頂點看成各棵樹上的根結點，之後，從網的邊集 E 中選取一條權值最小的邊，若該條邊的兩個頂點分屬不同的樹，則將其加入子圖，即把兩棵樹合成一棵樹。

反之，若該條邊的兩個頂點已落在同一棵樹上，則不可取，而應該取下一條權值最小的邊再試之。依次類推，直到森林中只有一棵樹，也即子圖中含有 n-1 條邊為止。

(5)圖的克魯斯卡爾演算法擴展閱讀：

克魯斯卡爾演算法證明

假設G=(V,E) 是一個具有n個頂點的連通網，T=(U,TE)是G的最小生成樹，U的初值等於V，即包含有G中的全部頂點，TE的初值為空集。該演算法的基本思想是：將圖G中的邊按權值從小到大的順序依次選取。

若選取的邊使生成樹T不形成迴路，則把它並入TE中，保留作為T的一條邊，若選取的邊使生成樹T形成迴路，則將其舍棄，如此進行下去直到TE中包含n-1條邊為止，此時的T即為最小生成樹。

克魯斯卡爾演算法，至多對e條邊各掃描一次，每次選擇最小代價的邊僅需要O(loge)的時間。因此，克魯斯卡爾演算法的時間復雜度為O(eloge)。

『陸』 克魯斯卡爾演算法求最小生成樹

克魯斯卡爾演算法的基本思想，這是我自己結合教材理解的，難免有誤，謹慎參考：
1：將圖中的n頂點看成是n個集合。解釋為，圖中共有6個頂點，那麼就有六個集合。即a,b,c,d,e,f各自分別都是一個集合。｛a｝,｛b｝等。
2：按權值由小到大的順序選擇邊。所選邊應滿足兩個頂點不在同一個頂點集合內。將該邊放到生成樹邊的集合，同時將該邊的兩個頂點所在的集合合並。這是書上的描述，可能有點難理解，這里解釋一下：
首先，選擇權值最小的邊，即為圖中的（a,c）邊，此時a,c滿足不在同一個頂點集合內，將這個邊記錄下來，然後合並這兩個頂點的集合，即此時剩下五個頂點集合了，｛a,c｝,｛b｝,｛d｝,｛e｝，｛f｝
3：重復步驟2，直到所有的頂點都在同一個集合內！解釋如下：
此時剩下的邊中權值最小的為（d，f），滿足不在同一個頂點集合，所以記錄下該邊，然後合並這兩個頂點集合。新的頂點集合為｛a，c｝ ｛b｝ ｛e｝ ｛d，f｝
接著，繼續重復，選擇邊（b，e），滿足不在同一個頂點集合內，所以記錄下該邊，然後再次合並這兩個集合，新的集合為｛a,c｝ ｛d,f｝ ｛b,e｝
繼續，選擇邊（c,f）,滿足不在同一個頂點集合內，所以記錄下該邊，然後合並這兩個頂點所在的集合，新集合為｛a,c,d,f｝ ｛b,e｝
再繼續，選擇權值為15的邊，發現邊（c,d）和邊（a,d）都不滿足條件不在同一個頂點集合內，所以只能選擇邊（b,c），記錄下該邊，然後合並頂點集合，新集合為｛a,b,c,d,e,f｝，此時所有點都在同一集合內，所以結束！
4：將上面我們記錄的那些邊連接起來就行了！這就是最小生成樹，附本人手繪：

『柒』 克魯斯卡爾演算法的基本思想

先構造一個只含 n 個頂點、而邊集為空的子圖，把子圖中各個頂點看成各棵樹上的根結點，之後，從網的邊集 E 中選取一條權值最小的邊，若該條邊的兩個頂點分屬不同的樹，則將其加入子圖，即把兩棵樹合成一棵樹，反之，若該條邊的兩個頂點已落在同一棵樹上，則不可取，而應該取下一條權值最小的邊再試之。依次類推，直到森林中只有一棵樹，也即子圖中含有 n-1 條邊為止。時間復雜度為為O(e^2), 使用並查集優化後復雜度為 O（eloge），與網中的邊數有關，適用於求邊稀疏的網的最小生成樹。

『捌』 什麼是克魯斯卡爾演算法

設有一個有n個頂點的連通網N={V,E},最初先構造一個只有n個頂點，沒有邊的非連通圖T={V, E},圖中每個頂點自成一個連通分量。當在E中選到一條具有最小權值的邊時,若該邊的兩個頂點落在不同的連通分量上，則將此邊加入到T中；否則將此邊捨去，重新選擇一條權值最小的邊。如此重復下去，直到所有頂點在同一個連通分量上為止。2演算法描述編輯克魯斯卡爾演算法的時間復雜度為O（eloge）(e為網中邊的數目)，因此它相對於普里姆演算法而言，適合於求邊稀疏的網的最小生成樹。克魯斯卡爾演算法從另一途徑求網的最小生成樹。假設連通網N=（V，{E}），則令最小生成樹的初始狀態為只有n個頂點而無邊的非連通圖T=（V，{∮}），圖中每個頂點自成一個連通分量。在E中選擇代價最小的邊，若該邊依附的頂點落在T中不同的連通分量上，則將此邊加入到T中，否則捨去此邊而選擇下一條代價最小的邊。依次類推，直至T中所有頂點都在同一連通分量上為止。例如圖為依照克魯斯卡爾演算法構造一棵最小生成樹的過程。代價分別為1，2，3，4的四條邊由於滿足上述條件，則先後被加入到T中，代價為5的兩條邊（1，4）和（3，4）被捨去。因為它們依附的兩頂點在同一連通分量上，它們若加入T中，則會使T中產生迴路，而下一條代價（=5）最小的邊（2，3）聯結兩個連通分量，則可加入T。因此，構造成一棵最小生成樹。上述演算法至多對 e條邊各掃描一次，假若以「堆」來存放網中的邊，則每次選擇最小代價的邊僅需O（loge）的時間（第一次需O（e））。又生成樹T的每個連通分量可看成是一個等價類，則構造T加入新的過程類似於求等價類的過程，由此可以以「樹與等價類」中介紹的 mfsettp類型來描述T，使構造T的過程僅需用O（eloge）的時間，由此，克魯斯卡爾演算法的時間復雜度為O（eloge）。^[1]

『玖』 克魯斯卡爾演算法的介紹

克魯斯卡爾演算法是在剩下的所有未選取的邊中，找最小邊，如果和已選取的邊構成迴路，則放棄，選取次小邊。