7 并查集的基本操作

在了解了图的高级算法（如最小生成树算法，包括 Kruskal 和 Prim 算法）之后，接下来我们将深入探讨并查集（Union-Find）这一重要数据结构。并查集广泛应用于动态连通性问题，特别是在涉及到合并和查询操作的场景中。

并查集的基本概念

并查集是一种用于处理不交集（disjoint sets）合并和查询的数据结构。它支持两种基本操作：

1. 合并（Union）：将两个集合合并成一个集合。
2. 查找（Find）：查找一个元素所在的集合，并返回该集合的代表（或根）。

基本概念示例

假设我们有以下的集合：

• 集合 A: {1, 2, 3}
• 集合 B: {4, 5}
• 集合 C: {6}

在开始时，每个元素都是一个独立的集合。我们需要进行如下操作：

• 合并集合 A 和集合 B
• 查询元素 2 所在的集合
• 合并集合 B 和集合 C

经过上述操作后，集合的状态会改变，并查集将帮助我们在这些操作中保持高效性。

数据结构的实现

我们将通过以下两种方法来实现并查集的基本操作：

• 使用数组表示父节点
• 使用路径压缩优化查找过程

在实现之前，让我们先定义 parent 数组，其中 parent[i] 表示元素 i 的父节点。初始化时，每个元素的父节点指向自己，即每个元素都是自己的代表。

初始化

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))

    def find(self, p):
        # 查找操作
        if self.parent[p] != p:
            self.parent[p] = self.find(self.parent[p])  # 路径压缩
        return self.parent[p]

    def union(self, p, q):
        # 合并操作
        rootP = self.find(p)
        rootQ = self.find(q)
        if rootP != rootQ:
            self.parent[rootP] = rootQ  # 将 P 的根指向 Q 的根

查找操作

def find(self, p):
    if self.parent[p] != p:
        self.parent[p] = self.find(self.parent[p])  # 路径压缩
    return self.parent[p]

这个 find 方法返回元素 p 的根节点，而在查找过程中，我们对路径进行压缩，将所有访问过的节点直接连接到根节点，达到优化查找效率的目的。

合并操作

def union(self, p, q):
    rootP = self.find(p)
    rootQ = self.find(q)
    if rootP != rootQ:
        self.parent[rootP] = rootQ  # 将 P 的根指向 Q 的根

在这个 union 方法中，我们首先找到要合并的两个元素的根节点，然后将一个根节点指向另一个根节点，用以合并这两个集合。

案例分析

让我们以一个具体的案例来演示并查集的基本操作。

假设我们有五个元素，范围在 0 到 4 之间，并希望进行以下操作：

1. 合并元素 0 和 1
2. 合并元素 1 和 2
3. 查询元素 0 的根
4. 合并元素 3 和 4
5. 查询元素 2 的根

执行代码示例

uf = UnionFind(5)

# 合并操作
uf.union(0, 1)  # 将 0 和 1 合并
uf.union(1, 2)  # 将 1 和 2 合并

# 查询操作
print(uf.find(0))  # 输出 2，代表集合中的根
print(uf.find(1))  # 输出 2，仍然是同一个集合的根

uf.union(3, 4)  # 将 3 和 4 合并

# 再次查询，2 仍然是 0 和 1 的根
print(uf.find(2))  # 输出 2

输出结果

执行上述代码后，我们将在控制台看到：

2
2
2

这说明元素 0, 1, 和 2 都属于同一个集合，而 3 和 4 也形成了一个新集合。

总结

并查集是一种高效的数据结构，适用于处理动态连通性问题。通过支持高效的合并和查找操作，特别是路径压缩技术的使用，使得该结构在处理大量快速合并和查询时表现出色。

在下一篇中，我们将深入探讨并查集的进一步优化，包括按秩合并的策略，让我们期待更多提升效率的方法！