最小生成樹之克魯斯卡爾算法

本文将講解生成連通圖的最小生成樹中的克魯斯卡爾算法及其Java實作。

上篇部落格中已經講解了什麼是最小生成樹以及找連通圖的最小生成樹中一種經典的普裡姆算法的原理和實作。有興趣的可以浏覽 http://blog.csdn.net/yz930618/article/details/77930364

克魯斯卡爾算法原理

為使生成樹上邊的權值之和達到最小，則應使生成樹中每一條邊的權值盡可能的小。普裡姆算法是以某頂點為起點，逐漸找各頂點上最小權值的邊來建構最小生成樹。而克魯斯卡爾算法始終選擇目前可用（所選的邊不能構成回路）的最小權值邊來建構生成樹。

克魯斯卡爾算法步驟如下：

• 将圖中的所有邊都去掉。
• 将邊按權值從小到大的順序添加到圖中，保證添加的過程中不會形成環
• 重複上一步直到連接配接所有頂點，此時就生成了最小生成樹。

克魯斯卡爾算法圖解如下：

克魯斯卡爾算法實作

下面是利用Java實作的克魯斯卡爾算法。

import java.util.ArrayList;
import java.util.List;

/**
 * 最小生成樹：克魯斯卡爾算法
 */
public class MinSpanTree {

    int[][] arc;                            // 鄰接矩陣

    int MAXVEX;                             // 頂點個數

    List<Edge> edges = new ArrayList<>();   // 邊集數組

    int[] parent;                           // 用于判斷邊與邊是否形成回路

    public MinSpanTree(){
        createArc(); //生成鄰接矩陣
        createEdge();    //生成邊集數組
        createParent();   //生成parent數組
    }

    //生成parent數組
    private void createParent(int i) {
        parent = new int[MAXVEX];
    }

    // 生成邊集數組
    private void createEdge(int i) {
        Edge v0 = new Edge(,,);
        Edge v1 = new Edge(,,);
        Edge v2 = new Edge(,,);
        Edge v3 = new Edge(,,);
        Edge v4 = new Edge(,,);
        Edge v5 = new Edge(,,);
        Edge v6 = new Edge(,,);
        Edge v7 = new Edge(,,);
        Edge v8 = new Edge(,,);
        Edge v9 = new Edge(,,);
        Edge v10 = new Edge(,,);
        Edge v11 = new Edge(,,);
        Edge v12 = new Edge(,,);
        Edge v13 = new Edge(,,);
        Edge v14 = new Edge(,,);

        this.edges.add(v0);
        this.edges.add(v1);
        this.edges.add(v2);
        this.edges.add(v3);
        this.edges.add(v4);
        this.edges.add(v5);
        this.edges.add(v6);
        this.edges.add(v7);
        this.edges.add(v8);
        this.edges.add(v9);
        this.edges.add(v10);
        this.edges.add(v11);
        this.edges.add(v12);
        this.edges.add(v13);
        this.edges.add(v14);
    }

    // 生成鄰接矩陣
    private void createArc(int index) {
        MAXVEX = index;
        arc = new int[index][index];
        this.arc[] = new int[]{        ,       ,MAXVEX,MAXVEX,MAXVEX,       ,MAXVEX,MAXVEX,MAXVEX};
        this.arc[] = new int[]{       ,        ,       ,MAXVEX,MAXVEX,MAXVEX,       ,MAXVEX,       };
        this.arc[] = new int[]{MAXVEX,MAXVEX,        ,       ,MAXVEX,MAXVEX,MAXVEX,MAXVEX,        };
        this.arc[] = new int[]{MAXVEX,MAXVEX,       ,        ,       ,MAXVEX,MAXVEX,       ,       };
        this.arc[] = new int[]{MAXVEX,MAXVEX,MAXVEX,       ,        ,       ,MAXVEX,        ,MAXVEX};
        this.arc[] = new int[]{       ,MAXVEX,MAXVEX,MAXVEX,       ,        ,       ,MAXVEX,MAXVEX};
        this.arc[] = new int[]{MAXVEX,       ,MAXVEX,MAXVEX,MAXVEX,       ,        ,       ,MAXVEX};
        this.arc[] = new int[]{MAXVEX,MAXVEX,MAXVEX,       ,        ,MAXVEX,       ,        ,MAXVEX};
        this.arc[] = new int[]{MAXVEX,       ,        ,       ,MAXVEX,MAXVEX,MAXVEX,MAXVEX,         };
    }

    /**
     * 克魯斯卡爾實作最小生成樹
     */
    public void kruskal(){
        int i,n,m;
        int count = ;
        for(i = ;i < this.edges.size();i++){//周遊每一條邊
            int begin = this.edges.get(i).getBegin();
            int end = this.edges.get(i).getEnd();
            n = this.find(begin);
            m = this.find(end);
            if(n != m) {//如果n不等于m，則說明沒有形成回路
                count++;
                parent[n] = m;  //将此邊的尾結點放入parent數組中，數組的下标表示頭結點。parent[n] = m表示此頂點已經在生成樹中
                System.out.println(" 第  "+count+" 條邊為 : ( "+this.edges.get(i).getBegin()+" , "+ this.edges.get(i).getEnd() +" ) = "+this.edges.get(i).getWeight()+" ");
            }
        }
    }

    //查找連接配接頂點的尾部下标
    public int find(int f){
        while(this.parent[f] > ){
            f = this.parent[f];
        }
        return f;
    }

    public static void main(String[] args) {
        MinSpanTree kruskal = new MinSpanTree();
        kruskal.kruskal();
    }
}
           

邊的實體類：

public class Edge {
    private int begin;  // 邊的起點
    private int end;    // 邊的終點
    int weight;         // 邊的權重

    public Edge(int begin, int end, int weight) {
        this.begin = begin;
        this.end = end;
        this.weight = weight;
    }

    public int getBegin() {
        return begin;
    }
    public void setBegin(int begin) {
        this.begin = begin;
    }
    public int getEnd() {
        return end;
    }
    public void setEnd(int end) {
        this.end = end;
    }
    public int getWeight() {
        return weight;
    }
    public void setWeight(int weight) {
        this.weight = weight;
    }
}
           

運作結果如下