当前位置：首页 > news >正文

java---kruskal算法---最小生成树(2)（每日一道算法2022.9.3）

news 来源：原创 2024/4/28 14:13:38

注意事项:
kruskal算法的时间复杂度是mlogm
代码中涉及了并查集算法的合并和查找，如果不了解可以看我之前的文章：java-并查集算法

题目:
给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环，边权可能为负数。
求最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。
给定一张边带权的无向图 G=(V,E)，其中 V 表示图中点的集合，E 表示图中边的集合，n=|V|，m=|E|。
由 V 中的全部 n 个顶点和 E 中 n−1 条边构成的无向连通子图被称为 G 的一棵生成树，其中边的权值之和最小的生成树被称为无向图 G 的最小生成树。

第一行包含两个整数 n 和 m
接下来 m 行，每行包含三个整数 u,v,w，表示点 u 和点 v 之间存在一条权值为 w 的边

输出:
6

public class 最小生成树_kruskal {
    //p存储并查集数据，n是点的个数，m是边的个数，edges存储的是x点到y点的边权w, large是正无穷
    public static int N = 2000010, large = 0x3f3f3f3f, n ,m;
    public static int[] p = new int[N];
    public static edge[] edges = new edge[N];

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt(); m = in.nextInt();

        //将边权数据接收到edges中
        for (int i = 0; i<m; i++) {
            int x = in.nextInt(), y = in.nextInt(), w = in.nextInt();
            edges[i] = new edge(x, y, w);
        }

        int result = kruskal();
        if (result == large) System.out.println("impossible");
        else System.out.println(result);
    }

    public static int kruskal() {
        //根据边权进行排序，切记切记，这里要规定排序下标，不然后面的数据全是null，没法比较
        Arrays.sort(edges, 0, m);

        //根据点的数量初始化并查集，将所有集合的根指向自己
        for (int i = 1; i<=n; i++) {p[i] = i;}

        //res存储所有点到集合的最短边加起来的值，count代表一共有几条边出现
        int res = 0, count = 0;
        for (int i = 0; i<m; i++) {
            int x = edges[i].x, y = edges[i].y, w = edges[i].w;

            x = find(x); y = find(y);       //拿到x和y的并查集的根节点
            if (x != y) {
                p[x] = y;                   //这里是并查集的合并操作
                res += w;
                count++;
            }
        }

        //如果说边的数量最后小于n-1，那么说明有节点走不通，就不存在最小生成树，这里的large不存在实际意义，就是用作判断的
        if (count < n-1) return large;
        else return res;
    }

    //并查集的查找根节点
    public static int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
}

//记得要重写compareTo哦，要不然sort不了
class edge implements Comparable<edge>{
    int x, y, w;
    public edge(int x, int y, int w) {
        this.x = x;
        this.y = y;
        this.w = w;
    }

    @Override
    public int compareTo(edge other) {
        return this.w - other.w;
    }
}