Java求最小生成樹的兩種算法詳解

/**
 * 無向加權圖鄰接矩陣實現
 * {@link MatrixPrimAndKruskal#MatrixPrimAndKruskal(E[], Edge[])}  構建無向加權圖
 * {@link MatrixPrimAndKruskal#DFS()}  深度優先遍歷無向加權圖
 * {@link MatrixPrimAndKruskal#BFS()}  廣度優先遍歷無向加權圖
 * {@link MatrixPrimAndKruskal#toString()}  輸出無向加權圖
 * {@link MatrixPrimAndKruskal#prim()}  Prim算法實現最小生成樹
 * {@link MatrixPrimAndKruskal#kruskal()}   Kruskal算法實現最小生成樹
 * {@link MatrixPrimAndKruskal#kruskalAndPrim()}  Kruskal算法結合Prim算法實現最小生成樹
 * {@link MatrixPrimAndKruskal#getEdges()}  獲取邊集數組
 *
 * @author lx
 * @date 2020/5/14 18:13
 */
public class MatrixPrimAndKruskal<E> {

    /**
     * 頂點數組
     */
    private Object[] vertexs;

    /**
     * 鄰接矩陣
     */
    private int[][] matrix;

    /**
     *
     */
    private Edge<E>[] edges;

    /**
     * 由於是加權圖,這裡設置一個邊的權值上限,任何邊的最大權值不能大於等於該值，在實際應用中，該值應該根據實際情況確定
     */
    private static final int NO_EDGE = 99;


    /**
     * 邊對象,具有權值,在構建加權無向圖時使用
     */
    private static class Edge<E> {

        private E from;
        private E to;
        private int weight;

        public Edge(E from, E to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }

        @Override
        public String toString() {
            return "Edge{" +
                    "from=" + from +
                    ", to=" + to +
                    ", weight=" + weight +
                    '}';
        }
    }

    /**
     * 創建無向加權圖
     *
     * @param vertexs 頂點數組
     * @param edges   邊對象數組
     */
    public MatrixPrimAndKruskal(Object[] vertexs, Edge<E>[] edges) {
        //初始化邊數組
        this.edges = edges;
        // 初始化頂點數組,並添加頂點
        this.vertexs = Arrays.copyOf(vertexs, vertexs.length);
        // 初始化邊矩陣,並預先填充邊信息
        this.matrix = new int[vertexs.length][vertexs.length];
        for (int i = 0; i < vertexs.length; i++) {
            for (int j = 0; j < vertexs.length; j++) {
                if (i == j) {
                    this.matrix[i][j] = 0;
                } else {
                    this.matrix[i][j] = NO_EDGE;
                }
            }
        }
        for (Edge<E> edge : edges) {
            // 讀取一條邊的起始頂點和結束頂點索引值
            int p1 = getPosition(edge.from);
            int p2 = getPosition(edge.to);
            //對稱的兩個點位都置為edge.weight,無向圖可以看作相互可達的有向圖
            this.matrix[p1][p2] = edge.weight;
            this.matrix[p2][p1] = edge.weight;
        }
    }

    /**
     * 獲取某條邊的某個頂點所在頂點數組的索引位置
     *
     * @param e 頂點的值
     * @return 所在頂點數組的索引位置, 或者-1 - 表示不存在
     */
    private int getPosition(E e) {
        for (int i = 0; i < vertexs.length; i++) {
            if (vertexs[i] == e) {
                return i;
            }
        }
        return -1;
    }


    /**
     * 深度優先搜索遍歷圖,類似於樹的前序遍歷,
     */
    public void DFS() {
        //新建頂點訪問標記數組,對應每個索引對應相同索引的頂點數組中的頂點
        boolean[] visited = new boolean[vertexs.length];
        //初始化所有頂點都沒有被訪問
        for (int i = 0; i < vertexs.length; i++) {
            visited[i] = false;
        }
        System.out.println("DFS: ");
        for (int i = 0; i < vertexs.length; i++) {
            if (!visited[i]) {
                DFS(i, visited);
            }
        }
        System.out.println();
    }

