克魯斯卡爾演算法流程圖

Ⅰ 最小生成樹

所謂最小生成樹，就是在一個具有N個頂點的帶權連通圖G中，如果存在某個子圖G'，其包含了圖G中的所有頂點和一部分邊，且不形成迴路，並且子圖G'的各邊權值之和最小，則稱G'為圖G的最小生成樹。 由定義我們可得知最小生成樹的三個性質：
•最小生成樹不能有迴路。
•最小生成樹可能是一個，也可能是多個。
•最小生成樹邊的個數等於頂點的個數減一。宴昌 本文將介紹兩種最小生成樹的演算法，分別為克魯斯卡爾演算法(Kruskal Algorithm)和普利姆演算法(Prim Algorithm)。

克魯斯卡爾演算法的核心思想是：在帶權連通圖中，不斷地在邊集合中找到最小的邊，如果該邊滿足得到最小生成樹的條件，就將其構造，直到最後得到一顆最小生成樹。
克魯斯卡爾演算法的執行步驟：
第一步：在帶權連通圖中，將邊的權值排序；
第二步：判斷是否需要選擇這條邊（此時圖中的邊已按權值從小到大排好序）。判斷的依據是邊的兩個頂點是亂蘆否已連通，如果連通則繼續下一條；如果不連通，那麼就選擇晌陪扒使其連通。
第三步：循環第二步，直到圖中所有的頂點都在同一個連通分量中，即得到最小生成樹。
下面我用圖示法來演示克魯斯卡爾演算法的工作流程，如下圖：

Ⅱ kruskal演算法的舉例描述

克魯斯卡爾演算法(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)。

Ⅲ 這是一道數據結構問題，問題如下：對於如下圖所示的帶權無向圖，給出利用普利姆（Prim)演算法和克魯斯卡爾

自己按下面的先後過程畫圖即是生成過程；說雀雀明（i,j）是一條連接頂點i和j的一條邊；
普利姆（Prim)演算法：從頂點0開始頃世早構造
（0,1），（0,2），（1,2），（2,5），（5,4）
克魯斯卡爾演算法：
（0,1），（0,2），（返或1,2），（4,5），（2,5）