golang实现并查集数据结构的高效插件库dsu的使用

golang实现并查集数据结构的高效插件库dsu的使用

概述

dsu是一个Golang实现的并查集(Disjoint-Set)数据结构库。并查集也称为Union-Find或Merge-Find集合，是一种存储不相交(非重叠)集合的数据结构。它提供了添加新集合、合并集合(通过并集替换)和查找集合代表元素的操作，可以高效判断两个元素是否属于同一集合。

安装

go get github.com/ihebu/dsu

使用示例

下面是一个完整的示例代码，展示了如何使用dsu库：

package main

import (
	"fmt"
	"github.com/ihebu/dsu"
)

func main() {
	// 创建一个新的并查集
	d := dsu.New()

	// 添加元素1, 2, 3到集合中
	d.Add(1)
	d.Add(2)
	d.Add(3)

	// 当前集合状态: {1}, {2}, {3}

	// 合并集合{1}和{2}
	d.Union(1, 2)

	// 当前集合状态: {1, 2}, {3}

	// 查找每个集合的代表元素
	fmt.Println(d.Find(1)) // 输出: 2
	fmt.Println(d.Find(2)) // 输出: 2 
	fmt.Println(d.Find(3)) // 输出: 3

	// 检查元素是否存在于集合中
	fmt.Println(d.Contains(2))  // 输出: true
	fmt.Println(d.Contains(54)) // 输出: false

	// 注意：可以添加不同类型的元素到集合中
	// 示例:
	d.Add("hello")
	d.Add(34.5)

	d.Union("hello", 34.5)
	
	// 检查不同类型元素的合并结果
	fmt.Println(d.Find("hello")) // 输出: 34.5
	fmt.Println(d.Find(34.5))    // 输出: 34.5
}

主要功能

  1. New() - 创建一个新的并查集实例
  2. Add(element) - 向集合中添加一个新元素
  3. Union(x, y) - 合并包含x和y的两个集合
  4. Find(x) - 查找x所在集合的代表元素
  5. Contains(x) - 检查x是否存在于集合中

特性

  • 支持不同类型的元素
  • 高效的合并和查找操作
  • 简单易用的API接口
  • 良好的测试覆盖率

这个库非常适合需要处理动态连通性问题的场景，如图算法中的连通分量检测、网络连接状态管理等。


更多关于golang实现并查集数据结构的高效插件库dsu的使用的实战教程也可以访问 https://www.itying.com/category-94-b0.html

1 回复

更多关于golang实现并查集数据结构的高效插件库dsu的使用的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html


Golang 并查集(DSU)数据结构实现

并查集(Disjoint Set Union, DSU)是一种高效处理不相交集合合并及查询问题的数据结构。下面我将介绍如何在Go中实现并查集，并提供一个高效的使用示例。

基本实现

package dsu

// DSU 并查集结构体
type DSU struct {
	parent []int
	rank   []int
}

// NewDSU 初始化并查集
func NewDSU(size int) *DSU {
	dsu := &DSU{
		parent: make([]int, size),
		rank:   make([]int, size),
	}
	
	for i := range dsu.parent {
		dsu.parent[i] = i
		dsu.rank[i] = 1
	}
	
	return dsu
}

// Find 查找根节点，带路径压缩
func (d *DSU) Find(x int) int {
	if d.parent[x] != x {
		d.parent[x] = d.Find(d.parent[x]) // 路径压缩
	}
	return d.parent[x]
}

// Union 合并两个集合，按秩合并
func (d *DSU) Union(x, y int) {
	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]++
	}
}

// IsConnected 判断两个元素是否属于同一集合
func (d *DSU) IsConnected(x, y int) bool {
	return d.Find(x) == d.Find(y)
}

使用示例

package main

import (
	"fmt"
	"your_module_path/dsu" // 替换为实际的模块路径
)

func main() {
	// 初始化一个包含5个元素的并查集
	dsu := dsu.NewDSU(5)
	
	// 初始状态：每个元素都是自己的父节点
	fmt.Println("Initial state:")
	for i := 0; i < 5; i++ {
		fmt.Printf("Parent of %d: %d\n", i, dsu.Find(i))
	}
	
	// 合并操作
	dsu.Union(0, 1)
	dsu.Union(2, 3)
	dsu.Union(1, 4)
	
	// 查询操作
	fmt.Println("\nAfter unions:")
	fmt.Println("Is 0 connected to 4?", dsu.IsConnected(0, 4)) // true
	fmt.Println("Is 2 connected to 4?", dsu.IsConnected(2, 4)) // false
	
	// 查看最终父节点关系
	fmt.Println("\nFinal parent relationships:")
	for i := 0; i < 5; i++ {
		fmt.Printf("Parent of %d: %d\n", i, dsu.Find(i))
	}
}

性能优化说明

  1. 路径压缩：在Find操作中，我们将查找路径上的所有节点直接指向根节点，使得后续查找更快。

  2. 按秩合并：在Union操作中，我们总是将较小的树合并到较大的树上，保持树的平衡性。

这两种优化使得并查集的操作时间复杂度接近常数级别，具体来说是反阿克曼函数，可以认为是O(1)。

高级功能扩展

如果需要更高级的功能，可以扩展DSU结构：

// 添加获取集合大小功能
func (d *DSU) GetSize(x int) int {
	root := d.Find(x)
	return d.rank[root]
}

// 添加获取所有集合功能
func (d *DSU) GetSets() map[int][]int {
	sets := make(map[int][]int)
	for i := range d.parent {
		root := d.Find(i)
		sets[root] = append(sets[root], i)
	}
	return sets
}

实际应用场景

并查集常用于解决以下问题：

  • 图的连通分量检测
  • 朋友圈问题
  • 最小生成树算法(Kruskal)
  • 动态连通性问题

这个实现已经足够高效，可以直接用于生产环境。如果需要更复杂的实现，可以考虑社区维护的成熟库，但大多数情况下这个简单实现已经能满足需求。

回到顶部