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

1、Kruskal算法设计思想

实现克鲁斯卡尔算法的关键是准确判断选取的边是否与生成树中已有边形成回路。这可以通过判断边的两个顶点所在的连通分量来解决。克鲁斯卡尔算法为此设置了一个辅助数组vset【0~n-1】，用于判断两个顶点之间是否连通。数组元素vset【i】代表编号顶点为i的顶点所属的连通顶点集的编号，当两个顶点的集合编号不同时，加入这两个顶点构成的边到最小生成树中时一定不会形成回路。克鲁斯卡尔算法采用Node数组存放图中的所有边，采用排序的方法将所有边按权值从小到大排序。

以下代码仅供参考
以下代码仅供参考
以下代码仅供参考

/**
 *作者：魏宝航
 *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;
    }
}

本文地址：https://blog.csdn.net/m0_47256162/article/details/109995421