    /**
     * 深度優先搜索遍歷圖的遞歸實現,類似於樹的先序遍歷
     * 因此模仿樹的先序遍歷,同樣借用棧結構,這裡使用的是方法的遞歸,隱式的借用棧
     *
     * @param i       頂點索引
     * @param visited 訪問標志數組
     */
    private void DFS(int i, boolean[] visited) {
        visited[i] = true;
        System.out.print(vertexs[i] + " ");
        // 遍歷該頂點的所有鄰接點。若該鄰接點是沒有訪問過，那麼繼續遞歸遍歷領接點
        for (int w = firstVertex(i); w >= 0; w = nextVertex(i, w)) {
            if (!visited[w]) {
                DFS(w, visited);
            }
        }
    }


    /**
     * 廣度優先搜索圖,類似於樹的層序遍歷
     * 因此模仿樹的層序遍歷,同樣借用隊列結構
     */
    public void BFS() {
        // 輔組隊列
        Queue<Integer> indexLinkedList = new LinkedList<>();
        //新建頂點訪問標記數組,對應每個索引對應相同索引的頂點數組中的頂點
        boolean[] visited = new boolean[vertexs.length];
        for (int i = 0; i < vertexs.length; i++) {
            visited[i] = false;
        }
        System.out.println("BFS: ");
        for (int i = 0; i < vertexs.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                System.out.print(vertexs[i] + " ");
                indexLinkedList.add(i);
            }
            if (!indexLinkedList.isEmpty()) {
                //j索引出隊列
                Integer j = indexLinkedList.poll();
                //繼續訪問j的鄰接點
                for (int k = firstVertex(j); k >= 0; k = nextVertex(j, k)) {
                    if (!visited[k]) {
                        visited[k] = true;
                        System.out.print(vertexs[k] + " ");
                        //繼續入隊列
                        indexLinkedList.add(k);
                    }
                }
            }
        }
        System.out.println();
    }

    /**
     * 返回頂點v的第一個鄰接頂點的索引，失敗則返回-1
     *
     * @param v 頂點v在數組中的索引
     * @return 返回頂點v的第一個鄰接頂點的索引，失敗則返回-1
     */
    private int firstVertex(int v) {
        //如果索引超出范圍,則返回-1
        if (v < 0 || v > (vertexs.length - 1)) {
            return -1;
        }
        /*根據鄰接矩陣的規律:頂點索引v對應著邊二維矩陣的matrix[v][i]一行記錄
         * 從i=0開始*/
        for (int i = 0; i < vertexs.length; i++) {
            if (matrix[v][i] != 0 && matrix[v][i] != NO_EDGE) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 返回頂點v相對於w的下一個鄰接頂點的索引，失敗則返回-1
     *
     * @param v 頂點索引
     * @param w 第一個鄰接點索引
     * @return 返回頂點v相對於w的下一個鄰接頂點的索引，失敗則返回-1
     */
    private int nextVertex(int v, int w) {
        //如果索引超出范圍,則返回-1
        if (v < 0 || v > (vertexs.length - 1) || w < 0 || w > (vertexs.length - 1)) {
            return -1;
        }
        /*根據鄰接矩陣的規律:頂點索引v對應著邊二維矩陣的matrix[v][i]一行記錄
         * 由於鄰接點w的索引已經獲取瞭,所以從i=w+1開始尋找*/
        for (int i = w + 1; i < vertexs.length; i++) {
            if (matrix[v][i] != 0 && matrix[v][i] != NO_EDGE) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 輸出圖
     *
     * @return 輸出圖字符串
     */
    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < vertexs.length; i++) {
            for (int j = 0; j < vertexs.length; j++) {
                stringBuilder.append(matrix[i][j]).append("\t");
            }
            stringBuilder.append("\n");
        }
        return stringBuilder.toString();
    }

    /**
     * Prim算法求最小生成樹
     */
    public void prim() {
        System.out.println("prim: ");
        //對應節點應該被連接的前驅節點,用來輸出
        //默認為0,即前驅結點為第一個節點
        int[] mid = new int[matrix.length];
        //如果某頂點作為末端頂點被連接，對應位置應該為true
        //第一個頂點默認被連接
        boolean[] connected = new boolean[matrix.length];
        connected[0] = true;
        //存儲未連接頂點到已連接頂點的最短距離(最小權)
        int[] dis = new int[matrix.length];
        //首先將矩陣第一行即其他頂點到0索引頂點的權值拷貝進去
        System.arraycopy(matrix[0], 0, dis, 0, matrix.length);
        //存儲路徑長度
        int sum = 0;
        //最小權值
        int min;
        /*默認第一個頂點已經找到瞭,因此最多還要需要大循環n-1次*/
        for (int k = 1; k < matrix.length; k++) {
            min = NO_EDGE;
            //最小權值的頂點的索引
            int minIndex = 0;
            /*尋找權值最小的且未被連接的頂點索引*/
            for (int i = 1; i < matrix.length; i++) {
                //排除已連接的頂點,排除權值等於0的值,這裡權值等於0表示已生成的最小生成樹的頂點都未能與該頂點連接
                if (!connected[i] && dis[i] != 0 && dis[i] < min) {
                    min = dis[i];
                    minIndex = i;
                }
            }
            //如果沒找到,那麼該圖可能不是連通圖,直接返回瞭,此時最小生成樹沒啥意義
            if (minIndex == 0) {
                return;
            }
            //權值和增加
            sum += min;
            //該新連接頂點對應的索引值變成true,表示已被連接,後續判斷時跳過該頂點
            connected[minIndex] = true;
            //輸出對應的前驅頂點到該最小頂點的權值
            System.out.println(vertexs[mid[minIndex]] + " ---> " + vertexs[minIndex] + " 權值:" + min);
            /*在新頂點minIndex加入之前的其他所有頂點到連接頂點最小的權值已經計算過瞭
            因此隻需要更新其他未連接頂點到新連接頂點minIndex是否還有更短的權值,有的話就更新找到距離已連接的頂點權最小的頂點*/
            for (int i = 1; i < matrix.length; i++) {
                //如果該頂點未連接
                if (!connected[i]) {
                    /*如果新頂點到未連接頂點i的權值不為0,並且比原始頂點到未連接頂點i的權值還要小,那麼更新對應位置的最小權值*/
                    if (matrix[minIndex][i] != 0 && dis[i] > matrix[minIndex][i]) {
                        //更新最小權值
                        dis[i] = matrix[minIndex][i];
                        //更新前驅節點索引為新加入節點索引
                        mid[i] = minIndex;
                    }
                }

            }
        }
        System.out.println("sum: " + sum);
    }


    /**
     * Kruskal算法求最小生成樹傳統實現,要求知道邊集數組,和頂點數組
     */
    public void kruskal() {
        System.out.println("Kruskal: ");
        //由於創建圖的時候保存瞭邊集數組,這裡直接使用就行瞭
        //Edge[] edges = getEdges();
        //this.edges=edges;
        //對邊集數組進行排序
        Arrays.sort(this.edges, Comparator.comparingInt(o -> o.weight));
        // 用於保存已有最小生成樹中每個頂點在該最小樹中的最終終點的索引
        int[] vends = new int[this.edges.length];
        //能夠知道終點索引范圍是[0,this.edges.length-1],因此填充edges.length表示沒有終點
        Arrays.fill(vends, this.edges.length);
        int sum = 0;
        for (Edge<E> edge : this.edges) {
            // 獲取第i條邊的起點索引from
            int from = getPosition(edge.from);
            // 獲取第i條邊的終點索引to
            int to = getPosition(edge.to);
            // 獲取頂點from在"已有的最小生成樹"中的終點
            int m = getEndIndex(vends, from);
            // 獲取頂點to在"已有的最小生成樹"中的終點
            int n = getEndIndex(vends, to);
            // 如果m!=n，意味著沒有形成環路,則可以添加,否則直接跳過,進行下一條邊的判斷
            if (m != n) {
                //添加設置原始終點索引m在已有的最小生成樹中的終點為n
                vends[m] = n;
                System.out.println(vertexs[from] + " ---> " + vertexs[to] + " 權值:" + edge.weight);
                sum += edge.weight;
            }
        }
        System.out.println("sum: " + sum);
        //System.out.println(Arrays.toString(this.edges));
    }

    /**
     * 獲取頂點索引i的終點如果沒有終點則返回頂點索引本身
     *
     * @param vends 頂點在最小生成樹中的終點
     * @param i     頂點索引
     * @return 頂點索引i的終點如果沒有終點則返回頂點索引本身
     */
    private int getEndIndex(int[] vends, int i) {
        //這裡使用循環查找的邏輯,尋找的是最終的終點
        while (vends[i] != this.edges.length) {
            i = vends[i];
        }
        return i;
    }

    /**
     * 如果沒有現成的邊集數組，那麼根據鄰接矩陣結構獲取圖中的邊集數組
     *
     * @return 圖的邊集數組
     */
    private Edge[] getEdges() {
        List<Edge> edges = new ArrayList<>();
        /*遍歷矩陣數組 隻需要遍歷一半就行瞭*/
        for (int i = 0; i < vertexs.length; i++) {
            for (int j = i + 1; j < vertexs.length; j++) {
                //如果存在邊
                if (matrix[i][j] != NO_EDGE && matrix[i][j] != 0) {
                    edges.add(new Edge<>(vertexs[i], vertexs[j], matrix[i][j]));
                    //edges[index++] = new Edge(vertexs[i], vertexs[j], matrix[i][j]);
                }
            }
        }
        return edges.toArray(new Edge[0]);
    }

    /**
     * Kruskal結合Prim算法.不需要知道邊集,隻需要矩陣數組,和頂點數組
     * 同樣是求最小權值的邊,但是有一個默認起點頂點,該起點可以是要求[0,頂點數量-1]之間的任意值，同時查找最小權的邊。
     * 可能會有Bug,目前未發現
     */
    public void kruskalAndPrim() {
        System.out.println("kruskalAndPrim: ");
        //已經找到的邊攜帶的頂點對應的索引將變為true,其餘未找到邊對應的頂點將是false
        boolean[] connected = new boolean[matrix.length];
        //這裡選擇第一個頂點為起點,表示以該頂點開始尋找包含該頂點的最小邊
        connected[0] = true;
        int sum = 0, n1 = 0, n2 = 0;
        //最小權值
        int min;
        while (true) {
            min = NO_EDGE;
            /*找出所有帶有已找到頂點的邊中,最小權值的邊,隻需要尋找對稱矩陣的一半即可*/
            //第一維
            for (int i = 0; i < matrix.length; i++) {
                //第二維
                for (int j = i + 1; j < matrix.length; j++) {
                    //排除等於0的,排除兩個頂點都找到瞭的,這裡實際上已經隱含瞭排除環的邏輯,如果某條邊的兩個頂點都找到瞭,那麼如果算上該條邊,肯定會形成環
                    //尋找剩下的最小的權值的邊
                    if (matrix[i][j] != 0 && connected[i] != connected[j] && matrix[i][j] < min) {
                        min = matrix[i][j];
                        n1 = i;
                        n2 = j;
                    }
                }
            }
            //如果沒找到最小權值,該圖可能不是連通圖,或者已經尋找完畢,直接返回
            if (min == NO_EDGE) {
                System.out.println(" sum:" + sum);
                return;
            }
            //已經找到的邊對應的兩個頂點都置為true
            connected[n1] = true;
            connected[n2] = true;
            //輸出找到的邊和最小權值
            System.out.println(vertexs[n1] + " ---> " + vertexs[n2] + " 權值:" + min);
            sum += min;
        }
    }


    public static void main(String[] args) {
        //頂點數組
        Character[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        //邊數組,加權值
        Edge[] edges = {
                new Edge<>('A', 'C', 1),
                new Edge<>('D', 'A', 2),
                new Edge<>('A', 'F', 3),
                new Edge<>('B', 'C', 4),
                new Edge<>('C', 'D', 5),
                new Edge<>('E', 'G', 6),
                new Edge<>('E', 'B', 7),
                new Edge<>('D', 'B', 8),
                new Edge<>('F', 'G', 9)};

        //構建圖
        MatrixPrimAndKruskal<Character> matrixPrimAndKruskal = new MatrixPrimAndKruskal<Character>(vexs, edges);
        //輸出圖
        System.out.println(matrixPrimAndKruskal);
        //深度優先遍歷
        matrixPrimAndKruskal.DFS();
        //廣度優先遍歷
        matrixPrimAndKruskal.BFS();
        //Prim算法輸出最小生成樹
        matrixPrimAndKruskal.prim();
        //Kruskal算法輸出最小生成樹
        matrixPrimAndKruskal.kruskal();
        //Kruskal算法結合Prim算法輸出最小生成樹,可能會有Bug,目前未發現
        matrixPrimAndKruskal.kruskalAndPrim();
        //獲取邊集數組
        Edge[] edges1 = matrixPrimAndKruskal.getEdges();
        System.out.println(Arrays.toString(edges1));
    }
}

/**
 * 無向加權圖鄰接表實現
 * {@link ListPrimAndKruskal#ListPrimAndKruskal(E[], Edge[])} 構建無向加權圖
 * {@link ListPrimAndKruskal#DFS()}  深度優先遍歷無向加權圖
 * {@link ListPrimAndKruskal#BFS()}  廣度優先遍歷無向加權圖
 * {@link ListPrimAndKruskal#toString()}  輸出無向加權圖
 * {@link ListPrimAndKruskal#prim()}  Prim算法實現最小生成樹
 * {@link ListPrimAndKruskal#kruskal()}   Kruskal算法實現最小生成樹
 * {@link ListPrimAndKruskal#getEdges()}  獲取邊集數組
 *
 * @author lx
 * @date 2020/5/14 23:31
 */
public class ListPrimAndKruskal<E> {
    /**
     * 頂點類
     *
     * @param <E>
     */
    private class Node<E> {
        /**
         * 頂點信息
         */
        E data;
        /**
         * 指向第一條依附該頂點的邊
         */
        LNode firstLNode;

        public Node(E data, LNode firstLNode) {
            this.data = data;
            this.firstLNode = firstLNode;
        }
    }

    /**
     * 邊表節點類
     */
    private class LNode {
        /**
         * 該邊所指向的頂點的索引位置
         */
        int vertex;
        /**
         * 該邊的權值
         */
        int weight;
        /**
         * 指向下一條邊的指針
         */
        LNode nextLNode;
    }

    /**
     * 邊對象,具有權值,在構建加權無向圖時使用
     */
    private static class Edge<E> {

        private E from;
        private E to;
        private int weight;

        public Edge(E from, E to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }

        @Override
        public String toString() {
            return "Edge{" +
                    "from=" + from +
                    ", to=" + to +
                    ", weight=" + weight +
                    '}';
        }
    }

    /**
     * 頂點數組
     */
    private Node<E>[] vertexs;


    /**
     * 邊數組
     */
    private Edge<E>[] edges;

    /**
     * 由於是加權圖,這裡設置一個邊的權值上限,任何邊的最大權值不能大於等於該值，在實際應用中，該值應該根據實際情況確定
     */
    private static final int NO_EDGE = 99;

    /**
     * 創建無向加權圖
     *
     * @param vexs  頂點數組
     * @param edges 邊二維數組
     */
    public ListPrimAndKruskal(E[] vexs, Edge<E>[] edges) {
        this.edges = edges;
        /*初始化頂點數組,並添加頂點*/
        vertexs = new Node[vexs.length];
        for (int i = 0; i < vertexs.length; i++) {
            vertexs[i] = new Node<>(vexs[i], null);
        }
        /*初始化邊表,並添加邊節點到邊表尾部,即采用尾插法*/
        for (Edge<E> edge : edges) {
            // 讀取一條邊的起始頂點和結束頂點索引值
            int p1 = getPosition(edge.from);
            int p2 = getPosition(edge.to);
            int weight = edge.weight;
            /*這裡需要相互添加邊節點,無向圖可以看作相互可達的有向圖*/
            // 初始化lnode1邊節點
            LNode lnode1 = new LNode();
            lnode1.vertex = p2;
            lnode1.weight = weight;
            // 將LNode鏈接到"p1所在鏈表的末尾"
            if (vertexs[p1].firstLNode == null) {
                vertexs[p1].firstLNode = lnode1;
            } else {
                linkLast(vertexs[p1].firstLNode, lnode1);
            }
            // 初始化lnode2邊節點
            LNode lnode2 = new LNode();
            lnode2.vertex = p1;
            lnode2.weight = weight;
            // 將lnode2鏈接到"p2所在鏈表的末尾"
            if (vertexs[p2].firstLNode == null) {
                vertexs[p2].firstLNode = lnode2;
            } else {
                linkLast(vertexs[p2].firstLNode, lnode2);
            }
        }
    }

    /**
     * 獲取某條邊的某個頂點所在頂點數組的索引位置
     *
     * @param e 頂點的值
     * @return 所在頂點數組的索引位置, 或者-1 - 表示不存在
     */
    private int getPosition(E e) {
        for (int i = 0; i < vertexs.length; i++) {
            if (vertexs[i].data == e) {
                return i;
            }
        }
        return -1;
    }


    /**
     * 將lnode節點鏈接到邊表的最後,采用尾插法
     *
     * @param first 邊表頭結點
     * @param node  將要添加的節點
     */
    private void linkLast(LNode first, LNode node) {
        while (true) {
            if (first.vertex == node.vertex) {
                return;
            }
            if (first.nextLNode == null) {
                break;
            }
            first = first.nextLNode;
        }
        first.nextLNode = node;
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < vertexs.length; i++) {
            stringBuilder.append(i).append("(").append(vertexs[i].data).append("): ");
            LNode node = vertexs[i].firstLNode;
            while (node != null) {
                stringBuilder.append(node.vertex).append("(").append(vertexs[node.vertex].data).append("-").append(node.weight).append(")");
                node = node.nextLNode;
                if (node != null) {
                    stringBuilder.append("->");
                } else {
                    break;
                }
            }
            stringBuilder.append("\n");
        }
        return stringBuilder.toString();
    }

    /**
     * 深度優先搜索遍歷圖的遞歸實現,類似於樹的先序遍歷
     * 因此模仿樹的先序遍歷,同樣借用棧結構,這裡使用的是方法的遞歸,隱式的借用棧
     *
     * @param i       頂點索引
     * @param visited 訪問標志數組
     */
    private void DFS(int i, boolean[] visited) {
        //索引索引標記為true ,表示已經訪問瞭
        visited[i] = true;
        System.out.print(vertexs[i].data + " ");
        //獲取該頂點的邊表頭結點
        LNode node = vertexs[i].firstLNode;
        //循環遍歷該頂點的鄰接點,采用同樣的方式遞歸搜索
        while (node != null) {
            if (!visited[node.vertex]) {
                DFS(node.vertex, visited);
            }
            node = node.nextLNode;
        }
    }

    /**
     * 深度優先搜索遍歷圖,類似於樹的前序遍歷,
     */
    public void DFS() {
        //新建頂點訪問標記數組,對應每個索引對應相同索引的頂點數組中的頂點
        boolean[] visited = new boolean[vertexs.length];
        //初始化所有頂點都沒有被訪問
        for (int i = 0; i < vertexs.length; i++) {
            visited[i] = false;
        }
        System.out.println("DFS: ");
        /*循環搜索*/
        for (int i = 0; i < vertexs.length; i++) {
            //如果對應索引的頂點的訪問標記為false,則搜索該頂點
            if (!visited[i]) {
                DFS(i, visited);
            }
        }
        /*走到這一步,說明頂點訪問標記數組全部為true,說明全部都訪問到瞭,深度搜索結束*/
        System.out.println();
    }

    /**
     * 廣度優先搜索圖,類似於樹的層序遍歷
     * 因此模仿樹的層序遍歷,同樣借用隊列結構
     */
    public void BFS() {
        // 輔組隊列
        Queue<Integer> indexLinkedList = new LinkedList<>();
        //新建頂點訪問標記數組,對應每個索引對應相同索引的頂點數組中的頂點
        boolean[] visited = new boolean[vertexs.length];
        //初始化所有頂點都沒有被訪問
        for (int i = 0; i < vertexs.length; i++) {
            visited[i] = false;
        }
        System.out.println("BFS: ");
        for (int i = 0; i < vertexs.length; i++) {
            //如果訪問方劑為false,則設置為true,表示已經訪問,然後開始訪問
            if (!visited[i]) {
                visited[i] = true;
                System.out.print(vertexs[i].data + " ");
                indexLinkedList.add(i);
            }
            //判斷隊列是否有值,有就開始遍歷
            if (!indexLinkedList.isEmpty()) {
                //出隊列
                Integer j = indexLinkedList.poll();
                LNode node = vertexs[j].firstLNode;
                while (node != null) {
                    int k = node.vertex;
                    if (!visited[k]) {
                        visited[k] = true;
                        System.out.print(vertexs[k].data + " ");
                        //繼續入隊列
                        indexLinkedList.add(k);
                    }
                    node = node.nextLNode;
                }
            }
        }
        System.out.println();
    }

    /**
     * Prim算法求最小生成樹
     */
    public void prim() {
        System.out.println("prim: ");
        //對應節點應該被連接的前驅節點,用來輸出
        //默認為0,即前驅結點為第一個節點
        int[] mid = new int[vertexs.length];
        int start = 0;
        int min, tmp, sum = 0;
        int num = vertexs.length;

        //頂點間邊的權值
        //存儲未連接頂點到已連接頂點的最短距離(最小權)
        int[] dis = new int[num];


        // 初始化"頂點的權值數組"，
        // 將每個頂點的權值初始化為"第start個頂點"到"該頂點"的權值。
        //首先將其他頂點到0索引頂點的權值存儲進去
        for (int i = 0; i < num; i++) {
            dis[i] = getWeight(start, i);
        }
        //如果某頂點作為末端頂點被連接，對應位置應該為true
        //第一個頂點默認被連接
        boolean[] connected = new boolean[vertexs.length];
        connected[0] = true;
        /*默認第一個頂點已經找到瞭,因此最多還要需要大循環n-1次*/
        for (int k = 1; k < num; k++) {
            min = NO_EDGE;
            //最小權值的頂點的索引
            int minIndex = 0;
            // 在未被加入到最小生成樹的頂點中，找出權值最小的頂點。
            for (int i = 1; i < vertexs.length; i++) {
                //排除已連接的頂點,排除權值等於0的值,因為這裡默認頂點指向自己的權值為0
                if (!connected[i] && dis[i] != 0 && dis[i] < min) {
                    min = dis[i];
                    minIndex = i;
                }
            }
            //如果沒找到,那麼該圖可能不是連通圖,直接返回瞭,此時最小生成樹沒啥意義
            if (minIndex == 0) {
                return;
            }
            //權值和增加
            sum += min;
            //該新連接頂點對應的索引值變成true,表示已被連接,後續判斷時跳過該頂點
            connected[minIndex] = true;
            //輸出對應的前驅頂點到該最小頂點的權值
            System.out.println(vertexs[mid[minIndex]].data + " ---> " + vertexs[minIndex].data + " 權值:" + min);
            /*在新頂點minIndex加入之前的其他所有頂點到連接頂點最小的權值已經計算過瞭
            因此隻需要更新其他頂點到新連接頂點minIndex是否還有更短的權值,有的話就更新找到距離已連接的頂點權最小的頂點*/
            for (int i = 1; i < num; i++) {
                //如果該頂點未連接
                if (!connected[i]) {
                    // 獲取minindex頂點到未連接頂點i的權值
                    tmp = getWeight(minIndex, i);
                    /*如果新頂點到未連接頂點i的權值不為0,並且比原始頂點到未連接頂點i的權值還要小,那麼更新對應位置的最小權值*/
                    if (tmp != 0 && dis[i] > tmp) {
                        dis[i] = tmp;
                        //更新前驅節點索引為新加入節點索引
                        mid[i] = minIndex;
                    }
                }
            }
        }
        System.out.println("sum: " + sum);
    }

    /**
     * 嘗試獲取邊起點start到邊終點end的邊的權值,當然可能獲取不到
     *
     * @param start 邊起點
     * @param end   邊終點
     * @return 返回權值; 如果起點和終點相同則返回0;如果邊起點和邊終點之間並沒有邊, 則返回NO_EDGE
     */
    private int getWeight(int start, int end) {
        //如果start=end，則返回0
        if (start == end) {
            return 0;
        }
        //獲取該頂點的邊表的第一個值
        LNode node = vertexs[start].firstLNode;
        //循環查找邊表,看能否找到對應的索引=end,找不到就返回NO_EDGE,表示兩個頂點未連接。
        while (node != null) {
            if (end == node.vertex) {
                return node.weight;
            }
            node = node.nextLNode;
        }
        return NO_EDGE;
    }

    /**
     * Kruskal算法求最小生成樹,可以說鄰接矩陣和鄰接鏈表的實現方式是完全一致的
     */
    public void kruskal() {
        //由於創建圖的時候保存瞭邊集數組,這裡直接使用就行瞭
        //Edge[] edges = getEdges();
        //this.edges=edges;
        //對邊集數組進行排序
        Arrays.sort(this.edges, Comparator.comparingInt(o -> o.weight));
        // 用於保存已有最小生成樹中每個頂點在該最小樹中的最終終點的索引
        int[] vends = new int[this.edges.length];
        //能夠知道終點索引范圍是[0,this.edges.length-1],因此填充edges.length表示沒有終點
        Arrays.fill(vends, this.edges.length);
        int sum = 0;
        for (Edge<E> edge : this.edges) {
            // 獲取第i條邊的起點索引from
            int from = getPosition(edge.from);
            // 獲取第i條邊的終點索引to
            int to = getPosition(edge.to);
            // 獲取頂點from在"已有的最小生成樹"中的終點
            int m = getEndIndex(vends, from);
            // 獲取頂點to在"已有的最小生成樹"中的終點
            int n = getEndIndex(vends, to);
            // 如果m!=n，意味著沒有形成環路,則可以添加,否則直接跳過,進行下一條邊的判斷
            if (m != n) {
                //添加設置原始終點索引m在已有的最小生成樹中的終點為n
                vends[m] = n;
                System.out.println(vertexs[from].data + " ---> " + vertexs[to].data + " 權值:" + edge.weight);
                sum += edge.weight;
            }
        }
        System.out.println("sum: " + sum);
        //System.out.println(Arrays.toString(this.edges));
    }

    /**
     * 獲取頂點索引i的終點如果沒有終點則返回頂點索引本身
     *
     * @param vends 頂點在最小生成樹中的終點
     * @param i     頂點索引
     * @return 頂點索引i的終點如果沒有終點則返回頂點索引本身
     */
    private int getEndIndex(int[] vends, int i) {
        //這裡使用循環查找的邏輯,尋找的是最終的終點
        while (vends[i] != this.edges.length) {
            i = vends[i];
        }
        return i;
    }

    /**
     * 如果沒有現成的邊集數組，那麼根據鄰接表結構獲取圖中的邊集數組
     *
     * @return 圖的邊集數組
     */
    private Edge[] getEdges() {
        List<Edge> edges = new ArrayList<>();
        //遍歷頂點數組
        for (int i = 0; i < vertexs.length; i++) {
            LNode node = vertexs[i].firstLNode;
            while (node != null) {
                //隻需添加起點索引小於終點索引的邊就行瞭
                if (node.vertex > i) {
                    edges.add(new Edge<>(vertexs[i].data, vertexs[node.vertex].data, node.weight));
                }
                node = node.nextLNode;
            }
        }
        return edges.toArray(new Edge[0]);
    }

    public static void main(String[] args) {
        //頂點數組
        Character[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        //邊數組,加權值
        Edge[] edges = {
                new Edge('A', 'C', 1),
                new Edge('D', 'A', 2),
                new Edge('A', 'F', 3),
                new Edge('B', 'C', 4),
                new Edge('C', 'D', 5),
                new Edge('E', 'G', 6),
                new Edge('E', 'B', 7),
                new Edge('D', 'B', 8),
                new Edge('F', 'G', 9)};
        //構建圖
        ListPrimAndKruskal<Character> listPrimAndKruskal = new ListPrimAndKruskal<Character>(vexs, edges);
        //輸出圖
        System.out.println(listPrimAndKruskal);
        //深度優先遍歷
        //DFS:
        //A C B E G F D
        listPrimAndKruskal.DFS();
        //廣度優先遍歷
        //BFS:
        //A C D F B G E
        listPrimAndKruskal.BFS();
        //Prim算法求最小生成樹
        listPrimAndKruskal.prim();
        //Kruskal算法求最小生成樹
        listPrimAndKruskal.kruskal();
        //獲取邊集數組
        Edge[] edges1 = listPrimAndKruskal.getEdges();
        System.out.println(Arrays.toString(edges1));
    }
}