java实现 库鲁斯卡尔算法kruskal（算法设计与分析作业）

package package1;

import java.util.Arrays;

public class alg {
   
    //判断tar是否在nums中
    public static boolean isIn(int[] nums, int tar) {
   
        for (int n : nums) {
   
            if (tar == n) {
   
                return true;
            }
        }
        return false;
    }
    // 排序按照二维数组的第三个数排序
    public static void sortG(int[][] g) {
   
        for (int i = 0; i < g.length - 1; i++) {
   
            for (int j = 0; j < g.length - 1 - i; j++) {
   
                if (g[j][2] > g[j + 1][2]) {
   
                    int[] t = g[j];
                    g[j] = g[j + 1];
                    g[j + 1] = t;
                }
            }
        }
        System.out.printf("---------------%s------------------\n", "排序后");
        for (int[] i : g) {
   
            System.out.println(Arrays.toString(i));
        }
    }
    public static void kruskal(int[][] n, int m) {
   
        /** * n二维数组边 * m定点数 */
        int[] list = new int[m];
        int list_p = 0 ;
        for(int i = 0; i < n.length; i++){
   
            if(!isIn(list, n[i][0])){
   
                list[list_p] = n[i][0];
                list_p++;
                char p1 = (char) (n[i][0] + 97);
                char p2 = (char) (n[i][1] + 97);
                System.out.println((n[i][0] + 1) + "" + p1 + "<--->" + p2 + (n[i][1] + 1) + " ->" + n[i][2]);
            }else if(!isIn(list, n[i][1])){
   
                list[list_p] = n[i][1];
                list_p++;
                char p1 = (char) (n[i][0] + 97);
                char p2 = (char) (n[i][1] + 97);
                System.out.println((n[i][0] + 1) + "" + p1 + "<--->" + p2 + (n[i][1] + 1) + " ->" + n[i][2]);
            }
            if(list_p >= m - 1){
   
                break;
            }
        }
    }

    public static void main(String[] args) {
   
        int[][] n = {
   {
   1, 2, 3}, {
   1, 5, 6}, {
   1, 6, 5}, {
   2, 3, 1}, {
   2, 6, 4}, {
   3, 4, 6}, {
   3, 6, 4}, {
   4, 5, 8}, {
   4, 6, 5}, {
   5, 6, 2}};
        sortG(n);
        kruskal(n,6);

        System.out.printf("------------%s-------------\n", "图二");
        int[][] n1 = {
   {
   1,2,5},{
   1,4,6},{
   2,3,1},{
   2,4,3},{
   3,4,4},{
   3,5,6},{
   4,5,2}};
        sortG(n1);
        kruskal(n1,5);

        System.out.printf("------------%s-------------\n", "图三");
        int[][] n2 = {
   {
   1,2,3},{
   1,4,4},{
   1,3,5},{
   2,5,3},{
   2,6,6},{
   4,3,2},{
   4,8,5},{
   4,5,1},{
   6,5,2},{
   6,10,5},{
   7,3,4},{
   7,8,3},{
   7,11,6},{
   9,8,6},{
   9,5,4},{
   9,10,3},{
   9,12,5},{
   11,12,8},{
   11,8,7},{
   12,10,9}};
        sortG(n2);
        kruskal(n2,12);
    }
}

结果