/**
 * 無(wú)向加權(quán)圖鄰接矩陣實(shí)現(xiàn)
 * {@link MatrixDijkstraAndFloyd#MatrixDijkstraAndFloyd(Object[], Edge[])}  構(gòu)建無(wú)向加權(quán)圖
 * {@link MatrixDijkstraAndFloyd#DFS()}  深度優(yōu)先遍歷無(wú)向加權(quán)圖
 * {@link MatrixDijkstraAndFloyd#BFS()}  廣度優(yōu)先遍歷無(wú)向加權(quán)圖
 * {@link MatrixDijkstraAndFloyd#toString()}  輸出無(wú)向加權(quán)圖
 * {@link MatrixDijkstraAndFloyd#prim()}  Prim算法實(shí)現(xiàn)最小生成樹
 * {@link MatrixDijkstraAndFloyd#kruskal()}   Kruskal算法實(shí)現(xiàn)最小生成樹
 * {@link MatrixDijkstraAndFloyd#kruskalAndPrim()}  Kruskal算法結(jié)合Prim算法實(shí)現(xiàn)最小生成樹
 * {@link MatrixDijkstraAndFloyd#getEdges()}  獲取邊集數(shù)組
 * {@link MatrixDijkstraAndFloyd#dijkstra(int)} ()}  Dijkstra算法獲取指定頂點(diǎn)到所有頂點(diǎn)的最短路徑
 * {@link MatrixDijkstraAndFloyd#dijkstra(int, int)} Dijkstra算法獲取指定頂點(diǎn)到指定頂點(diǎn)的最短路徑
 * {@link MatrixDijkstraAndFloyd#floyd()} Floyd獲取所有頂點(diǎn)到所有頂點(diǎn)的最短路徑
 *
 * @author lx
 */
