最小生成樹 - Kruskal算法

Kruskal算法

第二種最小生成樹算法 —— Kruskal算法

按照邊的權重順序（從小到大）處理它們，将邊加入最小生成樹中，加入的邊不會與已經加入的邊構成環，直到樹中含有 V − 1 V-1 V−1 條邊為止。這些邊逐漸由一片森林合并為一棵樹，也就是圖的最小生成樹。

Kruskal算法能夠得到任意權重無向圖的最小生成樹。

算法如下：

使用一條優先隊列pq 來将邊按照權重排序，一個union-find資料結構uf 來識别會形成環的邊，一條隊列mst來儲存最小生成樹的所有邊。

/*
 * 最小生成樹的 Kruskal算法
 */
public class KruskalMST {
    private Queue<Edge> mst;   //使用一條隊列來儲存最小生成樹的所有邊
    
    public KruskalMST(EdgeWeightedGraph G) {
        mst = new Queue<Edge>();
        MinPQ<Edge> pq = new MinPQ<>();   //使用一條優先隊列來儲存還未被檢查的邊
        for(Edge e : G.edges()) 
            pq.insert(e);
            
        UF uf = new UF(G.V());     //使用一個union-find資料結構來判斷無效的邊
        while(!pq.isEmpty() && mst.size() < G.V()-1) {
            Edge e = pq.delMin();        //從pq得到權重最小的邊和它的頂點
            int v = e.either(), w=e.other(v);
            if(uf.connected(v, w))       //處于同一個連通分量中.忽略失效的邊
            	continue;    
            uf.union(v, w);       //合并分量
            mst.enqueue(e);       //将邊添加到最小生成樹中
        }
    }
    public Iterable<Edge> edges() { return mst; }
    
}