わたしの部屋

1
public int find(int x) {
2
    if (parent[x] != x) {
3
        parent[x] = find(parent[x]); // 递归寻根，并将沿途节点挂到根下
4
    }
5
    return parent[x];
6
}

1
public void union(int x, int y) {
2
    int rx = find(x);
3
    int ry = find(y);
4
    if (rx == ry) return; // 已经在同一分量，无需合并
5

6
    // 矮树挂载到高树下
7
    if (rank[rx] < rank[ry]) {
8
        parent[rx] = ry;
9
    } else if (rank[rx] > rank[ry]) {
10
        parent[ry] = rx;
11
    } else {
12
        parent[ry] = rx;
13
        rank[rx]++;
14
    }
15
}

1
/**
2
 * 采用路径压缩与按秩合并优化的并查集实现。
3
 */
4
class UnionFind {
5
    private final int[] parent;
6
    private final int[] rank;
7
    private int count; // 当前连通分量的数量
8

9
    public UnionFind(int n) {
10
        parent = new int[n];
11
        rank = new int[n];
12
        count = n;
13
        for (int i = 0; i < n; i++) {
14
            parent[i] = i; // 初始状态下，每个顶点自成一个分量
15
            rank[i] = 0;
16
        }
17
    }
18

19
    /**
20
     * 查询节点 x 所在分量的根节点，顺带进行路径压缩。
21
     */
22
    public int find(int x) {
23
        if (parent[x] != x) {
24
            parent[x] = find(parent[x]);
25
        }
26
        return parent[x];
27
    }
28

29
    /**
30
     * 合并 x 和 y 所在的两个分量。
31
     * @return 若成功合并（原本不在同一分量，未成环）返回 true；若已在同一分量（会成环）则返回 false。
32
     */
33
    public boolean union(int x, int y) {
34
        int rx = find(x);
35
        int ry = find(y);
36
        if (rx == ry) {
37
            return false; // 已在同一分量，合并失败（说明加入此边会成环）
38
        }
39
        // 按秩合并：将矮树挂载到高树下
40
        if (rank[rx] < rank[ry]) {
41
            parent[rx] = ry;
42
        } else if (rank[rx] > rank[ry]) {
43
            parent[ry] = rx;
44
        } else {
45
            parent[ry] = rx;
46
            rank[rx]++;
47
        }
48
        count--; // 成功连通，分量总数减 1
49
        return true;
50
    }
51

52
    public boolean connected(int x, int y) {
53
        return find(x) == find(y);
54
    }
55

56
    public int count() {
57
        return count;
58
    }
59
}

1
import java.util.*;
2

3
public class KruskalMST {
4

5
    /**
6
     * 代表图中的一条带权无向边。
7
     */
8
    public static class Edge implements Comparable<Edge> {
9
        int from;
10
        int to;
11
        int weight;
12

13
        public Edge(int from, int to, int weight) {
14
            this.from = from;
15
            this.to = to;
16
            this.weight = weight;
17
        }
18

19
        @Override
20
        public int compareTo(Edge other) {
21
            return Integer.compare(this.weight, other.weight);
22
        }
23

24
        @Override
25
        public String toString() {
26
            return "(" + from + "-" + to + ", w=" + weight + ")";
27
        }
28
    }
29

30
    /**
31
     * 采用路径压缩与按秩合并优化的并查集。
32
     */
33
    public static class UnionFind {
34
        private final int[] parent;
35
        private final int[] rank;
36

37
        public UnionFind(int n) {
38
            parent = new int[n];
39
            rank = new int[n];
40
            for (int i = 0; i < n; i++) {
41
                parent[i] = i;
42
                rank[i] = 0;
43
            }
44
        }
45

46
        public int find(int x) {
47
            if (parent[x] != x) {
48
                parent[x] = find(parent[x]); // 路径压缩
49
            }
50
            return parent[x];
51
        }
52

53
        public boolean union(int x, int y) {
54
            int rx = find(x);
55
            int ry = find(y);
56
            if (rx == ry) {
57
                return false; // 已在同一连通分量，说明加入该边会构成环路
58
            }
59
            // 按秩合并：将矮树挂载到高树下
60
            if (rank[rx] < rank[ry]) {
61
                parent[rx] = ry;
62
            } else if (rank[rx] > rank[ry]) {
63
                parent[ry] = rx;
64
            } else {
65
                parent[ry] = rx;
66
                rank[rx]++;
67
            }
68
            return true;
69
        }
70
    }
71

72
    /**
73
     * Kruskal 最小生成树算法的主实现。
74
     * @param n 顶点个数（顶点编号为 0 到 n-1）
75
     * @param edges 所有的无向边列表
76
     * @return 构成最小生成树的边列表。若图不连通，则返回最小生成森林。
77
     */
78
    public static List<Edge> kruskal(int n, List<Edge> edges) {
79
        // 1. 将所有边按权值升序排序
80
        List<Edge> sorted = new ArrayList<>(edges);
81
        Collections.sort(sorted);
82

83
        // 2. 初始化并查集
84
        UnionFind uf = new UnionFind(n);
85
        List<Edge> mst = new ArrayList<>();
86

87
        for (Edge e : sorted) {
88
            // 3. 判断是否同分量，不同分量则保留该边并合并
89
            if (uf.union(e.from, e.to)) {
90
                mst.add(e);
91
                if (mst.size() == n - 1) {
92
                    break; // 已成功找出 n-1 条边，提前结束
93
                }
94
            }
95
        }
96
        return mst;
97
    }
98

99
    public static void main(String[] args) {
100
        int n = 6;
101
        List<Edge> edges = Arrays.asList(
102
                new Edge(0, 1, 7),   // A-B
103
                new Edge(0, 2, 8),   // A-C
104
                new Edge(1, 2, 3),   // B-C
105
                new Edge(1, 3, 6),   // B-D
106
                new Edge(2, 3, 4),   // C-D
107
                new Edge(2, 4, 3),   // C-E
108
                new Edge(3, 4, 2),   // D-E
109
                new Edge(3, 5, 5),   // D-F
110
                new Edge(4, 5, 2)    // E-F
111
        );
112

113
        List<Edge> mst = kruskal(n, edges);
114

115
        System.out.println("Kruskal MST 选中的边：");
116
        int totalWeight = 0;
117
        for (Edge e : mst) {
118
            System.out.println("  " + e);
119
            totalWeight += e.weight;
120
        }
121
        System.out.println("总权值：" + totalWeight);
122
    }
123
}

1
Kruskal MST 选中的边：
2
  (3-4, w=2)
3
  (4-5, w=2)
4
  (1-2, w=3)
5
  (2-4, w=3)
6
  (0-1, w=7)
7
总权值：17