最小生成樹-Kruskal算法(Java實(shí)現(xiàn))

概念
  • 圖的生成樹是圖的子圖，并且不形成環(huán)路
  • 最小生成樹是帶權(quán)圖中所有生成樹里邊權(quán)值總和最小的一個解，可能不唯一
算法思路
  1. 將圖的所有邊按權(quán)重排序
  2. 按順序取出每條邊
  3. 按原位置拼接，如果形成環(huán)就跳過這一條邊的拼接

算法實(shí)現(xiàn)

圖的實(shí)現(xiàn)
  • 此實(shí)現(xiàn)方法沒有節(jié)點(diǎn)類
  • 采用鄰接矩陣和頂點(diǎn)索引
  • 邊類有兩個成員變量，用于記錄兩個端點(diǎn)的索引int A，int B
  • 鄰接矩陣int[][] matrix(鄰接矩陣無需設(shè)置為沿對角線對稱)
    • matrix[i][j]表示從索引i的節(jié)點(diǎn)指向索引j的節(jié)點(diǎn)的權(quán)值
    • 權(quán)值為0表示兩點(diǎn)不連接或者自身與自身不連接
public class Graph<T> {
    private int N; // N個節(jié)點(diǎn)
    public int[][] matrix;  // 鄰接矩陣
    private T[] datas;  // 保存每個節(jié)點(diǎn)的數(shù)據(jù)
    public List<Edge> edges = new ArrayList<>();
    class Edge {
        int A;  // 頂點(diǎn)索引
        int B;  // 頂點(diǎn)索引

        public Edge(int a, int b) {
            A = a;
            B = b;
        }

        @Override
        public String toString() {
            return "<" +
                    datas[A] +
                    "-" + matrix[A][B] + "-" + datas[B] +
                    '>';
        }
    }
}
兩個重點(diǎn)
  • 每條邊按權(quán)重排序
    • edges是圖所有邊的集合
    • 需要重寫compare()方法，默認(rèn)是升序排序
    • o1和o2是兩個對象也即兩條邊，return matrix[o1.A][o1.B] - matrix[o2.A][o2.B]的作用是，集合調(diào)用sort()方法進(jìn)行排序時，按前一條邊的權(quán)重減去后一條邊的權(quán)重，小于0(前一條邊的權(quán)重小)則兩條邊的位置不變，大于0則交換位置(大概意思是這樣)
        edges.sort(new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                return matrix[o1.A][o1.B] - matrix[o2.A][o2.B];
            }
        });
  • 判斷是否有環(huán)(回路)
    • 基本思路：判斷一條邊加入的時候兩個端點(diǎn)的 "終點(diǎn)" 是否相同，相同則說明有環(huán)
    • getEnd()
      • int[] ends保存所有節(jié)點(diǎn)的終點(diǎn)索引，但不是一開始就確定，而是執(zhí)行最小生成樹算法的過程中才動態(tài)確定每個元素的一個數(shù)組
      • 最開始ends所有元素都是0
      • 如果傳進(jìn)來的索引i，ends[i] == 0則說明這個節(jié)點(diǎn)是第一次被訪問到，則直接返回自身i(因?yàn)椴粫M(jìn)入循環(huán))，表示此節(jié)點(diǎn)的終點(diǎn)是自己
      • 傳進(jìn)來索引i，ends[i] != 0則說明這個節(jié)點(diǎn)不是第一次被訪問到，則把這個節(jié)點(diǎn)的終點(diǎn)索引賦值給i，如果ends[i]仍然不為0則說明最開始索引i的終點(diǎn)也有終點(diǎn)，則再把終點(diǎn)的終點(diǎn)索引賦值給i，while (ends[i] != 0)的作用就是不斷往下找到真正的終點(diǎn)
    • 在遍歷邊集合過程中，endOfA != endOfB如果邊的兩個端點(diǎn)的終點(diǎn)索引不同，ends[endOfA] = endOfB;則把第一個端點(diǎn)的終點(diǎn)的終點(diǎn)設(shè)置為第二個端點(diǎn)的終點(diǎn)(可能有點(diǎn)繞，這步驟的原因是兩個端點(diǎn)終點(diǎn)不同，所以可以加入最終結(jié)果的邊集合，也就是這條邊已經(jīng)確定加入圖中，所以第一個端點(diǎn)必定能按這條邊到達(dá)第二個端點(diǎn)的終點(diǎn))
    /**
     * 本方法獲取索引為i的頂點(diǎn)的終點(diǎn), 用于判斷兩個頂點(diǎn)的終點(diǎn)是否相同
     *
     * @param ends 記錄各個頂點(diǎn)的終點(diǎn)(遍歷過程中才動態(tài)確定的數(shù)組)
     * @param i    傳入的頂點(diǎn)索引
     * @return int 傳入索引對應(yīng)頂點(diǎn)的終點(diǎn)索引
     */
    private int getEnd(int[] ends, int i) {
        while (ends[i] != 0) {  // 循環(huán)是為了找到最終的終點(diǎn)
            i = ends[i];
        }
        return i;
    }

    /*****下面的代碼在最小生成樹算法主體方法中***********************/
            // 如果這條邊取出來拼接后構(gòu)成環(huán), 則取消拼接操作
            int endOfA = getEnd(ends, edge.A);
            int endOfB = getEnd(ends, edge.B);
            // 如果邊的第一個頂點(diǎn)的終點(diǎn)不等于第二個頂點(diǎn)的終點(diǎn)
            if (endOfA != endOfB) {
                // 設(shè)置第一個頂點(diǎn)的終點(diǎn)的終點(diǎn)為第二個頂點(diǎn)的終點(diǎn)
                ends[endOfA] = endOfB;
                result.add(edge);  // 最小生成樹結(jié)果的邊集合
            }
