使用Go语言实现通用并查集数据结构-Golang-PHP中文网

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

聖光之護

发布： 2025-10-29 12:34:01

原创

353人浏览过

使用go语言实现通用并查集数据结构

本教程旨在指导如何利用Go语言的`interface{}`特性，将原先绑定特定类型（如`int64`）的并查集（DisjointSets）数据结构进行泛化，使其能够支持任意可作为映射键的类型（如`float64`、`string`等），而无需为每种类型重写核心逻辑。通过重构数据结构和方法签名，我们将展示如何实现一个高度可复用且类型安全的并查集。

在Go语言中，实现泛型数据结构通常有几种方法，其中最常见且在Go 1.18之前广泛使用的是interface{}。对于像并查集这种主要依赖于元素比较和赋值操作的数据结构，interface{}提供了一种优雅的“鸭子类型”解决方案。

理解并查集（DisjointSets）

并查集是一种用于处理不相交集合的树形数据结构，它支持两种主要操作：

MakeSet(x)：创建一个包含元素x的新集合。
FindSet(x)：查找元素x所属集合的代表元素（根节点）。
Union(x, y)：合并包含元素x和y的两个集合。

原始的并查集实现通常会绑定到特定的数据类型，例如：

立即学习“go语言免费学习笔记（深入）”；

type DisjointSets struct {
    ranks map[int64]int64
    p map[int64]int64
}

// New returns a new DisjointSets
func NewDisjointSets() *DisjointSets {
    d := DisjointSets{map[int64]int64{}, map[int64]int64{}}
    return &d
}

// MakeSet adds element x to the disjoint sets in its own set
func (d *DisjointSets) MakeSet(x int64) {
    d.p[x] = x
    d.ranks[x] = 0
}

// Link assigns x to y or vice versa, depending on the rank of each
func (d *DisjointSets) Link(x, y int64) {
    if d.ranks[x] > d.ranks[y] {
        d.p[y] = x
    } else {
        d.p[x] = y
        if d.ranks[x] == d.ranks[y] {
            d.ranks[y] += 1
        }
    }
}

// FindSet returns the set in which an element x sits
func (d *DisjointSets) FindSet(x int64) int64 {
    if x != d.p[x] {
        d.p[x] = d.FindSet(d.p[x])
    }
    return d.p[x]
}

// Union combines two elements x and y into one set.
func (d *DisjointSets) Union(x, y int64) {
    d.Link(d.FindSet(x), d.FindSet(y))
}

登录后复制

上述代码中，所有的元素类型都被硬编码为int64。为了使其能够处理float64、string或任何其他类型，我们需要引入interface{}。

利用 interface{} 实现泛型并查集

Go语言的interface{}（空接口）可以表示任何类型的值。当我们将数据结构中的元素类型从int64替换为interface{}时，Go运行时将能够存储和处理不同类型的数据。关键在于，并查集的操作（如p[x] = x或x != d.p[x]）仅依赖于值的赋值和比较，而这些操作对于Go中所有可作为映射键的类型都是支持的。

重构 DisjointSets 结构和方法

我们将原始代码中的所有int64类型替换为interface{}：

即构数智人

即构数智人是由即构科技推出的AI虚拟数字人视频创作平台，支持数字人形象定制、短视频创作、数字人直播等。

查看详情

package main

import "fmt"

// DisjointSets 结构体现在使用 interface{} 来存储任意类型的元素
type DisjointSets struct {
    ranks map[interface{}]int64
    p     map[interface{}]interface{}
}

// NewDisjointSets 返回一个新的 DisjointSets 实例
func NewDisjointSets() *DisjointSets {
    d := DisjointSets{
        ranks: make(map[interface{}]int64),
        p:     make(map[interface{}]interface{}),
    }
    return &d
}

// MakeSet 添加元素 x 到并查集中，作为其自身集合的代表
func (d *DisjointSets) MakeSet(x interface{}) {
    // 检查元素是否已存在，避免重复初始化
    if _, ok := d.p[x]; !ok {
        d.p[x] = x
        d.ranks[x] = 0
    }
}

// Link 根据秩（rank）合并两个集合的代表元素
func (d *DisjointSets) Link(x, y interface{}) {
    if d.ranks[x] > d.ranks[y] {
        d.p[y] = x
    } else {
        d.p[x] = y
        if d.ranks[x] == d.ranks[y] {
            d.ranks[y] += 1
        }
    }
}

