什么是并查集？
并查集(Union-Find)是一种树型的数据结构，用于处理一些不相交集合的合并(Union)及查询(Find)问题。它支持以下两种基本操作：
- 查找(Find)：确定元素属于哪个子集
- 合并(Union)：将两个子集合并为一个集合
并查集在计算机科学中有广泛应用，如：
- 图的连通分量计算
- Kruskal最小生成树算法
- 网络连接问题
- 社交网络中的朋友圈计算
并查集的基本实现
数据结构表示
在Golang中，我们可以使用一个数组(parent)来表示并查集的森林结构：
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)
查找元素所在集合的根节点：
func (uf *UnionFind) Find(x int) int {
for uf.parent[x] != x {
x = uf.parent[x]
}
return x
}
合并操作(Union)
将两个元素所在的集合合并：
func (uf *UnionFind) Union(x, y int) {
rootX := uf.Find(x)
rootY := uf.Find(y)
if rootX == rootY {
return
}
uf.parent[rootX] = rootY
uf.count--
}
优化技术
1. 路径压缩(Path Compression)
在查找过程中，将路径上的所有节点直接连接到根节点，减少后续查找的深度：
func (uf *UnionFind) Find(x int) int {
if uf.parent[x] != x {
uf.parent[x] = uf.Find(uf.parent[x]) // 路径压缩
}
return uf.parent[x]
}
2. 按秩合并(Union by Rank)
维护一个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) {
rootX := uf.Find(x)
rootY := uf.Find(y)
if rootX == rootY {
return
}
// 按秩合并
if uf.rank[rootX] > uf.rank[rootY] {
uf.parent[rootY] = rootX
} else if uf.rank[rootX] < uf.rank[rootY] {
uf.parent[rootX] = rootY
} else {
uf.parent[rootY] = rootX
uf.rank[rootX]++
}
uf.count--
}
开源实现分析
1. github.com/yourbasic/uf
这是一个简洁高效的Golang并查集实现，特点包括：
- 使用路径压缩优化
- 接口简洁明了
- 支持动态扩容
// 创建包含n个元素的并查集
uf := uf.New(n)
// 合并两个元素
uf.Union(a, b)
// 查找元素所属集合
root := uf.Find(a)
// 获取连通分量数量
count := uf.Count()
2. github.com/kelvinlau/go-unionfind
这个实现提供了更多功能：
- 支持按大小合并(Union by Size)
- 提供Connected方法检查连通性
- 支持重置并查集
uf := unionfind.New(n)
uf.Union(a, b)
if uf.Connected(a, b) {
fmt.Println("a and b are connected")
}
3. github.com/wangzheng0822/algo
这个算法库中的并查集实现特点：
- 同时使用路径压缩和按秩合并
- 提供详细的文档和示例
- 支持泛型接口
实际应用示例
1. 计算图的连通分量
func countComponents(n int, edges [][]int) int {
uf := NewUnionFind(n)
for _, edge := range edges {
uf.Union(edge[0], edge[1])
}
return uf.count
}
2. 判断图中是否有环
func hasCycle(n int, edges [][]int) bool {
uf := NewUnionFind(n)
for _, edge := range edges {
x, y := edge[0], edge[1]
if uf.Find(x) == uf.Find(y) {
return true
}
uf.Union(x, y)
}
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
}
性能分析
- 时间复杂度：
• 仅路径压缩或按秩合并：O(alpha(n))
• 同时使用路径压缩和按秩合并：O(alpha(n))
其中alpha(n)是反阿克曼函数，增长极其缓慢，可以认为是常数时间。
- 空间复杂度：O(n)
总结
并查集是一种高效处理动态连通性问题的数据结构。通过路径压缩和按秩合并优化，可以达到接近常数时间的操作复杂度。Golang的简洁语法使其实现并查集尤为优雅，适合在各种需要处理连通性问题的场景中使用。
在实际应用中，根据具体需求选择合适的优化策略和开源实现可以大大提高开发效率和运行性能。对于大多数场景，同时使用路径压缩和按秩合并的实现是最佳选择。
