Go语言中如何优雅地泛化不相交集（DisjointSets）数据结构

不相交集（DisjointSets）也叫并查集，用来维护一组互不相交的集合，主要提供查找根节点和合并两个集合的能力。在Go语言支持泛型之后，我们可以把原本只能用于int的写法推广到任意可比较类型，从而避免重复代码并保持类型安全。

为什么需要泛化不相交集

早期Go没有泛型时，不相交集通常基于map[int]int实现，如果元素是整数以外的类型就要重写整套逻辑。使用泛型后，只要元素类型满足可比较约束，就能复用同一份实现，既减少出错也提升可读性。

泛型不相交集设计

核心思路是用一个map保存每个元素对应的父节点，再用一个map保存秩（高度或大小）以优化合并。下面给出完整且可直接使用的实现。

package disjoint

type DisjointSet[T comparable] struct {
	parent map[T]T
	rank   map[T]int
}

// NewDisjointSet 创建一个新的不相交集
func NewDisjointSet[T comparable]() *DisjointSet[T] {
	return &DisjointSet[T]{
		parent: make(map[T]T),
		rank:   make(map[T]int),
	}
}

// Add 将元素单独加入为一个集合
func (d *DisjointSet[T]) Add(x T) {
	if _, ok := d.parent[x]; !ok {
		d.parent[x] = x
		d.rank[x] = 0
	}
}

// Find 查找元素的根，带路径压缩
func (d *DisjointSet[T]) Find(x T) T {
	if d.parent[x] != x {
		d.parent[x] = d.Find(d.parent[x])
	}
	return d.parent[x]
}

// Union 合并两个元素所在集合，按秩合并
func (d *DisjointSet[T]) Union(x, y T) {
	d.Add(x)
	d.Add(y)
	rootX := d.Find(x)
	rootY := d.Find(y)
	if rootX == rootY {
		return
	}
	if d.rank[rootX] < d.rank[rootY] {
		d.parent[rootX] = rootY
	} else if d.rank[rootX] > d.rank[rootY] {
		d.parent[rootY] = rootX
	} else {
		d.parent[rootY] = rootX
		d.rank[rootX]++
	}
}

// Connected 判断两元素是否连通
func (d *DisjointSet[T]) Connected(x, y T) bool {
	d.Add(x)
	d.Add(y)
	return d.Find(x) == d.Find(y)
}

使用示例

下面代码展示如何用该结构处理字符串类型的节点，以及处理自定义结构体（需保证可比较）。

package main

import (
	"fmt"
	"disjoint"
)

func main() {
	ds := disjoint.NewDisjointSet[string]()
	ds.Union("a", "b")
	ds.Union("b", "c")
	fmt.Println(ds.Connected("a", "c")) // true
	fmt.Println(ds.Connected("a", "d")) // false

	type Point struct{ X, Y int }
	ds2 := disjoint.NewDisjointSet[Point]()
	p1 := Point{1, 2}
	p2 := Point{1, 2}
	ds2.Union(p1, p2)
	fmt.Println(ds2.Connected(p1, p2)) // true
}

注意事项

• 元素类型必须使用 comparable 约束，否则无法作为 map 的键。
• Find 中的递归路径压缩在元素极多且链极长时可能栈溢出，可改为迭代写法。
• 如果只用整数且追求极致性能，仍可用切片代替 map 以减少开销。

小结

借助 Go 泛型，不相交集可以优雅地泛化到任意可比较类型，配合路径压缩与按秩合并，能在多数场景下提供接近常数的操作效率。将上述代码放入公共包后，业务层就能专注连通性逻辑而不必关心底层实现。

GoDisjointSets泛型修改时间：2026-07-28 08:54:34