// FindSet 查找元素 x 所属集合的代表元素，并进行路径压缩
func (d *DisjointSets) FindSet(x interface{}) interface{} {
    // 如果 x 不是其自身的代表，则递归查找并压缩路径
    if x != d.p[x] {
        d.p[x] = d.FindSet(d.p[x])
    }
    return d.p[x]
}

// Union 合并包含元素 x 和 y 的两个集合
func (d *DisjointSets) Union(x, y interface{}) {
    d.Link(d.FindSet(x), d.FindSet(y))
}

登录后复制

泛型并查集的使用示例

现在，这个DisjointSets结构可以与任何可作为映射键的类型一起工作。

func main() {
    ds := NewDisjointSets()

    // 使用 int 类型
    ds.MakeSet(1)
    ds.MakeSet(2)
    ds.MakeSet(3)
    ds.MakeSet(4)

    ds.Union(1, 2)
    ds.Union(3, 4)
    ds.Union(2, 3)

    fmt.Printf("FindSet(1): %v\n", ds.FindSet(1)) // 预期：1 或 2 或 3 或 4
    fmt.Printf("FindSet(4): %v\n", ds.FindSet(4)) // 预期：与 FindSet(1) 相同

    // 使用 string 类型
    ds.MakeSet("apple")
    ds.MakeSet("banana")
    ds.MakeSet("cherry")

    ds.Union("apple", "banana")
    fmt.Printf("FindSet(\"apple\"): %v\n", ds.FindSet("apple"))
    fmt.Printf("FindSet(\"banana\"): %v\n", ds.FindSet("banana"))
    fmt.Printf("FindSet(\"cherry\"): %v\n", ds.FindSet("cherry"))

    // 使用 float64 类型
    ds.MakeSet(3.14)
    ds.MakeSet(2.71)
    ds.Union(3.14, 2.71)
    fmt.Printf("FindSet(3.14): %v\n", ds.FindSet(3.14))
    fmt.Printf("FindSet(2.71): %v\n", ds.FindSet(2.71))

    // 混合类型 (谨慎使用，通常不推荐在同一个并查集中混合不相关的类型)
    ds.Union("apple", 3.14) // 这将合并 string 和 float64 所在的集合
    fmt.Printf("FindSet(\"apple\"): %v\n", ds.FindSet("apple"))
    fmt.Printf("FindSet(3.14): %v\n", ds.FindSet(3.14))
}

登录后复制

运行上述代码，您会发现并查集能够正确处理不同类型的数据。

注意事项与总结

可作为映射键的类型 (Map Key Types):
- interface{} 方案的核心在于 Go 语言对映射键的要求。只有可比较的类型才能用作映射键。这包括：
  - 布尔型、数值型（int, float, complex等）、字符串。
  - 指针、通道（channel）。
  - 接口类型（如果其动态值是可比较的）。
  - 结构体类型，如果其所有字段都是可比较的。
  - 数组类型，如果其元素类型是可比较的。
- 切片（slice）、映射（map）和函数（function）是不可比较的，因此不能直接作为interface{}类型的值存储在作为映射键的map[interface{}]中。
- 如果尝试将不可比较的类型作为元素添加到并查集中，Go运行时会在尝试将其用作映射键时引发panic。
类型安全与运行时检查:
- 使用interface{}实现泛型，Go编译器无法在编译时提供严格的类型检查，所有类型检查都推迟到运行时。这意味着如果误用，例如在一个期望int的上下文中尝试对string进行算术操作（本例中不涉及），将会导致运行时错误。
- 对于并查集而言，由于其操作仅限于赋值和比较，interface{}足以满足需求，且不易引入类型相关的运行时错误。
性能考量:
- 将具体类型存储到interface{}中会涉及“装箱”（boxing）操作，即将值封装到一个接口值中。这可能会带来轻微的性能开销和额外的内存分配。对于大多数应用场景，这种开销通常可以忽略不计，尤其是在并查集这类操作数量通常不是极高的场景下。
Go 1.18+ 的泛型:
- Go 1.18及更高版本引入了真正的泛型（type parameters）。如果您的项目使用Go 1.18或更高版本，可以使用类型参数来更显式、更安全地定义泛型并查集，例如 type DisjointSets[T comparable] struct { ... }。这将提供编译时类型检查，并且通常具有更好的性能。然而，对于仅依赖于可比较性（equality）的场景，interface{}仍然是一个有效且简洁的解决方案，尤其是在不希望引入类型参数约束的复杂性时。