问答系统网站模板,网站界面类型,中国建设银行官网站保本理财,哪个电商平台好做前言 #xff08;最近在学习Java#xff0c;所有函数都是用Java语言来书写的#xff09;前言部分是一些前提储备知识
在并查集#xff08;Union-Find#xff09;数据结构中#xff0c;rank#xff08;中文称为“秩”#xff09;是用来表示树的高度或深度的一种辅助信息…前言 最近在学习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) 返回 1find(2) 返回 2。由于根节点不同1 不是 2可以将它们合并。因为它们的秩相等都为 0所以可以任意选择一个作为新的根节点此处选择把 2 的父节点设为 1并将 1 的秩增加 1。
Union(1, 2):
Element: 1 2
Parent: [1, 1] // 2 的父节点指向 11成为新的根
Rank: [1, 0] // 将 1 的秩增加 1状态更新后的图示 1/2接着进行 union(2, 3) 查找根节点: find(2) 返回 12 的父节点是 1find(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) 返回 1find(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 的父节点是 15 的父节点是 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 的秩大于 AA 被合并到 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() {SetInteger 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 ComparableEdge {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 ListEdge 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 ListEdge 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;}ListEdge 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);ListEdge 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.思考应用
有些问题像动态连通性、社交网络中的朋友圈判断等都可以使用并查集来高效解决。特别是在需要动态地合并集合并频繁地查询彼此是否连通时并查集是理想的选择。例如
社交网络确定任何两个人是否属于同一个社交圈。电网连通性判断两座城市是否通过电网连接。
通过这些例子可以看到并查集以其高效的合并和查询能力从简单集合操作到复杂图结构都有十分广泛的应用。