public class MatrixDijkstraAndFloyd<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 MatrixDijkstraAndFloyd(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ì)稱的兩個(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)先搜索遍歷圖,類似于樹的前序遍歷,
     */
    public void DFS() {
        //新建頂點(diǎn)訪問標(biāo)記數(shù)組,對(duì)應(yīng)每個(gè)索引對(duì)應(yīng)相同索引的頂點(diǎn)數(shù)組中的頂點(diǎn)
        boolean[] visited = new boolean[vertexs.length];
        //初始化所有頂點(diǎn)都沒有被訪問
        for (int i = 0; i < vertexs.length; i++) {
            visited[i] = false;
        }
        System.out.println("DFS: ");
        System.out.print("\t");
        for (int i = 0; i < vertexs.length; i++) {
            if (!visited[i]) {
                DFS(i, visited);
            }
        }
        System.out.println();
    }

    /**
     * 深度優(yōu)先搜索遍歷圖的遞歸實(shí)現(xiàn),類似于樹的先序遍歷
     * 因此模仿樹的先序遍歷,同樣借用棧結(jié)構(gòu),這里使用的是方法的遞歸,隱式的借用棧
     *
     * @param i       頂點(diǎn)索引
     * @param visited 訪問標(biāo)志數(shù)組
     */
    private void DFS(int i, boolean[] visited) {
        visited[i] = true;
        System.out.print(vertexs[i] + " ");
        // 遍歷該頂點(diǎn)的所有鄰接點(diǎn)。若該鄰接點(diǎ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)先搜索圖,類似于樹的層序遍歷
     * 因此模仿樹的層序遍歷,同樣借用隊(duì)列結(jié)構(gòu)
     */
    public void BFS() {
        // 輔組隊(duì)列
        Queue<Integer> indexLinkedList = new LinkedList<>();
        //新建頂點(diǎ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: ");
        System.out.print("\t");
        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ù)訪問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開始*/
        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開始尋找*/
        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: ");
        //對(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表示已生成的最小生成樹的頂點(diǎn)都未能與該頂點(diǎn)連接
                if (!connected[i] && dis[i] != 0 && dis[i] < min) {
                    min = dis[i];
                    minIndex = i;
                }
            }
            //如果沒找到,那么該圖可能不是連通圖,直接返回了,此時(shí)最小生成樹沒啥意義
            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("\t" + 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("\t" + "sum: " + sum);
    }


    /**
     * Kruskal算法求最小生成樹傳統(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));
        // 用于保存已有最小生成樹中每個(gè)頂點(diǎn)在該最小樹中的最終終點(diǎn)的索引
        int[] vends = new int[this.edges.length];
        //能夠知道終點(diǎn)索引范圍是[0,this.edges.length-1],因此填充edges.length表示沒有終點(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在"已有的最小生成樹"中的終點(diǎn)
            int m = getEndIndex(vends, from);
            // 獲取頂點(diǎn)to在"已有的最小生成樹"中的終點(diǎn)
            int n = getEndIndex(vends, to);
            // 如果m!=n，意味著沒有形成環(huán)路,則可以添加,否則直接跳過(guò),進(jìn)行下一條邊的判斷
            if (m != n) {
                //添加設(shè)置原始終點(diǎn)索引m在已有的最小生成樹中的終點(diǎn)為n
                vends[m] = n;
                System.out.println("\t" + vertexs[from] + " ---> " + vertexs[to] + " 權(quán)值:" + edge.weight);
                sum += edge.weight;
            }
        }
        System.out.println("\t" + "sum: " + sum);
        //System.out.println(Arrays.toString(this.edges));
    }

    /**
     * 獲取頂點(diǎn)索引i的終點(diǎn)如果沒有終點(diǎn)則返回頂點(diǎn)索引本身
     *
     * @param vends 頂點(diǎn)在最小生成樹中的終點(diǎn)
     * @param i     頂點(diǎn)索引
     * @return 頂點(diǎn)索引i的終點(diǎn)如果沒有終點(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;
    }

    /**
     * 如果沒有現(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)開始尋找包含該頂點(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ì)稱矩陣的一半即可*/
            //第一維
            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;
                    }
                }
            }
            //如果沒找到最小權(quán)值,該圖可能不是連通圖,或者已經(jīng)尋找完畢,直接返回
            if (min == NO_EDGE) {
                System.out.println("\t" + "sum:" + sum);
                return;
            }
            //已經(jīng)找到的邊對(duì)應(yīng)的兩個(gè)頂點(diǎn)都置為true
            connected[n1] = true;
            connected[n2] = true;
            //輸出找到的邊和最小權(quán)值
            System.out.println("\t" + vertexs[n1] + " ---> " + vertexs[n2] + " 權(quán)值:" + min);
            sum += min;
        }
    }


    /**
     * Dijkstra算法求最短路徑。
     *
     * @param start 起始頂點(diǎn)索引。即計(jì)算"頂點(diǎn)vs"到其它頂點(diǎn)的最短路徑。
     */
    public void dijkstra(int start) {
        checkIndex(start);
        int[] shortestPathance = getShortestDistance(start, vertexs.length);
        // 打印Dijkstra最短路徑的結(jié)果
        System.out.println("Dijkstra(" + vertexs[start] + "):");
        for (int i = 0; i < vertexs.length; i++) {
            System.out.println("\t(" + vertexs[start] + " ---> " + vertexs[i] + ")最短路徑:" + shortestPathance[i]);
        }
    }

    /**
     * Dijkstra算法求最短路徑
     *
     * @param start 起始點(diǎn)
     * @param end   終點(diǎn),如果end=vertexs.length說(shuō)明是遍歷查找所有的最短路徑
     * @return 起始頂點(diǎn)到其他點(diǎn)或者指定點(diǎn)的最短權(quán)值
     */
    private int[] getShortestDistance(int start, int end) {
        /*1、該數(shù)組存放起始頂點(diǎn)到其他點(diǎn)的權(quán)值*/
        int[] shortestPathance = new int[vertexs.length];
        //初始化數(shù)據(jù)
        //首先設(shè)置起始點(diǎn)到頂點(diǎn)i到的最短路徑為起始點(diǎn)到頂點(diǎn)i的權(quán)。
        System.arraycopy(matrix[start], 0, shortestPathance, 0, matrix.length);

        /*2、標(biāo)志位數(shù)組.某個(gè)位置如果為true表示對(duì)應(yīng)位置的頂點(diǎn)到起始頂點(diǎn)的最短路徑已成功獲取。*/
        boolean[] shortest = new boolean[vertexs.length];
        //首先設(shè)置起始點(diǎn)到自己的的路徑已經(jīng)找到了,為0
        shortest[start] = true;

        /*3、最多遍歷vertexs.length-1次；每次找出起始點(diǎn)到一個(gè)頂點(diǎn)的最短路徑。*/
        int k;
        int min;
        for (int i = 1; i < vertexs.length; i++) {
            k = 0;
            // 尋找當(dāng)前最小的路徑；
            min = NO_EDGE;
            for (int j = 0; j < vertexs.length; j++) {
                //排除已經(jīng)找到的最短路徑之后，找到離start最近的頂點(diǎn)(k)。
                if (!shortest[j] && shortestPathance[j] < min) {
                    min = shortestPathance[j];
                    k = j;
                }
            }
            //先設(shè)置起始點(diǎn)到新頂點(diǎn)k的最短路徑已經(jīng)找到
            shortest[k] = true;
            if (end != vertexs.length && k == end) {
                break;
            }
            //更新未獲取最短路徑的頂點(diǎn)的最短路徑,因?yàn)槠渌颜业降捻旤c(diǎn)的最短路徑已經(jīng)找到了,這里指需要更新新加入的已找到的可達(dá)頂點(diǎn)的路徑.
            for (int j = 0; j < vertexs.length; j++) {
                int tmp = matrix[k][j];
                //排除已經(jīng)找到的最短路徑，排除未連接的路徑，排除等于0的路徑（連接自己）之后
                //找到離start最如果新的最短路徑比以前的最短路徑還要短，則更新最短路徑。
                if (!shortest[j] && tmp != NO_EDGE && tmp != 0 && ((tmp = min + tmp) < shortestPathance[j])) {
                    shortestPathance[j] = tmp;
                }
            }
        }
        return shortestPathance;
    }

    /**
     * 索引檢查
     *
     * @param index 多個(gè)索引
     */
    private void checkIndex(int... index) {
        for (int i : index) {
            if (i < 0 || i >= vertexs.length) {
                throw new ArrayIndexOutOfBoundsException("索引越界:" + i);
            }
        }
    }

    /**
     * Dijkstra算法求最短路徑。
     *
     * @param start 起始頂點(diǎn)索引。
     * @param end   結(jié)束點(diǎn)索引
     */
    public void dijkstra(int start, int end) {
        checkIndex(start, end);
        int[] shortestPathance = getShortestDistance(start, end);
        // 打印Dijkstra最短路徑的結(jié)果
        System.out.println("Dijkstra(" + vertexs[start] + " ---> " + vertexs[end] + ")最短路徑:" + shortestPathance[end]);
    }


    /**
     * Floyd算法獲取所有頂點(diǎn)到所有頂點(diǎn)的最短路徑,代碼很簡(jiǎn)單,思想很巧妙
     */
    public void floyd() {
        //路徑矩陣(兩頂點(diǎn)最短路徑,即最小權(quán)值)
        int[][] shortestPath = new int[matrix.length][matrix.length];
        /*初始化數(shù)據(jù)*/
        for (int i = 0; i < matrix.length; i++) {
            System.arraycopy(matrix[i], 0, shortestPath[i], 0, vertexs.length);
        }
        // 計(jì)算最短路徑
        for (int k = 0; k < matrix.length; k++) {
            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix.length; j++) {
                    //要求經(jīng)過(guò)下標(biāo)k頂點(diǎn)的兩個(gè)路徑都不能等于NO_EDGE,否則就是沒有路徑,NO_EDGE應(yīng)該選取的足夠的大,否則可能出錯(cuò)
                    int tmp = (shortestPath[i][k] == NO_EDGE || shortestPath[k][j] == NO_EDGE) ? NO_EDGE : (shortestPath[i][k] + shortestPath[k][j]);
                    // 如果經(jīng)過(guò)下標(biāo)為k頂點(diǎn)路徑比原兩點(diǎn)間路徑更短，則更新shortestPath[i][j]
                    if (shortestPath[i][j] > tmp) {
                        // i到j(luò)最短路徑對(duì)應(yīng)的值設(shè)為經(jīng)過(guò)k的更小的一個(gè)
                        shortestPath[i][j] = tmp;
                    }

                }
            }
        }
        /*輸出路徑矩陣*/
        System.out.println("Floyd: ");
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix.length; j++) {
                System.out.print("\t" + shortestPath[i][j]);
            }
            System.out.println();
        }
    }


    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', 8),
                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', 9),
                new Edge<>('F', 'G', 9)};

        //構(gòu)建圖
        MatrixDijkstraAndFloyd<Character> matrixDijkstraAndFloyd = new MatrixDijkstraAndFloyd<Character>(vexs, edges);
        //輸出圖
        System.out.println(matrixDijkstraAndFloyd);
        //深度優(yōu)先遍歷
        matrixDijkstraAndFloyd.DFS();
        //廣度優(yōu)先遍歷
        matrixDijkstraAndFloyd.BFS();
        //Prim算法輸出最小生成樹
        matrixDijkstraAndFloyd.prim();
        //Kruskal算法輸出最小生成樹
        matrixDijkstraAndFloyd.kruskal();
        //Kruskal算法結(jié)合Prim算法輸出最小生成樹,可能會(huì)有Bug,目前未發(fā)現(xiàn)
        matrixDijkstraAndFloyd.kruskalAndPrim();


        // Dijkstra算法獲取某個(gè)索引的頂點(diǎn)到其它各個(gè)頂點(diǎn)的最短距離
        // 這里參數(shù)是索引,也可以是一個(gè)頂點(diǎn),需要稍微修改代碼獲取頂點(diǎn)的索引,比較簡(jiǎn)單這里就不做了
        matrixDijkstraAndFloyd.dijkstra(0);
        // Dijkstra算法獲取一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的最短距離
        matrixDijkstraAndFloyd.dijkstra(2, 0);

        // Floyd算法獲取所有頂點(diǎn)到所有頂點(diǎn)的最短路徑
        matrixDijkstraAndFloyd.floyd();
    }
}

