Lab 05 要求我们实现一个带路径压缩的并查集（Union-Find with Path Compression）的数据结构，带路径压缩的并查集是一种高效的数据结构，用于管理不相交集合的合并与查询操作。它通过路径压缩技术优化了查找操作的性能。
不过预传统意义上的并查集不同的是， CS61B 中进行判断的依据是并查集的整体大小而非常规意义上的深度(也就是我们所称的秩， Rank)
其主要成员包括：
- Parent数组：记录每个元素的父节点
- Rank数组：记录每个集合的秩（树的高度），用于按秩合并优化
- Size数组：记录每个集合的大小，此处用于合并
路径压缩
在查找根节点的过程中，我们可以将查找路径上的所有节点直接连接到根节点，从而扁平化树结构，减少后续查找操作的深度。
核心代码是
parent[x] = find(parent[x]) 应用场景
- 连通性判断
- 网络连接检测
- 社交网络好友关系
- 图算法
- Kruskal最小生成树算法
- 检测图中环的存在
- 图像处理
- 连通组件标记
- 动态连通性问题
- 实时判断两个元素是否连通
算法优势
- 高效性：路径压缩使得后续操作极其快速
- 简单性：实现代码简洁易懂
- 实用性：广泛应用于各种算法和系统中
注意事项
- 路径压缩会改变树的结构，但不影响连通性的正确性
- 按秩合并是可选的，但能进一步优化性能
- 在实际应用中，通常同时使用路径压缩和按秩合并
实现(Size 版本)
public class UnionFind {
// TODO: Instance variables
final int N;
int [] parent; // 父节点数组
int [] rank; // Rank
int [] size; // 大小
/* Creates a UnionFind data structure holding N items. Initially, all
items are in disjoint sets. */
public UnionFind(int N) {
// 初始化方法
this.N = N;
this.parent = new int[N];
this.rank = new int[N];
this.size = new int[N];
for (int i = 0; i < N; i++) {
parent[i] = i;
rank[i] = 0;
size[i] = 1;
}
}
/* Returns the size of the set V belongs to. */
public int sizeOf(int v) {
if (v > N || v < 0){
throw new IllegalArgumentException("Index out of bounds: " + v);
}
// 返回根节点的 Size
return size[find(v)];
}
/* Returns the parent of V. If V is the root of a tree, returns the
negative size of the tree for which V is the root. */
public int parent(int v) {
if (v > N || v < 0){
throw new IllegalArgumentException("Index out of bounds: " + v);
}
int root = find(v);
return root == v ? -size[root] : parent[v];
}
/* Returns true if nodes/vertices V1 and V2 are connected. */
public boolean connected(int v1, int v2) {
if (v1 > N || v2 > N || v1 < 0 || v2 < 0) {
throw new IllegalArgumentException("Index out of bounds: " + v1 + " or " + v2);
}
return find(v1) == find(v2);
}
/* Returns the root of the set V belongs to. Path-compression is employed
allowing for fast search-time. If invalid items are passed into this
function, throw an IllegalArgumentException. */
public int find(int v) {
if (v > N || v < 0){
throw new IllegalArgumentException("Index out of bounds: " + v);
}
if(this.parent[v] == v) return v;
return this.parent[v] = find(this.parent[v]); // 路径压缩
}
/* Connects two items V1 and V2 together by connecting their respective
sets. V1 and V2 can be any element, and a union-by-size heuristic is
used. If the sizes of the sets are equal, tie break by connecting V1's
root to V2's root. Union-ing an item with itself or items that are
already connected should not change the structure. */
public void union(int v1, int v2) {
if (v1 > N || v2 > N || v1 < 0 || v2 < 0) {
throw new IllegalArgumentException("Index out of bounds: " + v1 + " or " + v2);
}
int root1 = find(v1);
int root2 = find(v2);
if (root1 == root2) {
return;
}
if (size[root1] < size[root2]) {
parent[root1] = root2;
size[root2] += size[root1];
} else if (size[root1] > size[root2]) {
parent[root2] = root1;
size[root1] += size[root2];
} else {
parent[root1] = root2;
++rank[root2];
size[root2] += size[root1];
}
}
}
实现(Rank 版本)
public class UnionFind {
private final int N;
private final int[] parent;
private final int[] rank;
private final int[] size;
/* Creates a UnionFind data structure holding N items. Initially, all
items are in disjoint sets. */
public UnionFind(int N) {
this.N = N;
this.parent = new int[N];
this.rank = new int[N];
this.size = new int[N];
for (int i = 0; i < N; i++) {
parent[i] = i;
rank[i] = 0;
size[i] = 1;
}
}
/* Returns the size of the set V belongs to. */
public int sizeOf(int v) {
if (v < 0 || v >= N) {
throw new IllegalArgumentException("Index out of bounds: " + v);
}
return size[find(v)];
}
/* Returns the parent of V. If V is the root of a tree, returns the
negative size of the tree for which V is the root. */
public int parent(int v) {
if (v < 0 || v >= N) {
throw new IllegalArgumentException("Index out of bounds: " + v);
}
// 直接返回父节点，不进行路径压缩
return parent[v];
}
/* Returns true if nodes/vertices V1 and V2 are connected. */
public boolean connected(int v1, int v2) {
if (v1 < 0 || v1 >= N || v2 < 0 || v2 >= N) {
throw new IllegalArgumentException("Index out of bounds");
}
return find(v1) == find(v2);
}
/* Returns the root of the set V belongs to. Path-compression is employed
allowing for fast search-time. If invalid items are passed into this
function, throw an IllegalArgumentException. */
public int find(int v) {
if (v < 0 || v >= N) {
throw new IllegalArgumentException("Index out of bounds: " + v);
}
if (parent[v] != v) {
parent[v] = find(parent[v]); // 递归路径压缩
}
return parent[v];
}
/* 迭代版本的find方法，避免递归深度问题 */
public int findIterative(int v) {
if (v < 0 || v >= N) {
throw new IllegalArgumentException("Index out of bounds: " + v);
}
// 找到根节点
int root = v;
while (root != parent[root]) {
root = parent[root];
}
// 路径压缩
while (v != root) {
int next = parent[v];
parent[v] = root;
v = next;
}
return root;
}
/* Connects two items V1 and V2 together using union-by-rank heuristic. */
public void union(int v1, int v2) {
if (v1 < 0 || v1 >= N || v2 < 0 || v2 >= N) {
throw new IllegalArgumentException("Index out of bounds");
}
int root1 = find(v1);
int root2 = find(v2);
if (root1 == root2) {
return; // 已在同一集合中
}
// 按秩合并：将秩较小的树合并到秩较大的树下
if (rank[root1] < rank[root2]) {
parent[root1] = root2;
size[root2] += size[root1];
} else if (rank[root1] > rank[root2]) {
parent[root2] = root1;
size[root1] += size[root2];
} else {
// 秩相等时，任选一个作为根，并增加秩
parent[root1] = root2;
rank[root2]++;
size[root2] += size[root1];
}
}
/* 获取元素的秩（主要用于调试） */
public int getRank(int v) {
if (v < 0 || v >= N) {
throw new IllegalArgumentException("Index out of bounds: " + v);
}
return rank[find(v)];
}
/* 检查元素是否为根节点 */
public boolean isRoot(int v) {
if (v < 0 || v >= N) {
throw new IllegalArgumentException("Index out of bounds: " + v);
}
return parent[v] == v;
}
/* 获取集合数量 */
public int countSets() {
int count = 0;
for (int i = 0; i < N; i++) {
if (parent[i] == i) {
count++;
}
}
return count;
}
}
以上
发表回复