并查集

作者： /
并查集Union-Find 集合合并与路径压缩

什么是并查集

并查集（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--
}

裸实现的问题：Union 顺序不当时树退化成链，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]
}
并查集路径压缩：Find沿途节点直接指向根
图 1：Find(4) 之后，链上所有节点直接指向根 0

注意：单次 Find 仍可能 O(log n)，但摊还下来接近常数——这正是并查集快的来源。

优化二：按秩合并

用 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--
}
并查集Union操作：先Find根再根挂根
图 2：Union(2,4)——先 Find 出根 0、3，再把根挂到根上

铁律：合并前先 Find 再比较根，把根挂到根上。直接挂普通节点会破坏森林结构，产生假根。

复杂度分析

  • 只做路径压缩：均摊 O(log n)；
  • 只做按秩合并：最坏 O(log n)；
  • 两者都用：均摊 O(α(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 时按秩合并。两者都做，操作均摊常数时间。代码量极小、边界清晰，是动态连通性问题的默认首选。

滚动至顶部