经典算法思想--并查集

前言

		（最近在学习Java，所有函数都是用Java语言来书写的）

• 前言部分是一些前提储备知识

在并查集（Union-Find）数据结构中，rank（中文称为“秩”）是用来表示树的高度或深度的一种辅助信息。它的主要作用是优化合并操作，以保持并查集的结构尽可能扁平，从而提高查询效率。

秩的具体定义

1. 秩（Rank）：

   • 秩用来衡量一个节点在树中的相对高度。具体来说，秩通常指的是树的“深度”或“高度”。初始时，每一个节点的秩可以设定为 0。若秩突然增加，说明该节点的子树的深度在增加。

2. 合并时使用：

   • 在进行 union 操作时，
     • 若两个集合的根节点的秩不同，我们将根节点秩更小的树连接到秩更大的树上。
     • 当两个根节点的秩相同时，将任意一棵树连接到另一棵树上，并将新根节点的秩值加一。这可以避免树过高。

合并示例

1. 初始状态：
   • 每个元素最初是自己父节点（根节点），并且秩都是 0。

Element:   1   2   3   4
Parent:   [1,  2,  3,  4]  // 表示每个元素都是自己的父节点
Rank:     [0,  0,  0,  0]  // 秩初始化为 0

2. 调用 union(1, 2)：
   • 首先找出元素 1 和 2 的根节点。由于它们各自是自己的根节点，所以 find(1) 返回 1，find(2) 返回 2。
   • 由于根节点不同（1 不是 2），可以将它们合并。
   • 因为它们的秩相等，都为 0，所以可以任意选择一个作为新的根节点，此处选择把 2 的父节点设为 1，并将 1 的秩增加 1。

Union(1, 2):
Element:   1   2
Parent:   [1,  1]   // 2 的父节点指向 1（1成为新的根）
Rank:     [1,  0]   // 将 1 的秩增加 1

3. 状态更新后的图示：

    1/2

4. 接着进行 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]  // 秩不变

5. 最后进行 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; // 随意合并并增加其中一个的rankrank[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)); // 输出 trueSystem.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;}@Overridepublic 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.思考应用

有些问题像动态连通性、社交网络中的朋友圈判断等都可以使用并查集来高效解决。特别是在需要动态地合并集合并频繁地查询彼此是否连通时，并查集是理想的选择。例如：

• 社交网络：确定任何两个人是否属于同一个社交圈。
• 电网连通性：判断两座城市是否通过电网连接。

通过这些例子，可以看到并查集以其高效的合并和查询能力，从简单集合操作到复杂图结构都有十分广泛的应用。