algorithm - 动态连接和union-find有什么关系？

Question

根据维基百科：

动态连接结构是一种数据结构，它动态维护有关图的连接组件的信息。

和：

union-find数据结构是一种跟踪一组元素的数据结构，这些元素被划分为多个不相交（非重叠）的子集。

乍一看，这些数据结构之间几乎没有什么关系。但几乎每一篇提到动态连接的文章，都会瞥见 union-find。所以，我想知道这两者有什么关系？

标签： algorithmdata-structuresunion-find

Answer 1

来自维基百科关于动态连接的文章：

图的顶点集合 V 是固定的，但边的集合 E 可以改变。这三种情况，按照难易程度依次是：

• 边只添加到图中（这可以称为增量连接）；
• 边只从图中删除（这可以称为递减连通性）；
• 可以添加或删除边（这可以称为完全动态连接）。

在第一种情况下可以使用联合查找数据结构（也称为不相交集数据结构）。在添加边时可以使用并集运算来连接两个组件，使用查找操作来测试两个顶点是否在同一个组件中。但是，union-find 数据结构没有支持删除边的操作，将一个组件拆分为两个新断开的组件；所以它不能用来解决动态连通性问题的其他两种情况。