Java十大算法之克魯斯卡爾算法

應用場景:

1.克魯斯卡爾算法介紹

克魯斯卡爾(Kruskal)算法,是用來求權重連通圖的最小生成樹的算法,基本思想:按照權值從小到大的順序選擇n-1條邊,并保證這n-1條邊不構成回路,具體做法:首先構造一個隻含有n個頂點的森林,然後依權值從小到大從連通網中選擇邊加入到森林中,并使森林中不産生回路,直到森林變成一棵樹為止

接下來用圖解的方式進行一下分析:

上面的連通網,不同的連通方式,權值總和是不一樣的,以本圖為例,進行克魯斯卡爾示範:

(1)第一步

(2)第二步

(3)第三步

(4)第四步,雖然EC,FC的距離都比BF短,但是我們依然選取BF,因為EC,FC都構成短路(關于什麼是短路,在示範結束會講解)

(5)第五步

(6)第六步

克魯斯卡爾算法分析:

克魯斯卡爾算法重點需要解決兩個問題

(1)對圖的所有邊按照權值大小進行排序?

解決:采用排序算法進行排序即可.

(2)将邊添加到最小生成樹中時,怎麼樣判斷是否形成了回路?

記錄頂點在"最小生成樹"中的終點,頂點的終點是"在最小生成樹中與它連通的最大頂點",然後每次需要将一條邊添加到最小生成樹時,判斷該邊的兩個頂點的終點是否重合,重合的話則會構成回路

圖解說明:

在将<E,F>,<C,D>,<D,E>加入到最小生成樹R中之後,這幾條邊的頂點就都有了終點

C的終點是F

D的終點是F

E的終點是F

F的終點是F

關于終點的說明:就是将所有頂點按照從小到大的順序排列好之後,某個頂點的終點就是"與它連通的最大頂點",是以,接下來,雖然<C,E>是權最小的邊,但是C和E的終點都是F,即他們終點相同,是以,将<C,E>加入最小生成樹的話,會形成回路,這就是回路的判斷方式,也就是說,我們加入的邊的兩個頂點不能都指向同一個終點,否則構成回路

代碼實作

package com.self.tenAlgorithm;

import java.util.Arrays;

public class KruskaCase {
    private char[] vertexs;  //頂點
    private int edgeNum;  //邊的個數
    private int[][] matrix;  //鄰接矩陣
    private static final int INT = Integer.MAX_VALUE;
    public static void main(String[] args) {
        char[] vertexs = {'A','B','C','D','E','F','G'};
        int[][] matrix = {
                {0,12,INT,INT,INT,16,14},
                {12,0,10,INT,INT,7,INT},
                {INT,10,0,3,5,6,INT},
                {INT,INT,3,0,4,INT,INT},
                {INT,INT,5,4,0,2,8},
                {16,7,6,INT,2,0,9},
                {14,INT,INT,INT,8,9,0}
        };
        KruskaCase kruskaCase = new KruskaCase(vertexs, matrix);
        kruskaCase.print();

        EData[] egdes = kruskaCase.getEgdes();
        System.out.println(Arrays.toString(egdes));
        System.out.println("==========================================================");
        kruskaCase.sortEdges(egdes);
        System.out.println(Arrays.toString(egdes));
        System.out.println("==========================================================");
        kruskaCase.kruskal();
    }

    /**
     * @param vertexs  頂點數組
     * @param matrix  鄰接矩陣
     */
    //構造器
    public KruskaCase(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] != INT){
                    edgeNum ++;
                }
            }
        }
    }
    public void kruskal(){
        int index = 0;  //表示最後結果數組的索引
        int[] ends = new int[edgeNum];//用于儲存已有"最小生成樹"中的每個頂點在最小生成樹中的終點
        //建立結果數組,儲存最小生成樹
        EData[] rets = new EData[edgeNum];
        //擷取圖中所有邊的集合
        EData[] egdes = getEgdes();
        //按照權值從小到大排序
        sortEdges(egdes);
        //周遊edges數組,将邊添加到最小生成樹,判斷準備加入的邊是否構成了回路,如果沒有,就加入rets,否則不能加入
        for (int i = 0; i < edgeNum; i++) {
            //擷取到第i條邊的第一個頂點(起點)  下标
            int p1 = getPosition(egdes[i].start);
            //擷取第i條邊的第2個頂點  下标
            int p2 = getPosition(egdes[i].end);

            //擷取p1這個頂點在已有最小生成樹中的終點
            int m = getEnd(ends, p1);
            int n = getEnd(ends,p2);
            if(m != n){  //判斷是否構成了回路  不等于 沒有構成回路
                ends[m] = n;  //設定m在"已有最小生成樹"中的終點
                rets[index++] = egdes[i];  //有一條邊加入到rets數組
            }
        }
        //統計并列印"最小生成樹",輸出rets
        System.out.println("最小生成樹為:");
        for (int i = 0; i < index; i++) {
            System.out.println(rets[i]);
        }
    }

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

    /**   對邊進行排序
     * @param edges  邊的集合
     */
    private void sortEdges(EData[] edges){
        for (int i = 0; i < edges.length - 1; i++) {
            for (int j = 0; j < edges.length - 1 - i; j++) {
                if(edges[j].weight > edges[i].weight){
                    EData temp = edges[j];
                    edges[j] = edges[i];
                    edges[i] = temp;
                }
            }
        }
    }

    /**
     * @param ch   頂點的值
     * @return  傳回頂點的下标  如果找不到 傳回-1
     */
    private int getPosition(char ch){
        for (int i = 0; i < vertexs.length; i++) {
            if(vertexs[i] == ch){
                return i;
            }
        }
        return -1;
    }

    /** 擷取圖中邊 放到EData[] 數組中  後面我們需要周遊數組
     * @return  形式['A','B',12]
     */
    private EData[] getEgdes(){
        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] != INT){
                    edges[index++] = new EData(vertexs[i],vertexs[j],matrix[i][j]);
                }
            }
        }
        return edges;
    }

    /**功能:擷取下标為i的頂點的終點,用于後面判斷兩個頂點的終點是否相同
     * @param ends 記錄各個頂點對應的終點是哪一個,endss數組是在周遊的過程中,逐漸生成
     * @param i  表示對應的頂點對應的下标
     * @return  傳回的就是這個頂點對應的下标
     */
    private int getEnd(int[] ends,int i){
        while (ends[i] != 0){
            i = ends[i];
        }
        return 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;
    }

    @Override
    public String toString() {
        return "EData{" +
                "start=" + start +
                ", end=" + end +
                ", weight=" + weight +
                '}';
    }
}