克魯斯卡爾算法

克魯斯卡爾算法介紹

克魯斯卡爾(Kruskal)算法，是用來求權重連通圖的最小生成樹的算法。

==基本思想==：按照權值從小到大的順序選擇n-1條邊，并保證這n-1條邊不構成回路

==具體做法==：首先構造一個隻含n個頂點的森林，然後依權值從小到大從連通網中選擇邊加入到森林中，并使森林中不産生回路，直至森林變成一棵樹為止

克魯斯卡爾最佳實踐-公交站問題

有北京有新增7個站點(A, B, C, D, E, F, G) ，現在需要修路把7個站點連通

各個站點的距離用邊線表示(權) ，比如 A – B 距離 12公裡
    問：如何修路保證各個站點都能連通，并且總的修建公路總裡程最短?
           

代碼示例

package com.wxit.kruskal;

import java.util.Arrays;

/**
 * @Author wj
 **/
public class KruskalCase {

    private int edgeNum; //邊的個數
    private char[] vertexs; //頂點數組
    private int[][] matrix; //鄰接矩陣
    //使用INF 表示兩個頂點不能聯通
    private static final int INF = Integer.MAX_VALUE;
    public static void main(String[] args) {
        char[] vertexs = {'A','B','C','D','E','F','G'};
        //克魯斯卡爾算法的鄰接矩陣
        int matrix[][] = {
                {0,12,INF,INF,INF,16,14},
                {12,0,10,INF,INF,7,INF},
                {INF,10,0,3,5,6,INF},
                {INF,INF,3,0,4,INF,INF},
                {INF,INF,5,4,0,2,8},
                {16,7,6,INF,2,0,9},
                {14,INF,INF,INF,8,9,0}
        };

        //建立KruskalCase對象
        KruskalCase kruskalCase = new KruskalCase(vertexs, matrix);
        kruskalCase.print();
        System.out.println("xx" + Arrays.toString(kruskalCase.getEdges()));
        kruskalCase.kruskal();
    }

    //構造器
    public KruskalCase(char[] vertexs,int[][] matrix){
        //初始化頂點數和邊的個數
        int vlen = vertexs.length;

        //初始化頂點
        this.vertexs = new char[vlen];
        for (int i = 0; i < vertexs.length; i++) {
            this.vertexs[i] = vertexs[i];
        }

        //初始化邊，使用的是複制拷貝的方式
        this.matrix = new int[vlen][vlen];
        for (int i = 0; i < vlen; i++) {
            for (int j = 0; j < vlen; j++) {
                this.matrix[i][j] = matrix[i][j];
            }
        }

        //統計邊
        for (int i = 0; i < vlen; i++) {
            for (int j = i + 1; j < vlen; j++) {
                if (this.matrix[i][j] != INF){
                    edgeNum++;
                }
            }
        }
    }

    //列印鄰接矩陣
    public void print(){
        System.out.println("鄰接矩陣為:\n");
        for (int i = 0; i < vertexs.length; i++) {
            for (int j = 0; j < vertexs.length; j++) {
                System.out.printf("%10d",matrix[i][j]);
            }
            System.out.println();
        }
    }

    /**
     * 功能:對邊進行排序處理,冒泡排序
     * @param edges 邊的集合
     */
    private void sortEdges(EData[] edges){
        for (int i = 0; i < edges.length; i++) {
            for (int j = 0; j < edges.length - 1 - i; j++) {
                if (edges[j].weight >edges[j + 1].weight){ //交換
                    EData tmp = edges[j];
                    edges[j] = edges[j + 1];
                    edges[j + 1] = tmp;
                }
            }
        }
    }

    /**
     *
     * @param ch
     * @return
     */
    private int getPosition(char ch){
        for (int i = 0; i < vertexs.length; i++) {
            if (vertexs[i] == ch){
                return i;
            }
        }
        //找不到
        return -1;
    }

    /**
     * 功能:擷取圖中邊，放到EData[]數組中，後面我們需要周遊該數組
     * 是通過matrix 鄰接矩陣來擷取
     * EData[]  形式[['A],'B',12],
     * @return
     */
    private EData[] getEdges(){
        int index = 0;
        EData[] edges = new EData[edgeNum];
        for (int i = 0; i < vertexs.length; i++) {
            for (int j = i + 1; j < vertexs.length; j++) {
                if (matrix[i][j] != INF){
                    edges[index++] = new EData(vertexs[i],vertexs[j],matrix[i][j]);
                }
            }
        }
        return edges;
    }

    /**
     * 功能:擷取下标為i的頂點終點（），用于後面判斷兩個頂點的終點是否相同
     * @param ends  數組就是記錄了各個頂點對應的終點是哪個。end數組是在周遊過程中逐漸形成的
     * @param i 表示傳入的頂點對應的下标
     * @return 傳回的就是下标為i的這個頂點對應的終點下标
     */
    private int getEnd(int[] ends,int i){
        while (ends[i] != 0){
            i = ends[i];
        }
        return i;
    }

    //
    public void kruskal(){
        int index = 0; //表示最後結果數組的索引
        int[] ends = new int[edgeNum];//用于儲存“已有生成樹"中的每個頂點在最小生成樹中的終點
        //建立結果數組，儲存最後的最小生成樹
        EData[] rets = new EData[edgeNum];

        //擷取圖中,所有的邊的集合，一共有12邊
        EData[] edges = getEdges();
        System.out.println("圖的邊的集合=" + Arrays.toString(edges) + "共" + edges.length);

        //按照邊的權值排序。從小到大
        sortEdges(edges);

        //周遊edges數組，将邊添加到最小生成樹時，判斷準備加入的邊是否形成回路，如果沒有，就加入rets，否則不能加入
        for (int i = 0; i < edgeNum; i++) {
            //擷取到第i條邊的第一個頂點(起點)
            int p1 = getPosition(edges[i].start);
            //擷取到第i條邊的第二個頂點
            int p2 = getPosition(edges[i].end);

            //擷取p1這個頂點在已有的最小生成樹中的終點
            int m = getEnd(ends,p1);
            //擷取p2這個頂點在已有最小生成樹的終點
            int n = getEnd(ends,p2);
            //是否構成回路
            if (m != n){ //沒有構成回路
                ends[m] = n;
                rets[index++] = edges[i];//有一條邊加入到rets數組
            }
        }

        //統計并列印"最小生成樹"輸出rets
        System.out.println("最小的生成樹為");
        for (int i = 0; i < index; i++) {
            System.out.println(rets[i]);
        }
    }
}

//建立一個類EData，它的對象執行個體就表示一條邊
class EData{
    char start; //邊的一個點
    char end; //邊的另一個點
    int weight; //邊的權值

    //構造器
    public EData(char start,char end, int weight){
        this.start = start;
        this.end = end;
        this.weight = weight;
    }

    //重寫toString,便于輸出邊
    @Override
    public String toString() {
        return "EData{" +
                "start=" + start +
                ", end=" + end +
                ", weight=" + weight +
                '}';
    }
}