Go语言并查集实现详解

本文深入解析了Go语言中高效实现并查集（Union-Find）的核心要点，强调采用`[]int`数组版配合路径压缩与按秩合并的黄金组合——既规避了指针结构体带来的GC压力和间接访问开销，又通过递归压缩与rank平衡确保单次操作均摊接近反阿克曼函数O(α(n))的极致性能；同时直击常见陷阱：如漏写rank自增、非递归Find未更新父节点、误用map导致复杂度失控，并给出离散化处理非连续/负数ID的实用方案，以及并发场景下加锁与预计算的权衡策略，堪称Go开发者落地高性能并查集的避坑指南与最佳实践手册。

Go 语言实现并查集（Union-Find）不需要第三方库，核心就两个操作：Find 和 Union，但直接写容易踩内存和性能坑——比如用切片做 parent 数组时忘了路径压缩，或用指针结构体导致 GC 压力大。

怎么写一个带路径压缩的数组版 Union-Find

最常用、最高效的方式是用 []int 存 parent 索引，配合路径压缩 + 按秩合并（rank）。不推荐用结构体嵌套指针，那会引入不必要的间接访问和 GC 开销。

关键点：

• parent[i] == i 表示 i 是根节点
• Find 必须递归或迭代做路径压缩：把沿途所有节点直接连到根
• Union 比较 rank 决定谁当新根，避免树退化成链表
• 初始化时 rank 全为 0，parent[i] = i

示例片段：

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

func NewUnionFind(n int) *UnionFind {
    parent := make([]int, n)
    rank := make([]int, n)
    for i := 0; i 

<h3>为什么不能省略 rank 或只做路径压缩</h3>
<p>只做路径压缩（无 rank）在极端 case 下仍可能让树高达到 O(log n)，而按秩合并能保证单次 <code>Find</code> 均摊接近 O(α(n))；反过来，只按秩不压缩，查询会退化成 O(log n)。两者缺一不可。</p>
<p>常见误写：</p>

• 在 Union 中漏掉 if uf.rank[px] == uf.rank[py] 的自增判断 → 后续合并失去平衡性
• Find 写成非递归但没更新父节点（只返回根，没压缩路径）→ 失去均摊优势
• 用 map[int]int 存 parent，键是任意整数（如离散化 ID）→ 性能差且易忘初始化，默认值 0 会被误认为有效根

处理非连续或负数 ID 怎么办

原生数组版只支持 0..n-1。如果输入是字符串、负数或稀疏 ID（如 1000001, 9999999），别硬套数组——先做离散化映射。

安全做法：

• 收集所有出现的 ID 到 slice，排序去重，用 sort.Search 查下标
• 或用 map[any]int 做 id → index 映射，再把 index 交给数组版 UnionFind
• 避免直接在 map[int]int 上实现 Find/Union —— 没有 rank 控制，无法保证复杂度，且 map 查找本身是 O(1) 平摊但常数大

例如：

ids := []int{105, -3, 999999}
sort.Ints(ids)
ids = unique(ids) // 去重
// 然后用 map[int]int{105: 0, -3: 1, 999999: 2} 做转换

并发场景下怎么安全使用

UnionFind 本身不是线程安全的。多个 goroutine 同时调用 Union 或 Find 会引发数据竞争。

简单方案：

• 用 sync.Mutex 包一层，适合读多写少、总操作数不大的情况
• 如果图是静态的（只构建一次，之后只读），可预先计算连通分量，用 map[int]int 缓存每个节点的根，之后并发读无锁
• 不要试图给每个 parent 元素加 atomic —— Find 是多步依赖，原子操作无法覆盖路径压缩逻辑

错误示范：atomic.LoadInt32(&uf.parent[x]) 只读一个值，但 Find 需要写回压缩后的根，必须整体加锁。

路径压缩和按秩合并的组合看似简单，但漏掉任一环节，实际运行中在大数据量下就会明显变慢；而 map 实现看似灵活，反而在高频调用时成为瓶颈。选数组 + 离散化 + 适度加锁，是 Go 里最稳的落地方式。

文中关于的知识介绍，希望对你的学习有所帮助！若是受益匪浅，那就动动鼠标收藏这篇《Go语言并查集实现详解》文章吧，也可关注golang学习网公众号了解相关技术文章。