Kruskal算法（克鲁斯卡尔）最小生成树

/**
 *作者：魏宝航
 *2020年11月23日,下午14:28
 */
import org.omg.CORBA.INTERNAL;
import java.io.IOException;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;
public class MatrixUDG {
    private char[] mVexs;
    private int[][] mMatrix;
    private int num;
    public MatrixUDG(char[] vexs, char[][] edges) {
        num = vexs.length;
        mVexs = new char[num];
        for (int i = 0; i < mVexs.length; i++)
            mVexs[i] = vexs[i];
        mMatrix = new int[num][num];
        for(int i=0;i<num;i++){
            for(int j=0;j<num;j++){
                if(edges[i][j]=='∞'){
                    mMatrix[i][j]=Integer.MAX_VALUE;
                }else{
                    mMatrix[i][j]=Integer.parseInt(edges[i][j]+"");
                }
            }
        }
    }
    public void InsertSort(Node arr[],int n){
        int i=0,j=0;
        Node temp;
        for(i=1;i<n;i++){
            temp=arr[i];
            j=i-1;
            while(j>=0&&temp.w<arr[j].w){
                arr[j+1]=arr[j];
                j--;
            }
            arr[j+1]=temp;
        }
    }
    public void print() {
        System.out.printf("Martix Graph:\n");
        for (int i = 0; i < mVexs.length; i++) {
            for (int j = 0; j < mVexs.length; j++){
                if(mMatrix[i][j]<Integer.MAX_VALUE){
                    System.out.printf("%d ", mMatrix[i][j]);
                }else{
                    System.out.print("∞ ");
                }
            }
            System.out.printf("\n");
        }
    }
    public void Kruskal(){
        Node[] arr=new Node[1000];
        int m1,m2,sn1,sn2,k;
        int[] vset=new int[1000];
        k=0;
        for(int i=0;i<this.num;i++){
            for(int j=i+1;j<this.num;j++){
                if(this.mMatrix[i][j]!=0&&this.mMatrix[i][j]!=Integer.MAX_VALUE){
                    arr[k]=new Node(i,j,this.mMatrix[i][j]);
                    k++;
                }
            }
        }
        InsertSort(arr,k);
        for(int i=0;i<this.num;i++){
            vset[i]=i;
        }
        k=1;
        int j=0;
        for(;k<num;){
            m1=arr[j].u;
            m2=arr[j].v;
            sn1=vset[m1];
            sn2=vset[m2];
            if(sn1!=sn2){
                System.out.printf("边（%d，%d）：%d\n",m1,m2,arr[j].w);
                k++;
                for(int i=0;i<this.num;i++){
                    if(vset[i]==sn2){
                        vset[i]=sn1;
                    }
                }
            }
            j++;
        }
    }
    public static void main(String[] args) {
        char[] vexs={'0','1','2','3','4','5'};
        char[][] edges=new char[][]{
                {'0','6','1','5','∞','∞'},
                {'6','0','5','∞','3','∞'},
                {'1','5','0','5','6','4'},
                {'5','∞','5','0','∞','2'},
                {'∞','3','6','∞','0','6'},
                {'∞','∞','4','2','6','0'},
        };
        MatrixUDG g=new MatrixUDG(vexs,edges);
        g.print();
        g.Kruskal();
    }
}
class Node implements Comparable<Node>{
    int u;
    int v;
    int w;
    Node(int u,int v,int w){
        this.u=u;
        this.v=v;
        this.w=w;
    }
    @Override
    public int compareTo(Node o) {
        return w-o.w;
    }
}