如何用Go语言实现通用并查集数据结构

并查集（Union-Find）是一种树型数据结构，主要用于处理一些不相交集合的合并及查询问题，核心操作包括查找元素所在集合的根节点、合并两个元素所在的集合。传统并查集实现通常针对特定类型，复用性较差，而Go语言1.18版本引入泛型后，我们可以实现支持任意可比较类型的通用并查集。

并查集核心原理

并查集的核心逻辑基于两个优化点：路径压缩和按秩合并。路径压缩是在查找根节点时，将查找路径上的所有节点直接挂载到根节点下，减少后续查找的深度；按秩合并是在合并两个集合时，将高度较小的树挂载到高度较大的树的根节点下，避免树的高度过高。

核心操作说明

• 查找（Find）：找到元素所在集合的根节点，过程中触发路径压缩
• 合并（Union）：判断两个元素是否在同一集合，不在则合并两个集合
• 查询连通性（Connected）：判断两个元素是否属于同一个集合

通用并查集设计思路

要实现通用并查集，我们需要使用Go语言的泛型特性，约束类型参数必须是可比较的，这样才可以作为map的键使用。并查集内部维护两个map：一个存储每个元素对应的父节点，一个存储每个根节点对应的秩（树的高度）。

结构定义

首先定义通用并查集的结构体，类型参数T需要满足comparable约束：

package main

import "fmt"

// UnionFind 通用并查集结构体，T为可比较的任意类型
type UnionFind[T comparable] struct {
    parent map[T]T // 存储每个元素的父节点
    rank   map[T]int // 存储每个根节点对应的秩（树的高度）
}

初始化方法

初始化并查集时，需要创建两个空的map，并为后续添加的元素动态初始化父节点和秩：

// NewUnionFind 创建新的通用并查集实例
func NewUnionFind[T comparable]() *UnionFind[T] {
    return &UnionFind[T]{
        parent: make(map[T]T),
        rank:   make(map[T]int),
    }
}

核心方法实现

查找方法实现

查找方法需要先判断元素是否已经在parent中，如果不在则将其父节点初始化为自身，秩初始化为1。查找过程中执行路径压缩优化：

// Find 查找元素x所在集合的根节点，同时执行路径压缩
func (uf *UnionFind[T]) Find(x T) T {
    // 如果元素不存在，初始化其parent为自身，rank为1
    if _, ok := uf.parent[x]; !ok {
        uf.parent[x] = x
        uf.rank[x] = 1
    }
    // 路径压缩：如果父节点不是自身，递归查找根节点，并将当前节点的父节点直接设为根节点
    if uf.parent[x] != x {
        uf.parent[x] = uf.Find(uf.parent[x])
    }
    return uf.parent[x]
}

合并方法实现

合并方法先找到两个元素的根节点，如果根节点不同则按秩合并，将秩较小的树挂载到秩较大的树的根节点下：

// Union 合并元素x和元素y所在的集合
func (uf *UnionFind[T]) Union(x, y T) {
    rootX := uf.Find(x)
    rootY := uf.Find(y)
    // 如果根节点相同，说明已经在同一集合，不需要合并
    if rootX == rootY {
        return
    }
    // 按秩合并：秩小的树挂载到秩大的树的根节点下
    if uf.rank[rootX] < uf.rank[rootY] {
        uf.parent[rootX] = rootY
    } else if uf.rank[rootX] > uf.rank[rootY] {
        uf.parent[rootY] = rootX
    } else {
        // 秩相等时，任意合并，合并后根节点的秩加1
        uf.parent[rootY] = rootX
        uf.rank[rootX]++
    }
}

连通性查询方法

查询两个元素是否连通，只需要判断它们的根节点是否相同：

// Connected 判断元素x和元素y是否连通（属于同一集合）
func (uf *UnionFind[T]) Connected(x, y T) bool {
    return uf.Find(x) == uf.Find(y)
}

使用示例

下面展示通用并查集的使用方式，分别测试整型和字符串类型的场景：

func main() {
    // 测试整型类型的并查集
    fmt.Println("整型并查集测试：")
    ufInt := NewUnionFind[int]()
    ufInt.Union(1, 2)
    ufInt.Union(2, 3)
    fmt.Println("1和3是否连通：", ufInt.Connected(1, 3)) // 输出 true
    fmt.Println("1和4是否连通：", ufInt.Connected(1, 4)) // 输出 false

    // 测试字符串类型的并查集
    fmt.Println("n字符串并查集测试：")
    ufStr := NewUnionFind[string]()
    ufStr.Union("北京", "上海")
    ufStr.Union("上海", "广州")
    fmt.Println("北京和广州是否连通：", ufStr.Connected("北京", "广州")) // 输出 true
    fmt.Println("北京和深圳是否连通：", ufStr.Connected("北京", "深圳")) // 输出 false
}

实现注意事项

在使用该通用并查集时，需要注意以下几点：

• 类型参数T必须满足comparable约束，即支持==和!=操作，否则无法作为map的键使用
• 查找方法中会对未初始化父节点的元素进行自动初始化，不需要提前手动添加元素
• 路径压缩和按秩合并的优化可以将单次操作的时间复杂度降低到接近O(1)，适合处理大规模数据

这个通用并查集实现可以适配任意可比较类型，避免了针对不同类型重复编写并查集逻辑的问题，在需要处理集合合并查询的场景中可以直接复用。

Go语言并查集通用数据结构Union_Find算法实现修改时间：2026-06-17 06:03:36