我尝试在 C++ 中编写一个组件标签代码，该代码使用具有 4 连接性的两遍算法。您可能想查看https://en.wikipedia.org/wiki/Connected-component_labeling。在该算法中有一个名为 union-find 的数据结构。我无法获得它的结构，也无法对其进行编码，因为我无法理解算法是如何使用该结构的。您是否知道如何在该算法中使用联合查找，或者至少在 C++ 环境中是否有任何本机库，或者您是否知道任何可以理解该结构的来源。也许动画可能有用。
问问题
1155 次
2 回答
1
Union-Find 的数据结构也称为“不相交集”。实际上，您可以在其 Wikipedia 页面 ( http://en.wikipedia.org/wiki/Disjoint-set_data_structure )上找到更多关于 disjoint-set 的描述和信息。在“算法简介”一书第 21 章中可以找到对不相交集数据结构调用的更详细介绍（如维基百科页面的参考 1 中所示。）
通常当我们谈论不相交集数据结构时，我们谈论的是一种称为“不相交集森林”的特定实现。这个具体实现的好处在于：1）它真的很容易实现 2）具有完美的时间复杂度（几乎恒定）。
您还可以在 Wikipedia 页面或我提到的书的第 21 章中找到一些关于如何实现不相交集森林的伪代码。
于 2012-07-22T02:42:46.100 回答
0
请参阅：http ://berkeley.intel-research.net/arahimi/connected/和http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=5F7A5FE1F4DCBA968A0B0E99B0593F71?doi=10.1.1.2.5996&rep=rep1&type=pdf
于 2012-07-22T01:14:04.600 回答