当前位置：首页 > news >正文

并查集(未压缩未按秩合并)

news 2025/7/17 0:14:28

并查集（Union-Find）是一种用于处理不相交集合（disjoint-set）的数据结构，主要用于处理连通性问题。并查集支持两种操作：

查找（Find）：确定元素所属的集合。
合并（Union）：将两个集合合并为一个集合。

并查集通常应用于图的连通性问题，例如判断图中两点是否连通、计算连通分量等。

动画描述

将(1,2),(2,3),(2,4)union后的图例，可以观察到不带压缩的情况下树的高度在持续增长。

问题描述

下面是一个不带路径压缩的并查集（Union-Find）。这个版本仅使用基本的查找和合并操作：

代码实现

public class SimpleUnionFind {private int[] parent;// 初始化并查集public SimpleUnionFind(int size) {parent = new int[size];for (int i = 0; i < size; i++) {parent[i] = i;}}// 查找操作，不带路径压缩public int find(int p) {while (p != parent[p]) {p = parent[p];}return p;}// 合并操作，不带按秩合并public void union(int p, int q) {int rootP = find(p);int rootQ = find(q);if (rootP != rootQ) {parent[rootP] = rootQ;}}// 判断两个节点是否连通public boolean connected(int p, int q) {return find(p) == find(q);}public static void main(String[] args) {int size = 10; // 假设有10个元素SimpleUnionFind uf = new SimpleUnionFind(size);uf.union(1, 2);uf.union(2, 3);uf.union(4, 5);uf.union(6, 7);uf.union(5, 6);System.out.println("1 和 3 是否连通: " + uf.connected(1, 3)); // trueSystem.out.println("1 和 4 是否连通: " + uf.connected(1, 4)); // falseSystem.out.println("4 和 7 是否连通: " + uf.connected(4, 7)); // trueuf.union(1, 4);System.out.println("1 和 4 是否连通: " + uf.connected(1, 4)); // true}
}

解释

初始化:
- parent数组用于存储每个元素的父节点，初始时每个元素的父节点是它自己。
查找操作（find）:
- 查找元素所属的集合，通过不断访问父节点来找到根节点。因为没有路径压缩，树的高度可能会很高，查找的时间复杂度是O(n)（n是元素个数）。
合并操作（union）:
- 合并两个集合，将一个集合的根节点指向另一个集合的根节点。因为没有按秩合并，树的高度可能会很高，合并的时间复杂度也是O(n)。
连通性检查（connected）:
- 判断两个元素是否属于同一个集合，即查找它们的根节点是否相同。