> 文章列表 > Disjoint 集合数据结构或 Union-Find 算法简介

Disjoint 集合数据结构或 Union-Find 算法简介

Disjoint 集合数据结构或 Union-Find 算法简介

联合查找算法是一种对此类数据结构执行两个有用操作的算法:

  • 查找:确定特定元素在哪个子集中。这可用于确定两个元素是否在同一子集中。
  • 联合:将两个子集连接成一个子集。这里首先我们必须检查这两个子集是否属于同一个集合。如果否,则我们无法执行联合。 

不相交集的 UNION 和 FIND 操作

一组元素 a1、a2、…an 上的关系可以分为等价类。元素 a 的等价类是 S 的子集,它包含 S 中与 a 相关的所有元素。

通过这两个操作将一组元素划分为等价的类