并查集：原理、路径压缩与按秩合并

2023-07-11 02:32| 来源: 网络整理| 查看: 265

并查集的原理

路径压缩

按秩合并

并查集的应用

总结

并查集（Disjoint Set）是一种常用的数据结构，用于解决一类关于集合合并和查询的问题。它提供了高效的合并（Union）和查询（Find）操作，并且在实际应用中有广泛的应用。本文将介绍并查集的原理、路径压缩和按秩合并两种优化策略，并通过C++代码示例来演示其实现。

并查集的原理

并查集维护了一组不相交的集合，每个集合用一棵树来表示。每个树的节点表示一个元素，节点之间的关系表示两个元素的归属关系。树的根节点表示集合的代表元素，通过根节点的相等关系来判断两个元素是否属于同一个集合。

并查集主要支持两个操作：

Find：查找元素所属的集合，即找到元素所在树的根节点。Union：将两个元素所在的集合合并为一个集合，即将两个根节点连接在一起。

下面是一个简单的并查集的实现：

#include #include using namespace std; class UnionFind { public: UnionFind(int n) { parent.resize(n); rank.resize(n, 0); for (int i = 0; i < n; i++) { parent[i] = i; } } int find(int x) { if (parent[x] != x) { parent[x] = find(parent[x]); } return parent[x]; } void unite(int x, int y) { int rootX = find(x); int rootY = find(y); if (rootX != rootY) { if (rank[rootX] < rank[rootY]) { parent[rootX] = rootY; } else if (rank[rootX] > rank[rootY]) { parent[rootY] = rootX; } else { parent[rootY] = rootX; rank[rootX]++; } } } private: vector parent; vector rank; }; int main() { int n = 10; // 元素个数 UnionFind uf(n); // 进行一些合并操作 uf.unite(1, 2); uf.unite(3, 4); uf.unite(5, 6); uf.unite(7, 8); uf.unite(1, 9); uf.unite(3, 6); // 查找元素所属的集合 cout

【本文地址】

公司简介

联系我们