programming

并查集算法：高效的集合合并与查找

算法原理

并查集（Union-Find）是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。它支持两种操作：查找（Find）：确定元素属于哪一个子集；合并（Union）：将两个子集合并成同一个集合。

基本思想

  1. 初始化：每个元素自成一个集合
  2. 查找根节点：找到元素所属集合的代表
  3. 合并集合：将两个集合的根节点连接
  4. 路径压缩：优化查找效率

C语言实现

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
68
69
70
71
72
#include <stdio.h>
#include <stdlib.h>

typedef struct UnionFind {
    int* parent;
    int* rank;
    int size;
    int count; // 连通分量数
} UnionFind;

// 创建并查集
UnionFind* create_union_find(int n) {
    UnionFind* uf = (UnionFind*)malloc(sizeof(UnionFind));
    uf->parent = (int*)malloc(n * sizeof(int));
    uf->rank = (int*)calloc(n, sizeof(int));
    uf->size = n;
    uf->count = n;
    
    // 初始化：每个元素的父节点是自己
    for (int i = 0; i < n; i++) {
        uf->parent[i] = i;
    }
    
    return uf;
}

// 查找根节点（带路径压缩）
int find(UnionFind* uf, int x) {
    if (uf->parent[x] != x) {
        uf->parent[x] = find(uf, uf->parent[x]); // 路径压缩
    }
    return uf->parent[x];
}

// 合并两个集合（按秩合并）
void union_sets(UnionFind* uf, int x, int y) {
    int root_x = find(uf, x);
    int root_y = find(uf, y);
    
    if (root_x != root_y) {
        // 按秩合并
        if (uf->rank[root_x] < uf->rank[root_y]) {
            uf->parent[root_x] = root_y;
        } else if (uf->rank[root_x] > uf->rank[root_y]) {
            uf->parent[root_y] = root_x;
        } else {
            uf->parent[root_y] = root_x;
            uf->rank[root_x]++;
        }
        uf->count--; // 连通分量减一
    }
}

// 判断两个元素是否在同一个集合
bool connected(UnionFind* uf, int x, int y) {
    return find(uf, x) == find(uf, y);
}

int main() {
    UnionFind* uf = create_union_find(10);
    
    // 合并一些元素
    union_sets(uf, 0, 1);
    union_sets(uf, 1, 2);
    union_sets(uf, 3, 4);
    
    printf("0和2是否连通: %s\n", connected(uf, 0, 2) ? "是" : "否");
    printf("0和3是否连通: %s\n", connected(uf, 0, 3) ? "是" : "否");
    printf("连通分量数: %d\n", uf->count);
    
    return 0;
}

应用场景

  1. 网络连通性：判断网络节点是否连通
  2. 社交网络：朋友圈的划分
  3. 图像处理：连通区域的识别
  4. 最小生成树：Kruskal算法的实现

版权所有，如有侵权请联系我