前言
（最近在学习Java，所有函数都是用Java语言来书写的）
- 前言部分是一些前提储备知识
在并查集（Union-Find）数据结构中，rank（中文称为“秩”）是用来表示树的高度或深度的一种辅助信息。它的主要作用是优化合并操作，以保持并查集的结构尽可能扁平，从而提高查询效率。
秩的具体定义
-
秩（Rank）：
- 秩用来衡量一个节点在树中的相对高度。具体来说，秩通常指的是树的“深度”或“高度”。初始时，每一个节点的秩可以设定为 0。若秩突然增加，说明该节点的子树的深度在增加。
-
合并时使用：
- 在进行
union操作时，- 若两个集合的根节点的秩不同，我们将根节点秩更小的树连接到秩更大的树上。
- 当两个根节点的秩相同时，将任意一棵树连接到另一棵树上，并将新根节点的秩值加一。这可以避免树过高。
- 在进行
合并示例
- 初始状态：
- 每个元素最初是自己父节点（根节点），并且秩都是 0。
Element: 1 2 3 4
Parent: [1, 2, 3, 4] // 表示每个元素都是自己的父节点
Rank: [0, 0, 0, 0] // 秩初始化为 0
- 调用
union(1, 2)：- 首先找出元素 1 和 2 的根节点。由于它们各自是自己的根节点，所以
find(1)返回 1，find(2)返回 2。 - 由于根节点不同（1 不是 2），可以将它们合并。
- 因为它们的秩相等，都为 0，所以可以任意选择一个作为新的根节点，此处选择把 2 的父节点设为 1，并将 1 的秩增加 1。
- 首先找出元素 1 和 2 的根节点。由于它们各自是自己的根节点，所以
Union(1, 2):
Element: 1 2
Parent: [1, 1] // 2 的父节点指向 1（1成为新的根）
Rank: [1, 0] // 将 1 的秩增加 1
- 状态更新后的图示：
1
/
2
- 接着进行
union(2, 3)：- 查找根节点:
find(2)返回 1（2 的父节点是 1），find(3)返回 3。 - 1 和 3 是不同的根节点，可以合并。
- 由于 1 的秩（1）大于 3 的秩（0），所以将 3 的父节点指向 1。
- 查找根节点:
Union(2, 3):
Element: 1 2 3
Parent: [1, 1, 1] // 3 的父节点指向 1
Rank: [1, 0, 0] // 秩不变
- 最后进行
union(1, 3)：- 查找根节点:
find(1)返回 1，find(3)返回 1，所以它们已经在同一个集合中，什么也不做。
- 查找根节点:
总结
在进行 union 操作时，我们首先需要找到两个元素的根节点。如果它们的根节点不同，就可以将它们合并。如果相同，则表示它们已经在同一个集合中。
以上是对 union 操作的正确描述和过程演示，谢谢你的耐心！如果你还有其他问题，请随时问我。
并查集简介
并查集（Union-Find）是一种用于处理不重叠集合的数据结构。它特别适合用于解决有关集合连接、合并和查询的问题。并查集通常包括两个主要操作：
- Find: 查找元素所属的集合。
- Union: 合并两个集合。
并查集的主要思想
- 快速查找：利用树形结构可以快速找到集合的根代表。
- 树的优化：
- 路径压缩：在查找过程中，将访问的每个节点直接连接到根节点，从而优化树的结构，使得树变平，查找效率更高。
- 按秩合并：在合并过程中，总是将秩（rank）低的树连接到秩高的树，防止树变得过于高。
路径压缩
路径压缩是在 find 操作中进行的优化。当我们执行查找时，我们将经过的所有节点直接连接到根节点。这减少了树的高度，从而提高随后的查找效率。
路径压缩示例代码
public int find(int[] parent, int index) {
if (parent[index] != index) {
// 递归地找到根节点，并在回溯阶段将当前节点直接连接到根节点
parent[index] = find(parent, parent[index]);
}
return parent[index];
}
路径压缩示例说明
假设我们有初始集合 [1, 2, 3, 4, 5]，其树结构如下：
1
|
2 - 3 - 4
|
5
- 假设
parent = [0, 1, 1, 2, 3, 3]，这意味着 2 和 3 的父节点是 1，5 的父节点是 3。 - 调用
find(parent, 5)时，路径为[5 -> 3 -> 1]。 - 路径压缩将改变
5的父节点直接连接到1，结果是parent = [0, 1, 1, 1, 3, 1]。 - 树在调用 find 后，将如下一步变得更平展：
1
|
2 - 3 - 4 - 5
按秩合并
按秩合并是在 union 操作中进行的优化，目的是尽可能保持树的扁平。所谓“秩”，在这里可以理解为树的高度。
按秩合并示例代码
public void union(int[] parent, int[] rank, int index1, int index2) {
int root1 = find(parent, index1);
int root2 = find(parent, index2);
if (root1 != root2) {
if (rank[root1] > rank[root2]) {
parent[root2] = root1; // root2合并到root1上
} else if (rank[root1] < rank[root2]) {
parent[root1] = root2; // root1合并到root2上
} else {
parent[root2] = root1; // 随意合并并增加其中一个的rank
rank[root1]++;
}
}
}
按秩合并示例说明
假设我们有两个树：
- 第一棵树的根为 A，秩为 2。
- 第二棵树的根为 B，秩为 3。
调用 union(parent, rank, A, B) 时：
- 由于 B 的秩大于 A，A 被合并到 B 上，这样就避免了增加树的高度。
- 在 rank 相同的情况下，任选一个作为新根，并增加该树的 rank。
结合路径压缩和按秩合并
结合这两个优化策略，在大多数实际应用中，find 和 union 操作可以接近于常数时间复杂度。这种效率使得并查集在处理大量集合合并和查找操作时极为高效。使用上面的两个优化版本的代码，能够保证树的高度不会过于增长，从而优化操作效率。
并查集的应用
并查集被广泛应用于很多算法与实际问题中，比如：
并查集（Union-Find）数据结构在计算机科学中有着广泛的应用，特别是在处理图相关的问题时。下面我将介绍几个具体的实例问题，并展示如何使用并查集来解决这些问题。
1. 网络连接
问题：判断网络中两个节点是否连通。
实例：假设我们有一个网络系统，每一对节点之间有或没有直接连接。如果两个节点是连通的，则它们之间存在一条直接或间接路径。
代码：
public class Network {
private int[] parent;
private int[] rank;
public Network(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) {
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) {
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
public boolean isConnected(int x, int y) {
return find(x) == find(y);
}
public static void main(String[] args) {
Network network = new Network(5);
network.union(0, 1);
network.union(1, 2);
System.out.println(network.isConnected(0, 2)); // 输出 true
System.out.println(network.isConnected(0, 3)); // 输出 false
}
}
2. 图的连通分量
问题：找出图中的连接组件，即连通分量。
实例：给定一个无向图，找出所有的连通分量。
代码：
import java.util.*;
public class Graph {
private int[] parent;
private int[] rank;
public Graph(int size) {
parent = new int[size];
rank = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = i; // 初始化，每个节点的父节点指向自己
rank[i] = 0; // 秩初始化为0
}
}
// 查找并进行路径压缩
public int find(int x) {
if (parent[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) {
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
// 计算连通分量的数量
public int countComponents() {
Set<Integer> uniqueRoots = new HashSet<>();
for (int i = 0; i < parent.length; i++) {
uniqueRoots.add(find(i));
}
return uniqueRoots.size();
}
// 主函数用于测试
public static void main(String[] args) {
Graph graph = new Graph(5);
graph.union(0, 1);
graph.union(1, 2);
graph.union(3, 4);
System.out.println(graph.countComponents()); // 输出 2，表明有两个连通分量
}
}
3. 最小生成树算法中的环检测
问题：在 Kruskal 算法中，检测添加的边是否会形成环。
实例：找到一个连通无向图的最小生成树。
代码：
import java.util.*;
class Edge implements Comparable<Edge> {
int src, dest, weight;
Edge(int src, int dest, int weight) {
this.src = src;
this.dest = dest;
this.weight = weight;
}
@Override
public int compareTo(Edge compareEdge) {
return this.weight - compareEdge.weight;
}
}
public class KruskalMST {
private List<Edge> edges;
private int vertices;
public KruskalMST(int vertices) {
this.vertices = vertices;
edges = new ArrayList<>();
}
public void addEdge(int src, int dest, int weight) {
edges.add(new Edge(src, dest, weight));
}
public List<Edge> findMST() {
Collections.sort(edges);
int[] parent = new int[vertices];
int[] rank = new int[vertices];
// Initialize parent and rank arrays
for (int i = 0; i < vertices; i++) {
parent[i] = i;
rank[i] = 0;
}
List<Edge> mst = new ArrayList<>();
// Traverse through all edges
for (Edge edge : edges) {
int rootSrc = find(parent, edge.src);
int rootDest = find(parent, edge.dest);
// Check if the selected edge forms a cycle
if (rootSrc != rootDest) {
mst.add(edge);
union(parent, rank, rootSrc, rootDest);
}
}
return mst;
}
private int find(int[] parent, int x) {
if (parent[x] != x) {
parent[x] = find(parent, parent[x]);
}
return parent[x];
}
private void union(int[] parent, int[] rank, int x, int y) {
int rootX = find(parent, x);
int rootY = find(parent, y);
if (rootX != rootY) {
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
// 主函数用于测试
public static void main(String[] args) {
KruskalMST graph = new KruskalMST(4);
graph.addEdge(0, 1, 10);
graph.addEdge(1, 3, 15);
graph.addEdge(0, 2, 6);
graph.addEdge(2, 3, 4);
List<Edge> mst = graph.findMST();
for (Edge edge : mst) {
System.out.println(edge.src + " - " + edge.dest + ": " + edge.weight);
}
// 输出：
// 2 - 3: 4
// 0 - 2: 6
// 0 - 1: 10
// 最小生成树的构建避免了环的形成。
}
}
4. 动态连通性问题
问题：处理动态连通性查询和合并操作。
实例：在一种动态环境中运行，始终保持对连通性的跟踪。
代码：
public class DynamicConnectivity {
private int[] parent;
private int[] rank;
public DynamicConnectivity(int size) {
parent = new int[size];
rank = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = i; // 初始化每个节点的父节点为自己
rank[i] = 0; // 初始化秩为0
}
}
// 查找并进行路径压缩
public int find(int x) {
if (parent[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) {
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
// 检查两个节点是否在同一连通分量内
public boolean isConnected(int x, int y) {
return find(x) == find(y);
}
// 主函数用于测试
public static void main(String[] args) {
DynamicConnectivity dc = new DynamicConnectivity(5);
dc.union(0, 1);
dc.union(1, 2);
System.out.println(dc.isConnected(0, 2)); // 输出 true
System.out.println(dc.isConnected(0, 3)); // 输出 false
dc.union(2, 3);
System.out.println(dc.isConnected(0, 3)); // 输出 true
}
}
这些实例展示了如何应用并查集解决一些常见的动态连通性问题，以及如何通过高效的合并和查找来提高性能。
5.思考应用
有些问题像动态连通性、社交网络中的朋友圈判断等都可以使用并查集来高效解决。特别是在需要动态地合并集合并频繁地查询彼此是否连通时，并查集是理想的选择。例如：
- 社交网络：确定任何两个人是否属于同一个社交圈。
- 电网连通性：判断两座城市是否通过电网连接。
通过这些例子，可以看到并查集以其高效的合并和查询能力，从简单集合操作到复杂图结构都有十分广泛的应用。
标签：parent,--,查集,rank,节点,int,算法,rootX,find From： https://blog.csdn.net/wxdzuishaui/article/details/143272692