/**
 * 無(wú)向加權(quán)圖鄰接表實(shí)現(xiàn)
 * {@link ListDijkstraAndFloyd#ListDijkstraAndFloyd(Object[], Edge[])} 構(gòu)建無(wú)向加權(quán)圖
 * {@link ListDijkstraAndFloyd#DFS()}  深度優(yōu)先遍歷無(wú)向加權(quán)圖
 * {@link ListDijkstraAndFloyd#BFS()}  廣度優(yōu)先遍歷無(wú)向加權(quán)圖
 * {@link ListDijkstraAndFloyd#toString()}  輸出無(wú)向加權(quán)圖
 * {@link ListDijkstraAndFloyd#prim()}  Prim算法實(shí)現(xiàn)最小生成樹
 * {@link ListDijkstraAndFloyd#kruskal()}   Kruskal算法實(shí)現(xiàn)最小生成樹
 * {@link ListDijkstraAndFloyd#getEdges()}  獲取邊集數(shù)組
 * {@link ListDijkstraAndFloyd#dijkstra(int)} ()}  獲取指定頂點(diǎn)到所有頂點(diǎn)的最短路徑
 * {@link ListDijkstraAndFloyd#dijkstra(int, int)} 獲取指定頂點(diǎn)到指定頂點(diǎn)的最短路徑
 * {@link ListDijkstraAndFloyd#floyd()} Floyd獲取所有頂點(diǎn)到所有頂點(diǎn)的最短路徑
 *
 * @author lx
 */
