《DSAA》 9.5.2 Kruskal 算法

如何用最少的電線給一所房子安裝電路？本質上就是如何從一個無向圖中找出一顆最小生成樹。一個無向圖中的最小生成樹由該圖的那些連接配接所有頂點的邊構成的樹，且其總價值最小。

有兩個解決此問題的算法：Prim 和 Kruskal，這裡隻讨論後者，因為它比較簡明有趣。

和一般處理圖的算法不同，Kruskal 實際上是在處理森林，即樹的集合，開始時每個頂點是一顆單節點樹，添加一條邊則意味着将兩顆樹合并成一棵樹，添加邊的順序是從小到大，當邊數比總頂點數小1時算法終止，這時就隻有一顆樹了，這顆樹就是最小生成樹。

但還有一個關鍵的問題是在添加邊之前要對其進行檢驗，看看它是否會同已有的邊構成回路，如是必須放棄這條邊，否則将導緻算法失敗。檢驗的方法是使用一個不相交集合，當兩個頂點在目前森林中連通時，它們必屬于同一集合，是以當要添加邊的兩個頂點屬于同一集合時，則放棄這條邊。

btw，不相交集合在《DSAA》前面的章節講過，它主要有兩個方法：Union() 和 Find()，前者用于合并兩個不相交集合，後者傳回給定元素所在的集合，這裡不贅述。

也是根據原書的僞代碼做了實作，大緻思路如下：

1）将全部的邊裝入一個二叉堆，按照權值從小到大排序

2）從堆中取出最小的邊，如果其兩個頂點不屬于同一集合，則邊數加1，合并這兩個集合。否則什麼也不做

3）重複第二步直到邊數比總頂點數小1

下面是對原書中示例的求解，運作結果如下：