c++ - 如何在连通分量标注中使用不相交集？

Question

我在连接组件标签中使用不相交集时遇到了一些困难。我看过很多例子，也看过这个问题，博天提供了一个非常好的不相交集实现作为 C++ 链表。我已经在我的程序中实现了连接组件标签（标签是简单的整数），但是我很难解决具有不相交集的标签之间的等价性。

任何人都可以帮助我 - 也许使用 Bo Tian 的实现？我认为这也将帮助其他人达到这一点。

编辑

我的算法遍历图像，当它找到两个标签时，两个连接的像素具有不同的标签，它必须在“等价注册表”（这将是不相交集森林）中做一个注释。在循环整个图像之后，我必须通过（对图像进行第二次遍历）查看注册表，然后将这些像素标记为集合中的最小等效标签来解决等价问题。

score 4 · Accepted Answer

不相交集森林提供两种操作：

不相交集森林主要用于将一组对象划分为一组不同的集群，其中每个集群都不相交（也就是说，每个对象最多属于一个组）。然后，不相交集森林允许您有效地判断每个组中的对象，或者（大约在 O(n) 时间内）确定每个对象的集群 ID。

要使用不相交的集合林，首先将每个对象放入其自己的集群中。从那时起，每次你想标记两个不同的对象在同一个集群中时，你都会使用联合操作将它们链接在一起。最后，您将在每个点上调用find以确定它属于哪个集群，并从那里读取所有内容属于哪个组。

希望这可以帮助！

score 1 · Accepted Answer

在 DJS 上查看本教程。唯一的修改是，在联合期间，您必须将较大的连接到较小的，因此根始终是集合的最小值。

score 1 · Accepted Answer

你是对的，标记连接的集合只是完成了一半的工作。使用等价找到不相交的集合也是同样困难的部分。我面临着确切的情况。

查找不相交集（标记后）的一种方法是使用Union-Find算法。看看下面的文章。您将从头开始了解如何实现标记和查找不相交集。还给出了示例输入和输出矩阵的说明。

score 1 · Accepted Answer

有一篇关于使用不相交集标记连接组件的博客：

4 回答 4