并查集原理

并查集本质上是树的父亲表示法，用一个数组去保存当前结点的父结点（如果当前元素是根，那么数组中会存放元素本身）。并查集用于处理一些不相交集合的合并及查询问题（即所谓的并、查）。比如说，我们可以用并查集来判断一个森林中有几棵树、某个节点是否属于某棵树等。

下面是Java代码的一个简单实现：

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
import java.util.Arrays;

public class FindSet {
    private int[] pre;
    private int[] rank;
    // 点的个数
    private int size;
    public FindSet(int size) {
        this.size = size;
        pre = new int[size];
        for (int i = 0; i < size; i++) {
            pre[i] = i;
        }
        rank = new int[size];
        Arrays.fill(rank, 1);
    }

    public FindSet() {
        this(256);
    }

    public int find(int x) {
        if (pre[x] == x) {
            return x;
        }
        // 此代码相当于先找到根结点rootx，然后 pre[x] = rootx，完成路径的压缩
        return pre[x] = find(pre[x]);
    }

    public boolean isSame(int x, int y) {
        return find(x) == find(y);
    }

    public boolean union(int x,int y) {
        x = find(x);
        y = find(y);
        if(x == y) return false;			// 如果x和y的代表元一致，说明他们共属同一集合，则不需要合并，返回false，表示合并失败
        if(rank[x] > rank[y]) pre[y] = x;		// 如果x的高度大于y，则令y的上级为 x
        else {
            if(rank[x] == rank[y]) rank[y]++;	// 如果x的高度和y的高度相同，则令y的高度加1，让x的上级为 y
            pre[x] = y;
        }
        return true;						// 返回 true，表示合并成功
    }

}

用Kruskal去解决最小生成树

Kruskal算法是处理边的，所以在稀疏的边比较少的连通网中，用Kruskal算法效率就比较高；在边比较多，点比较少的连通网中，用加点法Prim算法效率比较高

Kruskal算法：此算法可以称为“加边法”，初始最小生成树边数为0，每迭代一次就选择一条满足条件的最小代价边，加入到最小生成树的边集合里，步骤如下：

  1. 把图中的所有边按权值从小到大排序，把图中的n个顶点看成独立的n颗树组成的森林
  2. 按权值从小到大选择边，所选的边连接的两个顶点$V_i$和 $V_j$应属于两颗不同的树，则称为最小生成树中的一条边，并合并成一棵树
  3. 重复步骤2，直到所有顶点都在一棵树内或者有n-1条边为止

例如，对于样例

1
2
3
4
5
6
7
8
9
10
11
10
A B 6
A C 1
A D 5
B C 5
C D 5
B E 3
C E 6
C F 4
E F 6
D F 2

image-20230812194911401

预期结果：

image-20230812195013639

边的定义如下：

1
2
3
4
5
public class Edge {
    public char start;
    public char end;
    public int w;
}

Kruskal算法如下：

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
public class Main {
    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        // 边数
        int n = in.nextInt();
        Edge[] edges = new Edge[n];
        FindSet findSet = new FindSet();
        for (int i = 0; i < n; i++) {
            edges[i] = new Edge();
            edges[i].start = in.next().charAt(0);
            edges[i].end = in.next().charAt(0);
            edges[i].w = in.nextInt();
        }
        Arrays.sort(edges, (o1, o2) -> o1.w - o2.w);
        for (Edge e : edges) {
            int root1 = findSet.find(e.start);
            int root2 = findSet.find(e.end);
            // 如果两个结点不属于同一棵树，那么就将该边加入其中
            if (root1 != root2) {
                findSet.union(root1, root2);
                System.out.println(e.start + " " + e.end + " " + e.w);
            }
        }

    }
}

程序运行结果：

image-20230812195048454