public class ListDijkstraAndFloyd<E> {
    /**
     * 頂點(diǎn)類
     *
     * @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)類
     */
    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 ListDijkstraAndFloyd(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),類似于樹的先序遍歷
     * 因此模仿樹的先序遍歷,同樣借用棧結(jié)構(gòu),這里使用的是方法的遞歸,隱式的借用棧
     *
     * @param i       頂點(diǎn)索引
     * @param visited 訪問標(biāo)志數(shù)組
     */
    private void DFS(int i, boolean[] visited) {
        //索引索引標(biāo)記為true ,表示已經(jīng)訪問了
        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)先搜索遍歷圖,類似于樹的前序遍歷,
     */
    public void DFS() {
        //新建頂點(diǎn)訪問標(biāo)記數(shù)組,對(duì)應(yīng)每個(gè)索引對(duì)應(yīng)相同索引的頂點(diǎn)數(shù)組中的頂點(diǎn)
        boolean[] visited = new boolean[vertexs.length];
        //初始化所有頂點(diǎn)都沒有被訪問
        for (int i = 0; i < vertexs.length; i++) {
            visited[i] = false;
        }
        System.out.println("DFS: ");
        System.out.print("\t");
        /*循環(huán)搜索*/
        for (int i = 0; i < vertexs.length; i++) {
            //如果對(duì)應(yīng)索引的頂點(diǎn)的訪問標(biāo)記為false,則搜索該頂點(diǎn)
            if (!visited[i]) {
                DFS(i, visited);
            }
        }
        /*走到這一步,說(shuō)明頂點(diǎn)訪問標(biāo)記數(shù)組全部為true,說(shuō)明全部都訪問到了,深度搜索結(jié)束*/
        System.out.println();
    }

