Union-Find 算法

算法
loading...

并查集（Union-Find）算法详解

一、概念介绍

并查集（Union-Find）是一种用于管理不相交集合（Disjoint Set）的数据结构，主要用于高效解决以下问题：

  • 判断两个元素是否属于同一集合
  • 合并两个集合
  • 统计集合数量

其核心思想是将每个集合表示为一棵树，每个节点指向父节点，根节点作为集合的代表。

二、核心操作

1. Find（查找根节点）

Find(x) 用于找到元素 x 所在集合的根节点。

1
2
3
4
function Find(x):
    if parent[x] != x:
        parent[x] = Find(parent[x])  // 路径压缩
    return parent[x]

路径压缩：查找过程中将节点直接指向根节点，使树扁平化，从而加快后续操作。

2. Union（合并集合）

Union(x, y) 将元素 x 和 y 所在集合合并。

1
2
3
4
5
function Union(x, y):
    rootX = Find(x)
    rootY = Find(y)
    if rootX != rootY:
        parent[rootX] = rootY

可使用**按秩合并（Union by Rank）**优化，将高度较小的树挂到高度较大的树下，进一步减少树的高度。

三、并查集实现要点

  • 初始化：每个元素自成一棵树，父节点指向自己。
  • Find：带路径压缩。
  • Union：可选按秩合并，降低时间复杂度。
  • 查询集合数量：通过统计不同根节点个数实现。

四、Go 语言实现示例

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
package main

import "fmt"

// UnionFind 定义
type UnionFind struct {
    parent []int
    rank   []int
}

// 初始化
func NewUnionFind(n int) *UnionFind {
    uf := &UnionFind{
        parent: make([]int, n),
        rank:   make([]int, n),
    }
    for i := 0; i < n; i++ {
        uf.parent[i] = i
        uf.rank[i] = 1
    }
    return uf
}

// Find 操作 + 路径压缩
func (uf *UnionFind) Find(x int) int {
    if uf.parent[x] != x {
        uf.parent[x] = uf.Find(uf.parent[x])
    }
    return uf.parent[x]
}

// Union 操作 + 按秩合并
func (uf *UnionFind) Union(x, y int) {
    rootX := uf.Find(x)
    rootY := uf.Find(y)
    if rootX == rootY {
        return
    }
    if uf.rank[rootX] < uf.rank[rootY] {
        uf.parent[rootX] = rootY
    } else if uf.rank[rootX] > uf.rank[rootY] {
        uf.parent[rootY] = rootX
    } else {
        uf.parent[rootY] = rootX
        uf.rank[rootX]++
    }
}

// 判断是否在同一个集合
func (uf *UnionFind) Connected(x, y int) bool {
    return uf.Find(x) == uf.Find(y)
}

func main() {
    uf := NewUnionFind(5)
    uf.Union(0, 1)
    uf.Union(1, 2)
    fmt.Println(uf.Connected(0, 2)) // true
    fmt.Println(uf.Connected(0, 3)) // false
}

五、应用场景

  1. 社交网络：计算朋友圈或互相认识的人群数量。
  2. 图论问题：判断图中连通分量、最小生成树（Kruskal算法）等。
  3. 动态连通性：处理在线合并和查询集合问题。

六、算法复杂度

  • 初始化：O(n)
  • 单次 Find/Union（带路径压缩 + 按秩）：近似 O(1)
  • 总复杂度：O(α(n))，其中 α(n) 是阿克曼函数的反函数，几乎可视为常数。

七、总结

  • 并查集是解决不相交集合问题的利器。
  • 核心优化策略是路径压缩 + 按秩合并，保证操作高效。