并查集

作者： /

什么是并查集

并查集（Union-Find / Disjoint Set Union）是一种树形数据结构，专门处理不相交集合的合并与查询问题，只支持两个操作：

  • Find(x)：确定元素 x 属于哪个集合（找到集合的代表元素/根）；
  • Union(x, y)：把 x 和 y 所在的两个集合合并。

它的典型应用包括：图的连通分量、Kruskal 最小生成树、网络连接问题、社交网络”朋友圈”等。

基本实现

用数组 parent 表示森林：parent[i] 是节点 i 的父节点，根节点的父节点指向自己。

type UnionFind struct {
    parent []int
    count  int // 连通分量个数
}

func NewUnionFind(n int) *UnionFind {
    uf := &UnionFind{parent: make([]int, n), count: n}
    for i := 0; i < n; i++ {
        uf.parent[i] = i
    }
    return uf
}

// Find 找到 x 所在集合的根
func (uf *UnionFind) Find(x int) int {
    for uf.parent[x] != x {
        x = uf.parent[x]
    }
    return x
}

// Union 合并 x、y 所在集合
func (uf *UnionFind) Union(x, y int) {
    rx, ry := uf.Find(x), uf.Find(y)
    if rx == ry {
        return
    }
    uf.parent[rx] = ry
    uf.count--
}

优化一：路径压缩

树可能退化成一条链，Find 最坏 O(n)。路径压缩在 Find 的过程中把路径上的所有节点直接挂到根下面，让后续查找接近 O(1)：

func (uf *UnionFind) Find(x int) int {
    if uf.parent[x] != x {
        uf.parent[x] = uf.Find(uf.parent[x])
    }
    return uf.parent[x]
}

优化二：按秩合并

用 rank 记录每棵树的高度，合并时把矮树挂到高树下面，避免树长高：

type UnionFind struct {
    parent []int
    rank   []int
    count  int
}

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

func (uf *UnionFind) Union(x, y int) {
    rx, ry := uf.Find(x), uf.Find(y)
    if rx == ry {
        return
    }
    if uf.rank[rx] > uf.rank[ry] {
        uf.parent[ry] = rx
    } else if uf.rank[rx] < uf.rank[ry] {
        uf.parent[rx] = ry
    } else {
        uf.parent[ry] = rx
        uf.rank[rx]++
    }
    uf.count--
}

注意：合并时要先 Find 再比较根，把根挂到根上，而不是把节点直接挂过去，否则会破坏森林结构。

复杂度分析

  • 只做路径压缩：均摊 O(log n)；
  • 只做按秩合并：最坏 O(log n)；
  • 两者同时使用：均摊 O(α(n))，其中 α(n) 是反阿克曼函数，增长极其缓慢——n 在宇宙原子数量级别时 α(n) 也不超过 5，工程上可以认为是常数时间。

空间复杂度 O(n)。

实战应用

1. 计算连通分量个数

func countComponents(n int, edges [][]int) int {
    uf := NewUnionFind(n)
    for _, e := range edges {
        uf.Union(e[0], e[1])
    }
    return uf.count
}

2. 判断图中是否有环

func hasCycle(n int, edges [][]int) bool {
    uf := NewUnionFind(n)
    for _, e := range edges {
        if uf.Find(e[0]) == uf.Find(e[1]) {
            return true // 两个端点已连通，再加这条边就成环
        }
        uf.Union(e[0], e[1])
    }
    return false
}

3. 朋友圈问题

func findCircleNum(isConnected [][]int) int {
    n := len(isConnected)
    uf := NewUnionFind(n)
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            if isConnected[i][j] == 1 {
                uf.Union(i, j)
            }
        }
    }
    return uf.count
}

开源实现参考

  • github.com/yourbasic/uf：简洁高效的 Go 实现，路径压缩，支持动态扩容，接口清晰（New/Union/Find/Count）；
  • github.com/kelvinlau/go-unionfind：按大小合并（Union by Size），提供 Connected 方法，支持重置；
  • github.com/wangzheng0822/algo：路径压缩 + 按秩合并同时使用，文档详细。

总结

并查集的全部精华就两句话：Find 时路径压缩，Union 时按秩合并。两者都做，操作均摊常数时间。它代码量极小、边界清晰，是处理动态连通性问题的默认首选。

滚动至顶部