发布于 

并查集 | 笔记整理!

并查集 | 笔记整理!

并查集

结构体

1
2
3
4
type UnionFind struct {
	parent []int
	rank   []int
}

常规操作

NewUnionFind 函数用于创建一个新的并查集实例。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func NewUnionFind(size int) *UnionFind {
	parent := make([]int, size)
	rank := make([]int, size)

	// 初始化
	for i := 0; i < size; i++ {
		parent[i] = i
		rank[i] = 0
	}
	return &UnionFind{
		parent: parent,
		rank:   rank,
	}
}

路径压缩

该函数的作用是查找元素 x 所属的集合的根节点，并在查找过程中进行路径压缩，将元素 x 到根节点路径上的所有节点直接连接到根节点，以提高后续查找的效率。

1
2
3
4
5
6
func (uf *UnionFind) Find(x int) int {
	if uf.parent[x] != x {
		uf.parent[x] = uf.Find(uf.parent[x])
	}
	return uf.parent[x]
}

按秩合并

并查集中的按秩合并优化策略，它基于每个集合的秩（rank）来决定合并时哪个集合的根节点指向哪个集合的根节点。

首先，秩是一个表示集合高度（或者近似高度）的指标。初始时，每个元素的秩都为 0。

在合并两个集合时，通过比较它们的秩，可以决定将一个集合的根节点指向另一个集合的根节点。具体的逻辑如下：

  1. 如果 uf.rank[rootX] < uf.rank[rootY]，表示集合 Y 的秩更大，即集合 Y 的高度更大。在这种情况下，将集合 X 的根节点的父节点指向集合 Y 的根节点，因为将树高度较小的集合合并到树高度较大的集合中，不会增加整体树的高度。
  2. 如果 uf.rank[rootX] > uf.rank[rootY]，表示集合 X 的秩更大，同理，将集合 Y 的根节点的父节点指向集合 X 的根节点。
  3. 如果 uf.rank[rootX] == uf.rank[rootY]，表示集合 X 和集合 Y 的秩相同，此时可以选择将集合 X 的根节点指向集合 Y 的根节点，也可以选择将集合 Y 的根节点指向集合 X 的根节点。在这里，我们选择将集合 Y 的根节点指向集合 X 的根节点，并且将集合 X 的秩加一，因为合并后，整个树的高度会增加一层。

这种按秩合并的优化策略可以有效地减小树的高度，提高并查集操作的效率，避免退化成链表式的数据结构。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func (uf *UnionFind) Union(x, y int) {
	px, py := uf.Find(x), uf.Find(y)
	if px == py {
		return
	}
	rx, ry := uf.rank[px], uf.rank[py]
	if rx < ry {
		uf.rank[rx] = ry
	} else if rx > ry {
		uf.rank[ry] = rx
	} else {
		uf.rank[rx] = ry
		uf.rank[rx]++
	}
}

辅助操作

IsConnected 函数用于判断两个元素 x 和 y 是否属于同一个集合。

1
2
3
func (uf *UnionFind) IsConnected(x, y int) bool {
	return uf.Find(x) == uf.Find(y)
}

Getsets 方法，可以获取并查集中的所有集合以及它们的元素列表

1
2
3
4
5
6
7
8
func (uf *UnionFind) Getsets() map[int][]int {
	sets := make(map[int][]int)
	for i := 0; i < len(uf.parent); i++ {
		root := uf.Find(i)
		sets[root] = append(sets[root], i)
	}
	return sets
}
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

快来参与讨论吧