Kruskal算法有兩個(gè)要求：

①對(duì)圖的所有邊按照權(quán)值大小進(jìn)行排序。
②將邊添加到最小生成樹(shù)中時(shí)，怎么樣判斷是否形成了回路。

①很好解決，采用排序算法進(jìn)行排序即可。
②處理方式是:記錄頂點(diǎn)在"最小生成樹(shù)"中的終點(diǎn)，頂點(diǎn)的終點(diǎn)是"在最小生成樹(shù)中與它連通的最大頂點(diǎn)"。然后每次需要將一條邊添加到最小生存樹(shù)時(shí)判斷該邊的兩個(gè)頂點(diǎn)的終點(diǎn)是否重合，重合的話則會(huì)構(gòu)成回路。

如何判斷回路？

將所有頂點(diǎn)按照從小到大的順序排列好之后，某個(gè)頂點(diǎn)的終點(diǎn)就是"與它連通的最大頂點(diǎn)"。我們加入的邊的兩個(gè)頂點(diǎn)不能都指向同一個(gè)終點(diǎn)，否則構(gòu)成回路。
具體是這個(gè)方法

/** * 返回傳入的點(diǎn)的終點(diǎn)的下標(biāo) * @param ends ends[i] = j i是傳入的點(diǎn)的下標(biāo)，j是i的相鄰點(diǎn)的下標(biāo) * @param i * @return */public static int getEnd(int[] ends,int i){    //如果這個(gè)點(diǎn)有可以到達(dá)的點(diǎn)，那么就把可以到達(dá)的點(diǎn)賦值到i，然后如果i還有可以到達(dá)的點(diǎn)，那么就重復(fù)此操作。一直到最后，最后的點(diǎn)就是最初傳入的點(diǎn)的終點(diǎn)    //其實(shí)ends數(shù)組記的是每一個(gè)點(diǎn)的相鄰點(diǎn)，而不是終點(diǎn)，但是可以通過(guò)ends數(shù)組，利用while循環(huán)，求出一個(gè)點(diǎn)的終點(diǎn)    while (ends[i] != 0){        i = ends[i];    }    return i;}

代碼

public class Main {    static char[] data = {"A","B","C","D","E","F","G"};    public static void main(String[] args) {        //char[] data = {"A","B","C","D","E","F","G"};        int[][] weight = {                {0,12,10000,10000,10000,16,14},                {12,0,10,10000,10000, 7,10000},                {10000,10,0,3,5,6,10000},                {10000,10000,3,0,4,10000,10000},                {10000,10000,5,4,0,2,8},                {16,7,6,10000,2,0,9},                {14,10000,10000,10000,8,9,0}};        MGraph mGraph = new MGraph(data.length);        mGraph.createGraph(data,weight);        mGraph.showGraph();        createMinTreeKruskal(mGraph);        //System.out.println(Arrays.toString(MEdge.getEdges(mGraph)));        //System.out.println(Arrays.toString(MEdge.getSortedEdges(MEdge.getEdges(mGraph))));    }    /**     * 克魯斯卡爾算法構(gòu)建最小生成樹(shù)     */    public static void createMinTreeKruskal(MGraph mGraph){        if (mGraph.vertexNum == 0){            return;        }        //首先得到傳入的圖的所有邊按權(quán)值從小到大的順序排序        MEdge[] sortedEdges = MEdge.getSortedEdges(MEdge.getEdges(mGraph));//所有邊        ArrayList<MEdge> mEdges = new ArrayList<>();        //創(chuàng)建所有頂點(diǎn)的終點(diǎn)集        int[] ends = new int[mGraph.vertexNum];        for (int i = 0;i < sortedEdges.length;i++){            int p1 = MEdge.getPointIndex(sortedEdges[i].startPoint,data);            int p2 = MEdge.getPointIndex(sortedEdges[i].endPoint,data);            //判斷此邊的兩個(gè)點(diǎn)的終點(diǎn)是否相同            int end1 = MEdge.getEnd(ends,p1);            int end2 = MEdge.getEnd(ends,p2);            if (end1 != end2){                ends[end1] = end2;                mEdges.add(sortedEdges[i]);            }        }        System.out.println(mEdges);    }}//創(chuàng)建邊class MEdge{    char startPoint;    char endPoint;    int weight;    public MEdge(char startPoint, char endPoint, int weight) {        this.startPoint = startPoint;        this.endPoint = endPoint;        this.weight = weight;    }    @Override    public String toString() {        return "MEdge{" +                "startPoint=" + startPoint +                ", endPoint=" + endPoint +                ", weight=" + weight +                "}";    }    //傳入一個(gè)圖，根據(jù)其鄰接矩陣，得到其邊的數(shù)目    public static int getEdgesNum(MGraph mGraph){        if (mGraph.vertexNum == 0){            return -1;        }        int edgeNum = 0;        for (int i = 0;i < mGraph.vertexNum;i++){            for(int j = i + 1;j < mGraph.vertexNum;j++){                if (mGraph.weight[i][j] != 10000){                    //說(shuō)明這是一條邊，i和j分別是其端點(diǎn)                    edgeNum++;                }            }        }        return edgeNum;    }    //傳入一個(gè)圖，根據(jù)其鄰接矩陣，得到其邊    public static MEdge[] getEdges(MGraph mGraph){        if (mGraph.vertexNum == 0){            return null;        }        MEdge[] mEdges = new MEdge[getEdgesNum(mGraph)];        int index = 0;        for (int i = 0;i < mGraph.vertexNum;i++){            for(int j = i + 1;j < mGraph.vertexNum;j++){                if (mGraph.weight[i][j] != 10000){                    //說(shuō)明這是一條邊，i和j分別是其端點(diǎn)                    mEdges[index] = new MEdge(mGraph.data[i],mGraph.data[j],mGraph.weight[i][j]);                    index++;//這里一定別忘了+1                }            }        }        return mEdges;    }    //傳入一個(gè)邊集合，根據(jù)其權(quán)值大小進(jìn)行排序    public static MEdge[] getSortedEdges(MEdge[] mEdges){        for (int i = 0;i < mEdges.length - 1;i++){            for (int j = 0;j < mEdges.length - i - 1;j++){                if (mEdges[j + 1].weight < mEdges[j].weight){                    //不能用下面的 因?yàn)橄旅孢@種僅僅改變了邊的權(quán)，我們應(yīng)該整個(gè)邊都去改變//                    int temp = mEdges[j + 1].weight;//                    mEdges[j + 1].weight = mEdges[j].weight;//                    mEdges[j].weight = temp;                    MEdge mEdge = mEdges[j + 1];                    mEdges[j + 1] = mEdges[j];                    mEdges[j] = mEdge;                }            }        }        return mEdges;    }    /**     * 返回傳入的點(diǎn)的終點(diǎn)的下標(biāo)     * @param ends ends[i] = j i是傳入的點(diǎn)的下標(biāo)，j是i的終點(diǎn)的下標(biāo)     * @param i     * @return     */    public static int getEnd(int[] ends,int i){        //如果這個(gè)點(diǎn)有可以到達(dá)的點(diǎn)，那么就把可以到達(dá)的點(diǎn)賦值到i，然后如果i還有可以到達(dá)的點(diǎn)，那么就重復(fù)此操作。        //其實(shí)ends數(shù)組記的是每一個(gè)點(diǎn)的相鄰點(diǎn)，而不是終點(diǎn)，但是可以通過(guò)ends數(shù)組，利用while循環(huán)，求出一個(gè)點(diǎn)的終點(diǎn)        while (ends[i] != 0){            i = ends[i];        }        return i;    }    //輸入一個(gè)頂點(diǎn)（char類型），返回其索引值（int類型）    public static int getPointIndex(char point,char[] datas){        for (int i = 0;i < datas.length;i++){            if (datas[i] == point){                return i;            }        }        return -1;//沒(méi)找到    }}//這是圖class MGraph{    //節(jié)點(diǎn)數(shù)目    int vertexNum;    //節(jié)點(diǎn)    char[] data;    //邊的權(quán)值    int[][] weight;    MGraph(int vertexNum){        this.vertexNum = vertexNum;        data = new char[vertexNum];        weight = new int[vertexNum][vertexNum];    }    //圖的創(chuàng)建    public void createGraph(char[] mData,int[][] mWeight){        if (vertexNum == 0){            return;//節(jié)點(diǎn)數(shù)目為0 無(wú)法創(chuàng)建        }        for (int i = 0;i < data.length;i++){            data[i] = mData[i];        }        for (int i = 0;i < mWeight.length;i++){            for (int j = 0;j < mWeight.length;j++){                weight[i][j] = mWeight[i][j];            }        }    }    //打印圖    public void showGraph(){        if (vertexNum == 0){            return;        }        for (int[] oneLine: weight){            for (int oneNum: oneLine){                System.out.printf("%20d",oneNum);            }            System.out.println();        }    }}

結(jié)果

                 0                  12               10000               10000               10000                  16                  14                  12                   0                  10               10000               10000                   7               10000               10000                  10                   0                   3                   5                   6               10000               10000               10000                   3                   0                   4               10000               10000               10000               10000                   5                   4                   0                   2                   8                  16                   7                   6               10000                   2                   0                   9                  14               10000               10000               10000                   8                   9                   0[MEdge{startPoint=E, endPoint=F, weight=2}, MEdge{startPoint=C, endPoint=D, weight=3}, MEdge{startPoint=D, endPoint=E, weight=4}, MEdge{startPoint=B, endPoint=F, weight=7}, MEdge{startPoint=E, endPoint=G, weight=8}, MEdge{startPoint=A, endPoint=B, weight=12}]