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

注意事项:
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 的边

输入：
4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4
1
2
3
4
5
6
7

输出:
6
1
2

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

别看代码很多，其实kruskal的思路其实非常简单
1.权重排序
2.合并集合
完事了，然后判断一下（合并的次数）和（点的总数减一）是否相同，即可判断最小生成树是否存在

PS：堆优化版Prim实在是不太常用，我就不写了，kruskal完全能胜任，真的不是我偷懒，哎嘿~

声明：算法思路来源为y总，详细请见https://www.acwing.com/
本文仅用作学习记录和交流