算法主體方法
  1. int[] ends保存取出各個邊后依次拼接時, 各個頂點(diǎn)的終點(diǎn)索引
  2. 把邊的權(quán)重排序
  3. List<Edge> result保存最終結(jié)果的所有邊的集合
  4. 依次取出，不形成回路則拼接
  5. 將結(jié)果集合的所有邊以鄰接矩陣int[][] treeMatrix的形式表現(xiàn)
    /**
     * 克魯斯卡爾算法-最小生成樹
     *
     * @return void
     */
    public void KruskalTree() {
        // ends保存取出各個邊后依次拼接時, 各個頂點(diǎn)的終點(diǎn)索引
        int[] ends = new int[N];
        // 把邊的權(quán)重排序
        edges.sort(new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                return matrix[o1.A][o1.B] - matrix[o2.A][o2.B];
            }
        });
        // 保存最終結(jié)果的所有邊的集合
        List<Edge> result = new ArrayList<>();
        // 依次取出并拼接
        for (Edge edge : edges) {
            // 如果這條邊取出來拼接后構(gòu)成環(huán), 則取消拼接操作
            int endOfA = getEnd(ends, edge.A);
            int endOfB = getEnd(ends, edge.B);
            // 如果邊的第一個頂點(diǎn)的終點(diǎn)不等于第二個頂點(diǎn)的終點(diǎn)
            if (endOfA != endOfB) {
                // 設(shè)置第一個頂點(diǎn)的終點(diǎn)的終點(diǎn)為第二個頂點(diǎn)的終點(diǎn)
                ends[endOfA] = endOfB;
                result.add(edge);
            }
        }
        // 查看一下結(jié)果
        System.out.println(result);
        // 返回最小生成樹的鄰接矩陣
        int[][] treeMatrix = new int[N][N];
        // 將結(jié)果集合的所有邊以鄰接矩陣的形式表現(xiàn)
        for (Edge edge : result) {
            treeMatrix[edge.A][edge.B] = matrix[edge.A][edge.B];
        }
        System.out.println("最小生成樹的鄰接矩陣: ");
        for (int[] nums : treeMatrix) {
            System.out.println(Arrays.toString(nums));
        }
    }
測試
  1. 6個節(jié)點(diǎn)，對應(yīng)保存數(shù)據(jù)為字母ABCDEF
  2. int[][] set是為了初始化鄰接矩陣graph.setMatrix(set[i][0], set[i][1], set[i][2])
  3. 設(shè)置邊集合graph.setEdges()
  4. 執(zhí)行算法graph.KruskalTree() 
    public static void main(String[] args) {
        Graph<String> graph = new Graph<>(6);
        graph.setDatas(new String[]{"A", "B", "C", "D", "E", "F"});
        // {端點(diǎn)索引, 端點(diǎn)索引, 權(quán)值}
        int[][] set = {{0, 1, 1},
                {0, 2, 3},
                {1, 3, 2},
                {1, 5, 2},
                {2, 3, 4},
                {2, 5, 7},
                {3, 4, 1},
                {4, 5, 8}};

        for (int i = 0; i < set.length; i++) {
            // graph.setMatrix(端點(diǎn)索引, 端點(diǎn)索引, 權(quán)值)
            graph.setMatrix(set[i][0], set[i][1], set[i][2]);
        }
        graph.setEdges();
        graph.KruskalTree();
    }
測試結(jié)果
圖
最小生成樹

輸出結(jié)果如下
[<A-1-B>, <D-1-E>, <B-2-D>, <B-2-F>, <A-3-C>]
最小生成樹的鄰接矩陣:
[0, 1, 3, 0, 0, 0]
[0, 0, 0, 2, 0, 2]
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0]

完整代碼實(shí)現(xiàn)

