并查集是一种树形数据结构,用于处理不相交集合的合并及查询问题,支持「查找」和「合并」两种操作,常用于解决连通性问题、最小生成树和动态连通性等问题。
并查集是一种树形的数据结构,用于处理不相交集合(Disjoint Set)的合并及查询问题。它主要支持两种操作:
名称"并查集"直接体现了它的核心功能:合并集合与查询元素所属集合。在英文中,它通常被称为"Union-Find"数据结构或"Disjoint-Set"数据结构。
并查集的基本思想是使用树形结构来表示每个集合,树的根节点作为集合的代表元素。
创建n个单元素集合,每个元素初始时都是独立的集合。
查找元素所属的集合,通常是查找元素所在树的根节点。
将两个集合合并为一个集合,通常是将一个集合的根节点连接到另一个集合的根节点上。
▼Java复制代码public class UnionFind { private int[] parent; // 记录每个节点的父节点 private int[] rank; // 记录每个根节点对应树的高度 // 初始化 public UnionFind(int size) { parent = new int[size]; rank = new int[size]; // 初始时,每个元素自成一个集合,父节点指向自己 for (int i = 0; i < size; i++) { parent[i] = i; rank[i] = 0; } } // 查找操作(带路径压缩) public int find(int x) { if (parent[x] != x) { // 路径压缩:将x的父节点直接设为根节点 parent[x] = find(parent[x]); } return parent[x]; } // 合并操作(按秩合并) public void union(int x, int y) { int rootX = find(x); int rootY = find(y); // 如果已经在同一集合中,不需要合并 if (rootX == rootY) { return; } // 按秩合并:将秩较小的树连接到秩较大的树下 if (rank[rootX] < rank[rootY]) { parent[rootX] = rootY; } else if (rank[rootX] > rank[rootY]) { parent[rootY] = rootX; } else { // 秩相同时,随便选一个作为根,并将新根的秩+1 parent[rootY] = rootX; rank[rootX]++; } } // 判断两个元素是否在同一集合 public boolean isConnected(int x, int y) { return find(x) == find(y); } }
▼Python复制代码class UnionFind: def __init__(self, size): # 初始化,每个元素的父节点是自己 self.parent = list(range(size)) # 记录每个根节点对应树的高度 self.rank = [0] * size def find(self, x): # 查找操作(带路径压缩) if self.parent[x] != x: # 路径压缩:将x的父节点直接设为根节点 self.parent[x] = self.find(self.parent[x]) return self.parent[x] def union(self, x, y): # 合并操作(按秩合并) root_x = self.find(x) root_y = self.find(y) # 如果已经在同一集合中,不需要合并 if root_x == root_y: return # 按秩合并:将秩较小的树连接到秩较大的树下 if self.rank[root_x] < self.rank[root_y]: self.parent[root_x] = root_y elif self.rank[root_x] > self.rank[root_y]: self.parent[root_y] = root_x else: # 秩相同时,随便选一个作为根,并将新根的秩+1 self.parent[root_y] = root_x self.rank[root_x] += 1 def is_connected(self, x, y): # 判断两个元素是否在同一集合 return self.find(x) == self.find(y)
▼Javascript复制代码class UnionFind { constructor(size) { // 初始化,每个元素的父节点是自己 this.parent = Array.from({length: size}, (_, i) => i); // 记录每个根节点对应树的高度 this.rank = Array(size).fill(0); } // 查找操作(带路径压缩) find(x) { if (this.parent[x] !== x) { // 路径压缩:将x的父节点直接设为根节点 this.parent[x] = this.find(this.parent[x]); } return this.parent[x]; } // 合并操作(按秩合并) union(x, y) { const rootX = this.find(x); const rootY = this.find(y); // 如果已经在同一集合中,不需要合并 if (rootX === rootY) { return; } // 按秩合并:将秩较小的树连接到秩较大的树下 if (this.rank[rootX] < this.rank[rootY]) { this.parent[rootX] = rootY; } else if (this.rank[rootX] > this.rank[rootY]) { this.parent[rootY] = rootX; } else { // 秩相同时,随便选一个作为根,并将新根的秩+1 this.parent[rootY] = rootX; this.rank[rootX]++; } } // 判断两个元素是否在同一集合 isConnected(x, y) { return this.find(x) === this.find(y); } }
▼Go复制代码package main type UnionFind struct { parent []int rank []int } // 初始化 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, } } // 查找操作(带路径压缩) func (uf *UnionFind) Find(x int) int { if uf.parent[x] != x { // 路径压缩:将x的父节点直接设为根节点 uf.parent[x] = uf.Find(uf.parent[x]) } return uf.parent[x] } // 合并操作(按秩合并) func (uf *UnionFind) Union(x, y int) { rootX := uf.Find(x) rootY := uf.Find(y) // 如果已经在同一集合中,不需要合并 if rootX == rootY { return } // 按秩合并:将秩较小的树连接到秩较大的树下 if uf.rank[rootX] < uf.rank[rootY] { uf.parent[rootX] = rootY } else if uf.rank[rootX] > uf.rank[rootY] { uf.parent[rootY] = rootX } else { // 秩相同时,随便选一个作为根,并将新根的秩+1 uf.parent[rootY] = rootX uf.rank[rootX]++ } } // 判断两个元素是否在同一集合 func (uf *UnionFind) IsConnected(x, y int) bool { return uf.Find(x) == uf.Find(y) }
▼C++复制代码#include <vector> class UnionFind { private: std::vector<int> parent; // 记录每个节点的父节点 std::vector<int> rank; // 记录每个根节点对应树的高度 public: // 初始化 UnionFind(int size) { parent.resize(size); rank.resize(size, 0); // 初始时,每个元素自成一个集合,父节点指向自己 for (int i = 0; i < size; i++) { parent[i] = i; } } // 查找操作(带路径压缩) int find(int x) { if (parent[x] != x) { // 路径压缩:将x的父节点直接设为根节点 parent[x] = find(parent[x]); } return parent[x]; } // 合并操作(按秩合并) void unite(int x, int y) { int rootX = find(x); int rootY = find(y); // 如果已经在同一集合中,不需要合并 if (rootX == rootY) { return; } // 按秩合并:将秩较小的树连接到秩较大的树下 if (rank[rootX] < rank[rootY]) { parent[rootX] = rootY; } else if (rank[rootX] > rank[rootY]) { parent[rootY] = rootX; } else { // 秩相同时,随便选一个作为根,并将新根的秩+1 parent[rootY] = rootX; rank[rootX]++; } } // 判断两个元素是否在同一集合 bool isConnected(int x, int y) { return find(x) == find(y); } };
在Kruskal算法中,并查集是核心数据结构。该算法按权重从小到大遍历边,使用并查集判断加入某条边是否会形成环,从而高效构建最小生成树。
并查集可高效解决动态连通性问题,比如判断网络中两个节点是否连通、社交网络中用户间的关系连接等。当关系变化时,只需执行简单的union操作,判断连通性时使用find操作即可。
在编译器设计、电路分析等领域,并查集可用于等价类识别与合并。当系统发现两个元素等价时执行union操作,需要判断等价关系时使用find操作,这种动态维护等价关系的能力正是并查集的优势所在。
当向无向图中添加边时,如果边的两个端点已在同一个集合中,则添加这条边会形成环。在很多图算法和网络设计问题中都可以使用这一特性。
测验答案
- 查找(Find)和合并(Union)操作
- 路径压缩是在执行查找操作时,将查找路径上的所有节点都直接连接到根节点的优化技术。这样可以减少树的高度,加速后续的查找操作。
- 4个集合。分析:集合1包含元素{1,2,5},集合2包含元素{3,4},集合3包含元素{6,7,8,9},元素10没有参与任何合并操作,单独构成集合4
- 同时使用路径压缩和按秩合并时,查找和合并操作的均摊时间复杂度都是O(α(n)),其中α(n)是阿克曼函数的反函数,实际使用中可以近似看作常数。如果只使用路径压缩而不按秩合并,均摊复杂度为O(log n)。
这些题目都是并查集的经典应用场景,可以帮助大家加深对并查集的理解和掌握。