您好，登录后才能下订单哦！
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
并查集（Disjoint Set Union，简称DSU）是一种用于处理不相交集合的数据结构。它主要支持两种操作：查找（Find）和合并（Union）。并查集在解决一些图论问题、连通性问题以及动态连通性问题时非常有用。本文将详细介绍并查集的基本概念、核心操作、优化方法，并通过Java代码实现并查集。
并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。它支持以下两种操作：
并查集的主要应用场景包括动态连通性问题、最小生成树算法（如Kruskal算法）等。
并查集的应用场景非常广泛，以下是一些常见的应用场景：
在并查集中，每个元素最初都是一个独立的集合。我们可以通过一个数组来表示每个元素的父节点，初始时每个元素的父节点都是它自己。
int[] parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
查找操作用于确定某个元素所属的集合。通常，我们通过递归查找元素的父节点，直到找到根节点（即父节点为自身的节点）。
int find(int x) {
if (parent[x] != x) {
return find(parent[x]);
}
return x;
}
合并操作用于将两个集合合并为一个集合。我们首先找到两个元素的根节点，然后将其中一个根节点的父节点指向另一个根节点。
void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
parent[rootX] = rootY;
}
}
路径压缩是一种优化查找操作的方法。在查找过程中，我们将查找路径上的所有节点直接连接到根节点，从而减少后续查找操作的时间复杂度。
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
按秩合并是一种优化合并操作的方法。我们通过记录每个集合的秩（即树的高度），在合并时将秩较小的树连接到秩较大的树上，从而避免树的高度过高。
int[] rank = new int[n];
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 class UnionFind {
private int[] parent;
public UnionFind(int n) {
parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
public int find(int x) {
if (parent[x] != x) {
return find(parent[x]);
}
return x;
}
public void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
parent[rootX] = rootY;
}
}
}
以下是一个优化后的并查集实现，包含路径压缩和按秩合并。
public class UnionFind {
private int[] parent;
private int[] rank;
public UnionFind(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 1;
}
}
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]++;
}
}
}
}
假设有n个人，每个人都有一个朋友列表。我们需要判断两个人是否在同一个朋友圈中。
public class FriendCircles {
public int findCircleNum(int[][] M) {
int n = M.length;
UnionFind uf = new UnionFind(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (M[i][j] == 1) {
uf.union(i, j);
}
}
}
int count = 0;
for (int i = 0; i < n; i++) {
if (uf.find(i) == i) {
count++;
}
}
return count;
}
}
在Kruskal算法中，我们需要判断两个节点是否在同一个集合中，以避免形成环。
public class KruskalMST {
public int minCostConnectPoints(int[][] points) {
int n = points.length;
List<int[]> edges = new ArrayList<>();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int dist = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);
edges.add(new int[]{i, j, dist});
}
}
edges.sort((a, b) -> a[2] - b[2]);
UnionFind uf = new UnionFind(n);
int cost = 0;
for (int[] edge : edges) {
int u = edge[0];
int v = edge[1];
int dist = edge[2];
if (uf.find(u) != uf.find(v)) {
uf.union(u, v);
cost += dist;
}
}
return cost;
}
}
并查集是一种非常高效的数据结构，适用于处理不相交集合的合并与查询问题。通过路径压缩和按秩合并等优化方法，可以进一步提高并查集的性能。本文详细介绍了并查集的基本概念、核心操作、优化方法，并通过Java代码实现了并查集及其应用实例。希望本文能帮助你更好地理解并查集及其在算法中的应用。
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。