public class Graph<T> {
    private int N; // 節(jié)點(diǎn)個數(shù)
    public int[][] matrix;  // 鄰接矩陣
    private T[] datas;  // 保存每個節(jié)點(diǎn)的數(shù)據(jù)
    public List<Edge> edges = new ArrayList<>();  // 邊集合

    class Edge {
        int A;  // 頂點(diǎn)索引
        int B;  // 頂點(diǎn)索引

        public Edge(int a, int b) {
            A = a;
            B = b;
        }

        // 重寫toString()方法方便查看結(jié)果
        @Override
        public String toString() {
            return "<" +
                    datas[A] +
                    "-" + matrix[A][B] + "-" + datas[B] +
                    '>';
        }
    }

    public Graph(int N) {
        this.N = N;
        matrix = new int[N][N];
        statuses = new Status[N];
        datas = (T[]) new Object[N];  // 泛型數(shù)組實(shí)例化
    }

    /**
     * 鄰接矩陣保存的信息是從一個節(jié)點(diǎn)指向另一個節(jié)點(diǎn)的信息
     *
     * @param from   從這個節(jié)點(diǎn)
     * @param to     指向這個節(jié)點(diǎn)
     * @param weight 路徑權(quán)重
     * @return void
     */
    public void setMatrix(int from, int to, int weight) {
        matrix[from][to] = weight;
    }

    /**
     * 設(shè)置圖的邊(matrix初始化之后才調(diào)用)
     *
     * @return void
     */
    public void setEdges() {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] > 0) {
                    edges.add(new Edge(i, j));
                }
            }
        }
    }

    /**
     * 最小生成樹中判斷是否有回路的重要方法
     * 獲取索引為i的頂點(diǎn)的終點(diǎn), 用于判斷兩個頂點(diǎn)的終點(diǎn)是否相同
     *
     * @param ends 記錄各個頂點(diǎn)的終點(diǎn)(遍歷過程中才動態(tài)確定的數(shù)組)
     * @param i    傳入的頂點(diǎn)索引
     * @return int 原頂點(diǎn)的終點(diǎn)索引
     */
    private int getEnd(int[] ends, int i) {
        System.out.print(datas[i] + "->");
        while (ends[i] != 0) {  // 艸我懂了: 循環(huán)是為了找到最終的終點(diǎn)
            i = ends[i];
        }
        System.out.println(datas[i]);

        return i;
    }

    /**
     * 克魯斯卡爾算法-最小生成樹
     *
     * @return void
     */
    public void KruskalTree() {
        // ends保存取出各個邊后依次拼接時, 各個頂點(diǎn)的終點(diǎn)索引
        int[] ends = new int[N];
        // 把邊的權(quán)重排序
        edges.sort(new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                return matrix[o1.A][o1.B] - matrix[o2.A][o2.B];
            }
        });
        // 保存最小生成樹中包含的邊集合
        List<Edge> result = new ArrayList<>();
        // 依次取出并拼接
        for (Edge edge : edges) {
            // 如果這條邊取出來拼接后構(gòu)成環(huán), 則取消拼接操作
            int endOfA = getEnd(ends, edge.A);
            int endOfB = getEnd(ends, edge.B);
            // 如果邊的第一個頂點(diǎn)的終點(diǎn)不等于第二個頂點(diǎn)的終點(diǎn)
            if (endOfA != endOfB) {
                // 設(shè)置第一個頂點(diǎn)的終點(diǎn)的終點(diǎn)為第二個頂點(diǎn)的終點(diǎn)
                ends[endOfA] = endOfB;
                result.add(edge);
            }
        }
        System.out.println(result);
        // 返回最小生成樹的鄰接矩陣
        int[][] treeMatrix = new int[N][N];
        for (Edge edge : result) {
            treeMatrix[edge.A][edge.B] = matrix[edge.A][edge.B];
        }
        System.out.println("最小生成樹的鄰接矩陣: ");
        for (int[] nums : treeMatrix) {
            System.out.println(Arrays.toString(nums));
        }
    }
    public static void main(String[] args) {
        Graph<String> graph = new Graph<>(6);
        graph.setDatas(new String[]{"A", "B", "C", "D", "E", "F"});
        // {端點(diǎn)索引, 端點(diǎn)索引, 權(quán)值}
        int[][] set = {{0, 1, 1},
                {0, 2, 3},
                {1, 3, 2},
                {1, 5, 2},
                {2, 3, 4},
                {2, 5, 7},
                {3, 4, 1},
                {4, 5, 8}};

        for (int i = 0; i < set.length; i++) {
            // graph.setMatrix(端點(diǎn)索引, 端點(diǎn)索引, 權(quán)值)
            graph.setMatrix(set[i][0], set[i][1], set[i][2]);
        }
        graph.setEdges();
        graph.KruskalTree();
    }
}

謝謝，第一次寫文，不喜輕噴，狗頭保命

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

友情鏈接更多精彩內(nèi)容