c++ - 在 4-connectivity two-pass 算法中编码 union-find

Question

我尝试用 C++ 编写一个组件标签代码，该代码使用具有 4 个连通性的两次传递算法。你可能想看看 https://en.wikipedia.org/wiki/Connected-component_labeling .在该算法中有一个名为 union-find 的数据结构。我无法获得它的结构，也无法对其进行编码，因为我无法理解该算法如何使用该结构。您知道如何在该算法中使用 union-find 吗，或者至少在 C++ 环境中是否有任何 native 库，或者您是否知道任何来源来理解该结构。也许动画可能会有用。

Answer 1

Union-Find 的数据结构也称为“disjoint-set”。实际上，您可以在其维基百科页面 (http://en.wikipedia.org/wiki/Disjoint-set_data_structure) 上找到更多关于 disjoint-set 的描述和信息。在“Introduction to Algorithms”一书第 21 章中可以找到对不相交集数据结构的更详细介绍(也显示在维基百科页面的引用文献 1 中。)

通常当我们谈论不相交集数据结构时，我们谈论的是一种称为“不相交集森林”的具体实现。这种具体实现的优点在于:1) 实现起来非常简单 2) 具有完美的时间复杂度(几乎恒定)。

您还可以在维基百科页面或我提到的书的第 21 章中找到一些关于如何实现不相交集森林的伪代码。