-fbrk.png){kind=small}
在算法与数据结构的世界中，并查集（Union-Find Set）并不算复杂，但它的效率和应用场景却让人拍案叫绝。无论是在解决动态连通性问题，还是支持图相关算法（如Kruskal最小生成树），并查集都发挥了不可替代的作用。那么，究竟什么是并查集？它具有什么样的魔力？接下来，我们将通过严谨的讲解和恰到好处的趣味例子，带你深入了解这一简单且神奇的数据结构。
一、什么是并查集？
并查集是一种树状结构的数据结构，专门用于处理动态连通性问题。这类问题的核心在于：随着一系列动态操作（如合并或查询），我们需要能够快速判断两个元素是否属于同一个集合。
并查集通过维护节点间的父子关系，以树形方式存储集合。它主要支持两个核心操作：
合并（Union）： 将两个集合合并为一个集合。
查找（Find）： 找到某个元素所属集合的代表元素（即树的根节点）。
为了实现这些操作的高效性，我们可以借助两种经典优化策略：
路径压缩： 在
Find操作中，将路径上的所有节点直接指向根节点，从而缩短树的高度。按秩（或按集合大小）合并： 在
Union操作中，将“矮树”附着到“高树”上，保持树的结构尽量平衡。
简单来看，并查集就像是一群朋友的社交圈，每个人最初独自一人是一个小圈子。随着朋友之间不断建立联系，圈子变得越来越大。如果你想知道“某某人和某某人是不是一伙的”，或者“把两个社交圈合并”，并查集是效率极高的解决方案。
二、适用场景
并查集在实际应用中的覆盖范围十分广泛，几乎可以说，凡是涉及到“集合合并”和“集合归一”的问题，都可以考虑用并查集解决。例如：
图的连通性检测： 判断图中任意两节点是否连通。
最小生成树构建（如Kruskal算法）： 用于判断两条边是否会形成环。
等价类划分： 如字符串的等价判定问题或者变量互换问题。
动态连通问题： 比如岛屿数量问题、朋友圈数量计算等。
社交网络分析： 判断用户是否属于同一个社交群体。
风趣小例子
假设你是一名社交经理，维护一个社交网络。初始时，所有用户都是“单独行动”的孤狼。
有一天，用户A认识了用户B，于是你需要将A和B合并到同一个圈子里（Union操作）。
过段时间，突然有人来问：“用户C和用户D是不是朋友的朋友（即处于同一圈子）？”这时候你就需要查找C和D的根节点是否相同（Find操作）。
不管网络有多么庞大，这两个操作在并查集中都快到让人咂舌！
三、如何实现并查集？
1. 基于根大小的基础模板
我们先从一个简单的实现开始，基于根大小进行合并。
Golang实现
type UnionFind struct {
root map[int]int // 每个节点的父节点
}
// 初始化并查集
func NewUnionFind(nodes []int) UnionFind {
uf := UnionFind{root: map[int]int{}}
for _, node := range nodes {
uf.root[node] = node // 每个节点都是独立的“根”
}
return uf
}
// 找到节点x的根节点，并支持路径压缩
func (uf UnionFind) Find(x int) int {
if uf.root[x] != x {
uf.root[x] = uf.Find(uf.root[x]) // 路径压缩
}
return uf.root[x]
}
// 合并两个集合，基于根节点大小
func (uf UnionFind) Union(x, y int) {
rootx, rooty := uf.Find(x), uf.Find(y)
if rootx == rooty {
return // 两个节点已经属于同一集合
}
if rootx < rooty {
uf.root[rootx] = rooty
} else {
uf.root[rooty] = rootx
}
}2. 基于秩（Rank）的优化实现
虽然根大小合并是一个不错的策略，按秩合并（即比较树的深度或大小再决定合并方向）往往能更进一步提升性能。
Golang实现
type UnionFind struct {
root map[int]int // 记录每个节点的父节点
rank map[int]int // 记录每个节点的秩（即集合的“深度”）
}
// 初始化
func NewUnionFind(nodes []int) UnionFind {
uf := UnionFind{
root: map[int]int{},
rank: map[int]int{},
}
for _, node := range nodes {
uf.root[node] = node // 每个节点初始是自己的根
uf.rank[node] = 1 // 初始所有集合的秩为1
}
return uf
}
// Find操作，路径压缩
func (uf UnionFind) Find(x int) int {
if uf.root[x] != x {
uf.root[x] = uf.Find(uf.root[x])
}
return uf.root[x]
}
// Union操作，按秩合并
func (uf UnionFind) Union(x, y int) {
rootx, rooty := uf.Find(x), uf.Find(y)
if rootx == rooty { // 已经是同一集合，返回
return
}
// 比较根节点的秩
if uf.rank[rootx] < uf.rank[rooty] {
uf.root[rootx] = rooty
uf.rank[rooty] += uf.rank[rootx]
} else {
uf.root[rooty] = rootx
uf.rank[rootx] += uf.rank[rooty]
}
}按秩与按大小合并的差异
为了帮助大家更好地理解“按秩合并”为什么更优，举个形象的例子进行解释：
假设你管理了一支军队，每名士兵最初是独立的（单独的小集团）。当多个集团开始合并时，有两种策略：
按大小合并： 谁”更强“，谁就“当老大”。
按秩合并： 哪个集团人更多，哪个集团的领导就当老大。
按秩合并可以避免深层嵌套的问题，从而让“分支树”不那么复杂，这也就是它性能更高的原因。
评论