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

    /**
     * 頂點(diǎn)數(shù)組
     */
    private Object[] vertexs;

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

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

    /**
     * 由于是加權(quán)圖,這里設(shè)置一個(gè)邊的權(quán)值上限,任何邊的最大權(quán)值不能大于等于該值，在實(shí)際應(yīng)用中，該值應(yīng)該根據(jù)實(shí)際情況確定
     */
    private static final int NO_EDGE = 99;


    /**
     * 邊對(duì)象,具有權(quán)值,在構(gòu)建加權(quán)無(wú)向圖時(shí)使用
     */
    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 +
                    '}';
        }
    }

    /**
     * 創(chuàng)建無(wú)向加權(quán)圖
     *
     * @param vertexs 頂點(diǎn)數(shù)組
     * @param edges   邊對(duì)象數(shù)組
     */
    public MatrixPrimAndKruskal(Object[] vertexs, Edge<E>[] edges) {
        //初始化邊數(shù)組
        this.edges = edges;
        // 初始化頂點(diǎn)數(shù)組,并添加頂點(diǎn)
        this.vertexs = Arrays.copyOf(vertexs, vertexs.length);
        // 初始化邊矩陣,并預(yù)先填充邊信息
        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) {
            // 讀取一條邊的起始頂點(diǎn)和結(jié)束頂點(diǎn)索引值
            int p1 = getPosition(edge.from);
            int p2 = getPosition(edge.to);
            //對(duì)稱(chēng)的兩個(gè)點(diǎn)位都置為edge.weight,無(wú)向圖可以看作相互可達(dá)的有向圖
            this.matrix[p1][p2] = edge.weight;
            this.matrix[p2][p1] = edge.weight;
        }
    }

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


    /**
     * 深度優(yōu)先搜索遍歷圖,類(lèi)似于樹(shù)的前序遍歷,
     */
    public void DFS() {
        //新建頂點(diǎn)訪問(wèn)標(biāo)記數(shù)組,對(duì)應(yīng)每個(gè)索引對(duì)應(yīng)相同索引的頂點(diǎn)數(shù)組中的頂點(diǎn)
        boolean[] visited = new boolean[vertexs.length];
        //初始化所有頂點(diǎn)都沒(méi)有被訪問(wèn)
        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();
    }

    /**
     * 深度優(yōu)先搜索遍歷圖的遞歸實(shí)現(xiàn),類(lèi)似于樹(shù)的先序遍歷
     * 因此模仿樹(shù)的先序遍歷,同樣借用棧結(jié)構(gòu),這里使用的是方法的遞歸,隱式的借用棧
     *
     * @param i       頂點(diǎn)索引
     * @param visited 訪問(wèn)標(biāo)志數(shù)組
     */
    private void DFS(int i, boolean[] visited) {
        visited[i] = true;
        System.out.print(vertexs[i] + " ");
        // 遍歷該頂點(diǎn)的所有鄰接點(diǎn)。若該鄰接點(diǎn)是沒(méi)有訪問(wèn)過(guò)，那么繼續(xù)遞歸遍歷領(lǐng)接點(diǎn)
        for (int w = firstVertex(i); w >= 0; w = nextVertex(i, w)) {
            if (!visited[w]) {
                DFS(w, visited);
            }
        }
    }


    /**
     * 廣度優(yōu)先搜索圖,類(lèi)似于樹(shù)的層序遍歷
     * 因此模仿樹(shù)的層序遍歷,同樣借用隊(duì)列結(jié)構(gòu)
     */
    public void BFS() {
        // 輔組隊(duì)列
        Queue<Integer> indexLinkedList = new LinkedList<>();
        //新建頂點(diǎn)訪問(wèn)標(biāo)記數(shù)組,對(duì)應(yīng)每個(gè)索引對(duì)應(yīng)相同索引的頂點(diǎn)數(shù)組中的頂點(diǎn)
        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索引出隊(duì)列
                Integer j = indexLinkedList.poll();
                //繼續(xù)訪問(wèn)j的鄰接點(diǎn)
                for (int k = firstVertex(j); k >= 0; k = nextVertex(j, k)) {
                    if (!visited[k]) {
                        visited[k] = true;
                        System.out.print(vertexs[k] + " ");
                        //繼續(xù)入隊(duì)列
                        indexLinkedList.add(k);
                    }
                }
            }
        }
        System.out.println();
    }

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

    /**
     * 返回頂點(diǎn)v相對(duì)于w的下一個(gè)鄰接頂點(diǎn)的索引，失敗則返回-1
     *
     * @param v 頂點(diǎn)索引
     * @param w 第一個(gè)鄰接點(diǎn)索引
     * @return 返回頂點(diǎn)v相對(duì)于w的下一個(gè)鄰接頂點(diǎn)的索引，失敗則返回-1
     */
    private int nextVertex(int v, int w) {
        //如果索引超出范圍,則返回-1
        if (v < 0 || v > (vertexs.length - 1) || w < 0 || w > (vertexs.length - 1)) {
            return -1;
        }
        /*根據(jù)鄰接矩陣的規(guī)律:頂點(diǎn)索引v對(duì)應(yīng)著邊二維矩陣的matrix[v][i]一行記錄
         * 由于鄰接點(diǎn)w的索引已經(jīng)獲取了,所以從i=w+1開(kāi)始尋找*/
        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算法求最小生成樹(shù)
     */
    public void prim() {
        System.out.println("prim: ");
        //對(duì)應(yīng)節(jié)點(diǎn)應(yīng)該被連接的前驅(qū)節(jié)點(diǎn),用來(lái)輸出
        //默認(rèn)為0,即前驅(qū)結(jié)點(diǎn)為第一個(gè)節(jié)點(diǎn)
        int[] mid = new int[matrix.length];
        //如果某頂點(diǎn)作為末端頂點(diǎn)被連接，對(duì)應(yīng)位置應(yīng)該為true
        //第一個(gè)頂點(diǎn)默認(rèn)被連接
        boolean[] connected = new boolean[matrix.length];
        connected[0] = true;
        //存儲(chǔ)未連接頂點(diǎn)到已連接頂點(diǎn)的最短距離(最小權(quán))
        int[] dis = new int[matrix.length];
        //首先將矩陣第一行即其他頂點(diǎn)到0索引頂點(diǎn)的權(quán)值拷貝進(jìn)去
        System.arraycopy(matrix[0], 0, dis, 0, matrix.length);
        //存儲(chǔ)路徑長(zhǎng)度
        int sum = 0;
        //最小權(quán)值
        int min;
        /*默認(rèn)第一個(gè)頂點(diǎn)已經(jīng)找到了,因此最多還要需要大循環(huán)n-1次*/
        for (int k = 1; k < matrix.length; k++) {
            min = NO_EDGE;
            //最小權(quán)值的頂點(diǎn)的索引
            int minIndex = 0;
            /*尋找權(quán)值最小的且未被連接的頂點(diǎn)索引*/
            for (int i = 1; i < matrix.length; i++) {
                //排除已連接的頂點(diǎn),排除權(quán)值等于0的值,這里權(quán)值等于0表示已生成的最小生成樹(shù)的頂點(diǎn)都未能與該頂點(diǎn)連接
                if (!connected[i] && dis[i] != 0 && dis[i] < min) {
                    min = dis[i];
                    minIndex = i;
                }
            }
            //如果沒(méi)找到,那么該圖可能不是連通圖,直接返回了,此時(shí)最小生成樹(shù)沒(méi)啥意義
            if (minIndex == 0) {
                return;
            }
            //權(quán)值和增加
            sum += min;
            //該新連接頂點(diǎn)對(duì)應(yīng)的索引值變成true,表示已被連接,后續(xù)判斷時(shí)跳過(guò)該頂點(diǎn)
            connected[minIndex] = true;
            //輸出對(duì)應(yīng)的前驅(qū)頂點(diǎn)到該最小頂點(diǎn)的權(quán)值
            System.out.println(vertexs[mid[minIndex]] + " ---> " + vertexs[minIndex] + " 權(quán)值:" + min);
            /*在新頂點(diǎn)minIndex加入之前的其他所有頂點(diǎn)到連接頂點(diǎn)最小的權(quán)值已經(jīng)計(jì)算過(guò)了
            因此只需要更新其他未連接頂點(diǎn)到新連接頂點(diǎn)minIndex是否還有更短的權(quán)值,有的話就更新找到距離已連接的頂點(diǎn)權(quán)最小的頂點(diǎn)*/
            for (int i = 1; i < matrix.length; i++) {
                //如果該頂點(diǎn)未連接
                if (!connected[i]) {
                    /*如果新頂點(diǎn)到未連接頂點(diǎn)i的權(quán)值不為0,并且比原始頂點(diǎn)到未連接頂點(diǎn)i的權(quán)值還要小,那么更新對(duì)應(yīng)位置的最小權(quán)值*/
                    if (matrix[minIndex][i] != 0 && dis[i] > matrix[minIndex][i]) {
                        //更新最小權(quán)值
                        dis[i] = matrix[minIndex][i];
                        //更新前驅(qū)節(jié)點(diǎn)索引為新加入節(jié)點(diǎn)索引
                        mid[i] = minIndex;
                    }
                }

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


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

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

    /**
     * 如果沒(méi)有現(xiàn)成的邊集數(shù)組，那么根據(jù)鄰接矩陣結(jié)構(gòu)獲取圖中的邊集數(shù)組
     *
     * @return 圖的邊集數(shù)組
     */
    private Edge[] getEdges() {
        List<Edge> edges = new ArrayList<>();
        /*遍歷矩陣數(shù)組 只需要遍歷一半就行了*/
        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結(jié)合Prim算法.不需要知道邊集,只需要矩陣數(shù)組,和頂點(diǎn)數(shù)組
     * 同樣是求最小權(quán)值的邊,但是有一個(gè)默認(rèn)起點(diǎn)頂點(diǎn),該起點(diǎn)可以是要求[0,頂點(diǎn)數(shù)量-1]之間的任意值，同時(shí)查找最小權(quán)的邊。
     * 可能會(huì)有Bug,目前未發(fā)現(xiàn)
     */
    public void kruskalAndPrim() {
        System.out.println("kruskalAndPrim: ");
        //已經(jīng)找到的邊攜帶的頂點(diǎn)對(duì)應(yīng)的索引將變?yōu)閠rue,其余未找到邊對(duì)應(yīng)的頂點(diǎn)將是false
        boolean[] connected = new boolean[matrix.length];
        //這里選擇第一個(gè)頂點(diǎn)為起點(diǎn),表示以該頂點(diǎn)開(kāi)始尋找包含該頂點(diǎn)的最小邊
        connected[0] = true;
        int sum = 0, n1 = 0, n2 = 0;
        //最小權(quán)值
        int min;
        while (true) {
            min = NO_EDGE;
            /*找出所有帶有已找到頂點(diǎn)的邊中,最小權(quán)值的邊,只需要尋找對(duì)稱(chēng)矩陣的一半即可*/
            //第一維
            for (int i = 0; i < matrix.length; i++) {
                //第二維
                for (int j = i + 1; j < matrix.length; j++) {
                    //排除等于0的,排除兩個(gè)頂點(diǎn)都找到了的,這里實(shí)際上已經(jīng)隱含了排除環(huán)的邏輯,如果某條邊的兩個(gè)頂點(diǎn)都找到了,那么如果算上該條邊,肯定會(huì)形成環(huán)
                    //尋找剩下的最小的權(quán)值的邊
                    if (matrix[i][j] != 0 && connected[i] != connected[j] && matrix[i][j] < min) {
                        min = matrix[i][j];
                        n1 = i;
                        n2 = j;
                    }
                }
            }
            //如果沒(méi)找到最小權(quán)值,該圖可能不是連通圖,或者已經(jīng)尋找完畢,直接返回
            if (min == NO_EDGE) {
                System.out.println(" sum:" + sum);
                return;
            }
            //已經(jīng)找到的邊對(duì)應(yīng)的兩個(gè)頂點(diǎn)都置為true
            connected[n1] = true;
            connected[n2] = true;
            //輸出找到的邊和最小權(quán)值
            System.out.println(vertexs[n1] + " ---> " + vertexs[n2] + " 權(quán)值:" + min);
            sum += min;
        }
    }


    public static void main(String[] args) {
        //頂點(diǎn)數(shù)組
        Character[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        //邊數(shù)組,加權(quán)值
        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)};

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

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

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

    /**
     * 邊表節(jié)點(diǎn)類(lèi)
     */
    private class LNode {
        /**
         * 該邊所指向的頂點(diǎn)的索引位置
         */
        int vertex;
        /**
         * 該邊的權(quán)值
         */
        int weight;
        /**
         * 指向下一條邊的指針
         */
        LNode nextLNode;
    }

    /**
     * 邊對(duì)象,具有權(quán)值,在構(gòu)建加權(quán)無(wú)向圖時(shí)使用
     */
    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 +
                    '}';
        }
    }

    /**
     * 頂點(diǎn)數(shù)組
     */
    private Node<E>[] vertexs;


    /**
     * 邊數(shù)組
     */
    private Edge<E>[] edges;

    /**
     * 由于是加權(quán)圖,這里設(shè)置一個(gè)邊的權(quán)值上限,任何邊的最大權(quán)值不能大于等于該值，在實(shí)際應(yīng)用中，該值應(yīng)該根據(jù)實(shí)際情況確定
     */
    private static final int NO_EDGE = 99;

    /**
     * 創(chuàng)建無(wú)向加權(quán)圖
     *
     * @param vexs  頂點(diǎn)數(shù)組
     * @param edges 邊二維數(shù)組
     */
    public ListPrimAndKruskal(E[] vexs, Edge<E>[] edges) {
        this.edges = edges;
        /*初始化頂點(diǎn)數(shù)組,并添加頂點(diǎn)*/
        vertexs = new Node[vexs.length];
        for (int i = 0; i < vertexs.length; i++) {
            vertexs[i] = new Node<>(vexs[i], null);
        }
        /*初始化邊表,并添加邊節(jié)點(diǎn)到邊表尾部,即采用尾插法*/
        for (Edge<E> edge : edges) {
            // 讀取一條邊的起始頂點(diǎn)和結(jié)束頂點(diǎn)索引值
            int p1 = getPosition(edge.from);
            int p2 = getPosition(edge.to);
            int weight = edge.weight;
            /*這里需要相互添加邊節(jié)點(diǎn),無(wú)向圖可以看作相互可達(dá)的有向圖*/
            // 初始化lnode1邊節(jié)點(diǎn)
            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邊節(jié)點(diǎn)
            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);
            }
        }
    }

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


    /**
     * 將lnode節(jié)點(diǎn)鏈接到邊表的最后,采用尾插法
     *
     * @param first 邊表頭結(jié)點(diǎn)
     * @param node  將要添加的節(jié)點(diǎn)
     */
    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();
    }

    /**
     * 深度優(yōu)先搜索遍歷圖的遞歸實(shí)現(xiàn),類(lèi)似于樹(shù)的先序遍歷
     * 因此模仿樹(shù)的先序遍歷,同樣借用棧結(jié)構(gòu),這里使用的是方法的遞歸,隱式的借用棧
     *
     * @param i       頂點(diǎn)索引
     * @param visited 訪問(wèn)標(biāo)志數(shù)組
     */
    private void DFS(int i, boolean[] visited) {
        //索引索引標(biāo)記為true ,表示已經(jīng)訪問(wèn)了
        visited[i] = true;
        System.out.print(vertexs[i].data + " ");
        //獲取該頂點(diǎn)的邊表頭結(jié)點(diǎn)
        LNode node = vertexs[i].firstLNode;
        //循環(huán)遍歷該頂點(diǎn)的鄰接點(diǎn),采用同樣的方式遞歸搜索
        while (node != null) {
            if (!visited[node.vertex]) {
                DFS(node.vertex, visited);
            }
            node = node.nextLNode;
        }
    }

    /**
     * 深度優(yōu)先搜索遍歷圖,類(lèi)似于樹(shù)的前序遍歷,
     */
    public void DFS() {
        //新建頂點(diǎn)訪問(wèn)標(biāo)記數(shù)組,對(duì)應(yīng)每個(gè)索引對(duì)應(yīng)相同索引的頂點(diǎn)數(shù)組中的頂點(diǎn)
        boolean[] visited = new boolean[vertexs.length];
        //初始化所有頂點(diǎn)都沒(méi)有被訪問(wèn)
        for (int i = 0; i < vertexs.length; i++) {
            visited[i] = false;
        }
        System.out.println("DFS: ");
        /*循環(huán)搜索*/
        for (int i = 0; i < vertexs.length; i++) {
            //如果對(duì)應(yīng)索引的頂點(diǎn)的訪問(wèn)標(biāo)記為false,則搜索該頂點(diǎn)
            if (!visited[i]) {
                DFS(i, visited);
            }
        }
        /*走到這一步,說(shuō)明頂點(diǎn)訪問(wèn)標(biāo)記數(shù)組全部為true,說(shuō)明全部都訪問(wèn)到了,深度搜索結(jié)束*/
        System.out.println();
    }

    /**
     * 廣度優(yōu)先搜索圖,類(lèi)似于樹(shù)的層序遍歷
     * 因此模仿樹(shù)的層序遍歷,同樣借用隊(duì)列結(jié)構(gòu)
     */
    public void BFS() {
        // 輔組隊(duì)列
        Queue<Integer> indexLinkedList = new LinkedList<>();
        //新建頂點(diǎn)訪問(wèn)標(biāo)記數(shù)組,對(duì)應(yīng)每個(gè)索引對(duì)應(yīng)相同索引的頂點(diǎn)數(shù)組中的頂點(diǎn)
        boolean[] visited = new boolean[vertexs.length];
        //初始化所有頂點(diǎn)都沒(méi)有被訪問(wèn)
        for (int i = 0; i < vertexs.length; i++) {
            visited[i] = false;
        }
        System.out.println("BFS: ");
        for (int i = 0; i < vertexs.length; i++) {
            //如果訪問(wèn)方劑為false,則設(shè)置為true,表示已經(jīng)訪問(wèn),然后開(kāi)始訪問(wèn)
            if (!visited[i]) {
                visited[i] = true;
                System.out.print(vertexs[i].data + " ");
                indexLinkedList.add(i);
            }
            //判斷隊(duì)列是否有值,有就開(kāi)始遍歷
            if (!indexLinkedList.isEmpty()) {
                //出隊(duì)列
                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 + " ");
                        //繼續(xù)入隊(duì)列
                        indexLinkedList.add(k);
                    }
                    node = node.nextLNode;
                }
            }
        }
        System.out.println();
    }

    /**
     * Prim算法求最小生成樹(shù)
     */
    public void prim() {
        System.out.println("prim: ");
        //對(duì)應(yīng)節(jié)點(diǎn)應(yīng)該被連接的前驅(qū)節(jié)點(diǎn),用來(lái)輸出
        //默認(rèn)為0,即前驅(qū)結(jié)點(diǎn)為第一個(gè)節(jié)點(diǎn)
        int[] mid = new int[vertexs.length];
        int start = 0;
        int min, tmp, sum = 0;
        int num = vertexs.length;

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


        // 初始化"頂點(diǎn)的權(quán)值數(shù)組"，
        // 將每個(gè)頂點(diǎn)的權(quán)值初始化為"第start個(gè)頂點(diǎn)"到"該頂點(diǎn)"的權(quán)值。
        //首先將其他頂點(diǎn)到0索引頂點(diǎn)的權(quán)值存儲(chǔ)進(jìn)去
        for (int i = 0; i < num; i++) {
            dis[i] = getWeight(start, i);
        }
        //如果某頂點(diǎn)作為末端頂點(diǎn)被連接，對(duì)應(yīng)位置應(yīng)該為true
        //第一個(gè)頂點(diǎn)默認(rèn)被連接
        boolean[] connected = new boolean[vertexs.length];
        connected[0] = true;
        /*默認(rèn)第一個(gè)頂點(diǎn)已經(jīng)找到了,因此最多還要需要大循環(huán)n-1次*/
        for (int k = 1; k < num; k++) {
            min = NO_EDGE;
            //最小權(quán)值的頂點(diǎn)的索引
            int minIndex = 0;
            // 在未被加入到最小生成樹(shù)的頂點(diǎn)中，找出權(quán)值最小的頂點(diǎn)。
            for (int i = 1; i < vertexs.length; i++) {
                //排除已連接的頂點(diǎn),排除權(quán)值等于0的值,因?yàn)檫@里默認(rèn)頂點(diǎn)指向自己的權(quán)值為0
                if (!connected[i] && dis[i] != 0 && dis[i] < min) {
                    min = dis[i];
                    minIndex = i;
                }
            }
            //如果沒(méi)找到,那么該圖可能不是連通圖,直接返回了,此時(shí)最小生成樹(shù)沒(méi)啥意義
            if (minIndex == 0) {
                return;
            }
            //權(quán)值和增加
            sum += min;
            //該新連接頂點(diǎn)對(duì)應(yīng)的索引值變成true,表示已被連接,后續(xù)判斷時(shí)跳過(guò)該頂點(diǎn)
            connected[minIndex] = true;
            //輸出對(duì)應(yīng)的前驅(qū)頂點(diǎn)到該最小頂點(diǎn)的權(quán)值
            System.out.println(vertexs[mid[minIndex]].data + " ---> " + vertexs[minIndex].data + " 權(quán)值:" + min);
            /*在新頂點(diǎn)minIndex加入之前的其他所有頂點(diǎn)到連接頂點(diǎn)最小的權(quán)值已經(jīng)計(jì)算過(guò)了
            因此只需要更新其他頂點(diǎn)到新連接頂點(diǎn)minIndex是否還有更短的權(quán)值,有的話就更新找到距離已連接的頂點(diǎn)權(quán)最小的頂點(diǎn)*/
            for (int i = 1; i < num; i++) {
                //如果該頂點(diǎn)未連接
                if (!connected[i]) {
                    // 獲取minindex頂點(diǎn)到未連接頂點(diǎn)i的權(quán)值
                    tmp = getWeight(minIndex, i);
                    /*如果新頂點(diǎn)到未連接頂點(diǎn)i的權(quán)值不為0,并且比原始頂點(diǎn)到未連接頂點(diǎn)i的權(quán)值還要小,那么更新對(duì)應(yīng)位置的最小權(quán)值*/
                    if (tmp != 0 && dis[i] > tmp) {
                        dis[i] = tmp;
                        //更新前驅(qū)節(jié)點(diǎn)索引為新加入節(jié)點(diǎn)索引
                        mid[i] = minIndex;
                    }
                }
            }
        }
        System.out.println("sum: " + sum);
    }

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

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

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

    /**
     * 如果沒(méi)有現(xiàn)成的邊集數(shù)組，那么根據(jù)鄰接表結(jié)構(gòu)獲取圖中的邊集數(shù)組
     *
     * @return 圖的邊集數(shù)組
     */
    private Edge[] getEdges() {
        List<Edge> edges = new ArrayList<>();
        //遍歷頂點(diǎn)數(shù)組
        for (int i = 0; i < vertexs.length; i++) {
            LNode node = vertexs[i].firstLNode;
            while (node != null) {
                //只需添加起點(diǎn)索引小于終點(diǎn)索引的邊就行了
                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) {
        //頂點(diǎn)數(shù)組
        Character[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        //邊數(shù)組,加權(quán)值
        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)};
        //構(gòu)建圖
        ListPrimAndKruskal<Character> listPrimAndKruskal = new ListPrimAndKruskal<Character>(vexs, edges);
        //輸出圖
        System.out.println(listPrimAndKruskal);
        //深度優(yōu)先遍歷
        //DFS:
        //A C B E G F D
        listPrimAndKruskal.DFS();
        //廣度優(yōu)先遍歷
        //BFS:
        //A C D F B G E
        listPrimAndKruskal.BFS();
        //Prim算法求最小生成樹(shù)
        listPrimAndKruskal.prim();
        //Kruskal算法求最小生成樹(shù)
        listPrimAndKruskal.kruskal();
        //獲取邊集數(shù)組
        Edge[] edges1 = listPrimAndKruskal.getEdges();
        System.out.println(Arrays.toString(edges1));
    }
}