    /**
     * 廣度優(yōu)先搜索圖,類似于樹的層序遍歷
     * 因此模仿樹的層序遍歷,同樣借用隊(duì)列結(jié)構(gòu)
     */
    public void BFS() {
        // 輔組隊(duì)列
        Queue<Integer> indexLinkedList = new LinkedList<>();
        //新建頂點(diǎn)訪問標(biāo)記數(shù)組,對(duì)應(yīng)每個(gè)索引對(duì)應(yīng)相同索引的頂點(diǎn)數(shù)組中的頂點(diǎn)
        boolean[] visited = new boolean[vertexs.length];
        //初始化所有頂點(diǎn)都沒有被訪問
        for (int i = 0; i < vertexs.length; i++) {
            visited[i] = false;
        }
        System.out.println("BFS: ");
        System.out.print("\t");
        for (int i = 0; i < vertexs.length; i++) {
            //如果訪問方劑為false,則設(shè)置為true,表示已經(jīng)訪問,然后開始訪問
            if (!visited[i]) {
                visited[i] = true;
                System.out.print(vertexs[i].data + " ");
                indexLinkedList.add(i);
            }
            //判斷隊(duì)列是否有值,有就開始遍歷
            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算法求最小生成樹
     */
    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;
            // 在未被加入到最小生成樹的頂點(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;
                }
            }
            //如果沒找到,那么該圖可能不是連通圖,直接返回了,此時(shí)最小生成樹沒啥意義
            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("\t" + 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("\t" + "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)之間并沒有邊, 則返回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算法求最小生成樹,可以說(shuō)鄰接矩陣和鄰接鏈表的實(shí)現(xiàn)方式是完全一致的
     */
    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));
        // 用于保存已有最小生成樹中每個(gè)頂點(diǎn)在該最小樹中的最終終點(diǎn)的索引
        int[] vends = new int[this.edges.length];
        //能夠知道終點(diǎn)索引范圍是[0,this.edges.length-1],因此填充edges.length表示沒有終點(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在"已有的最小生成樹"中的終點(diǎn)
            int m = getEndIndex(vends, from);
            // 獲取頂點(diǎn)to在"已有的最小生成樹"中的終點(diǎn)
            int n = getEndIndex(vends, to);
            // 如果m!=n，意味著沒有形成環(huán)路,則可以添加,否則直接跳過(guò),進(jìn)行下一條邊的判斷
            if (m != n) {
                //添加設(shè)置原始終點(diǎn)索引m在已有的最小生成樹中的終點(diǎn)為n
                vends[m] = n;
                System.out.println("\t" + vertexs[from].data + " ---> " + vertexs[to].data + " 權(quán)值:" + edge.weight);
                sum += edge.weight;
            }
        }
        System.out.println("\t" + "sum: " + sum);
        //System.out.println(Arrays.toString(this.edges));
    }

    /**
     * 獲取頂點(diǎn)索引i的終點(diǎn)如果沒有終點(diǎn)則返回頂點(diǎn)索引本身
     *
     * @param vends 頂點(diǎn)在最小生成樹中的終點(diǎn)
     * @param i     頂點(diǎn)索引
     * @return 頂點(diǎn)索引i的終點(diǎn)如果沒有終點(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;
    }

    /**
     * 如果沒有現(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]);
    }

    /**
     * Dijkstra算法求最短路徑。
     *
     * @param start 起始頂點(diǎn)索引。即計(jì)算"頂點(diǎn)vs"到其它頂點(diǎn)的最短路徑。
     */
    public void dijkstra(int start) {
        checkIndex(start);
        int[] distance = getShortestDistance(start, vertexs.length);
        // 打印dijkstra最短路徑的結(jié)果
        System.out.println("dijkstra(" + vertexs[start].data + "):");
        for (int i = 0; i < vertexs.length; i++) {
            System.out.println("\t(" + vertexs[start].data + " ---> " + vertexs[i].data + ")最短路徑:" + distance[i]);
        }
    }

    /**
     * Dijkstra算法求最短路徑。
     *
     * @param start 起始頂點(diǎn)索引。
     * @param end   結(jié)束點(diǎn)索引
     */
    public void dijkstra(int start, int end) {
        checkIndex(start, end);
        int[] shortestPathance = getShortestDistance(start, end);
        // 打印dijkstra最短路徑的結(jié)果
        System.out.println("Dijkstra(" + vertexs[start].data + " ---> " + vertexs[end].data + ")最短路徑:" + shortestPathance[end]);
    }

    /**
     * Dijkstra算法求最短路徑
     *
     * @param start 起始點(diǎn)
     * @param end   終點(diǎn),如果end=vertexs.length說(shuō)明是遍歷查找所有的最短路徑
     * @return 起始頂點(diǎn)到其他點(diǎn)或者指定點(diǎn)的最短權(quán)值
     */
    private int[] getShortestDistance(int start, int end) {
        /*1、該數(shù)組存放起始頂點(diǎn)到其他點(diǎn)的權(quán)值*/
        int[] distance = new int[vertexs.length];
        //初始化數(shù)據(jù)
        for (int i = 0; i < vertexs.length; i++) {
            //首先設(shè)置起始點(diǎn)到頂點(diǎn)i到的最短路徑為起始點(diǎn)到頂點(diǎn)i的權(quán)。
            distance[i] = getWeight(start, i);
        }

        /*2、標(biāo)志位數(shù)組.某個(gè)位置表示true表示,對(duì)應(yīng)位置的頂點(diǎn)到起始頂點(diǎn)的最短路徑已成功獲取。*/
        boolean[] shortest = new boolean[vertexs.length];
        //首先設(shè)置起始點(diǎn)到自己的的路徑已經(jīng)找到了,為0
        shortest[start] = true;


        /*3、最多遍歷vertexs.length-1次；每次找出起始點(diǎn)到一個(gè)頂點(diǎn)的最短路徑。*/
        int k;
        int min;
        for (int i = 1; i < vertexs.length; i++) {
            k = 0;
            // 尋找當(dāng)前最小的路徑；
            min = NO_EDGE;
            for (int j = 0; j < vertexs.length; j++) {
                //排除已經(jīng)找到的最短路徑之后，找到離start最近的頂點(diǎn)(k)。
                if (!shortest[j] && distance[j] < min) {
                    min = distance[j];
                    k = j;
                }
            }
            //先設(shè)置起始點(diǎn)到新頂點(diǎn)k的最短路徑已經(jīng)找到
            shortest[k] = true;
            if (end != vertexs.length && k == end) {
                break;
            }
            //更新未獲取最短路徑的頂點(diǎn)的最短路徑,因?yàn)槠渌颜业降捻旤c(diǎn)的最短路徑已經(jīng)找到了,這里指需要更新新加入的已找到的可達(dá)頂點(diǎn)的路徑.
            for (int j = 0; j < vertexs.length; j++) {
                int tmp = getWeight(k, j);
                //排除已經(jīng)找到的最短路徑，排除未連接的路徑，排除等于0的路徑（連接自己）之后
                //找到離start最如果新的最短路徑比以前的最短路徑還要短，則更新最短路徑。
                if (!shortest[j] && tmp != NO_EDGE && tmp != 0 && ((tmp = min + tmp) < distance[j])) {
                    distance[j] = tmp;
                }
            }
        }
        return distance;
    }


    /**
     * 索引檢查
     *
     * @param index 多個(gè)索引
     */
    private void checkIndex(int... index) {
        for (int i : index) {
            if (i < 0 || i >= vertexs.length) {
                throw new ArrayIndexOutOfBoundsException("索引越界:" + i);
            }
        }
    }

    /**
     * Floyd算法獲取所有頂點(diǎn)到所有頂點(diǎn)的最短路徑,與鄰接矩陣的實(shí)現(xiàn)基本一致
     */
    public void floyd() {
        //路徑矩陣(兩頂點(diǎn)最短路徑,即最小權(quán)值)
        int[][] shortestPath = new int[vertexs.length][vertexs.length];
        /*初始化數(shù)據(jù)*/
        for (int i = 0; i < vertexs.length; i++) {
            for (int j = 0; j < vertexs.length; j++) {
                //獲取兩點(diǎn)的直接權(quán)值
                //如果是頻繁調(diào)用該方法,因此可以創(chuàng)建一個(gè)屬于對(duì)象的權(quán)值矩陣用來(lái)保存權(quán)值,這里為了簡(jiǎn)單沒做
                shortestPath[i][j] = getWeight(i, j);
            }
        }
        // 計(jì)算最短路徑
        for (int k = 0; k < vertexs.length; k++) {
            for (int i = 0; i < vertexs.length; i++) {
                for (int j = 0; j < vertexs.length; j++) {
                    //要求經(jīng)過(guò)下標(biāo)k頂點(diǎn)的兩個(gè)路徑都不能等于NO_EDGE,否則就是沒有路徑,NO_EDGE應(yīng)該選取的足夠的大,否則可能出錯(cuò)
                    int tmp = (shortestPath[i][k] == NO_EDGE || shortestPath[k][j] == NO_EDGE) ? NO_EDGE : (shortestPath[i][k] + shortestPath[k][j]);
                    // 如果經(jīng)過(guò)下標(biāo)為k頂點(diǎn)路徑比原兩點(diǎn)間路徑更短，則更新shortestPath[i][j]
                    if (shortestPath[i][j] > tmp) {
                        // i到j(luò)最短路徑對(duì)應(yīng)的值設(shè)為經(jīng)過(guò)k的更小的一個(gè)
                        shortestPath[i][j] = tmp;
                    }

                }
            }
        }
        /*輸出路徑矩陣*/
        System.out.println("Floyd: ");
        for (int i = 0; i < vertexs.length; i++) {
            for (int j = 0; j < vertexs.length; j++) {
                System.out.print("\t" + shortestPath[i][j]);
            }
            System.out.println();
        }
    }


    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', 8),
                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', 9),
                new Edge<>('F', 'G', 9)};
        //構(gòu)建圖
        ListDijkstraAndFloyd<Character> listDijkstraAndFloyd = new ListDijkstraAndFloyd<Character>(vexs, edges);
        //輸出圖
        System.out.println(listDijkstraAndFloyd);
        //深度優(yōu)先遍歷
        //DFS:
        //A C B E G F D
        listDijkstraAndFloyd.DFS();
        //廣度優(yōu)先遍歷
        //BFS:
        //A C D F B G E
        listDijkstraAndFloyd.BFS();
        //Prim算法求最小生成樹
        listDijkstraAndFloyd.prim();
        //Kruskal算法求最小生成樹
        listDijkstraAndFloyd.kruskal();


        // Dijkstra算法獲取某個(gè)索引的頂點(diǎn)到其它各個(gè)頂點(diǎn)的最短距離
        // 這里參數(shù)是索引,也可以是一個(gè)頂點(diǎn),需要稍微修改代碼獲取頂點(diǎn)的索引,比較簡(jiǎn)單這里就不做了
        listDijkstraAndFloyd.dijkstra(0);
        // Dijkstra算法獲取一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的最短距離
        listDijkstraAndFloyd.dijkstra(2, 0);

        // Floyd算法獲取所有頂點(diǎn)到所有頂點(diǎn)的最短路徑
        listDijkstraAndFloyd.floyd();
    }

}