c++ - 适合集合（图）分区的数据结构

Question

我需要存储图形分区的数据分组节点，例如：

[节点1，节点2] [节点3] [节点4，节点5，节点6]

我的第一个想法是只有一个简单的向量或整数数组，其中数组中的位置表示 node_id，它的值是某种 group_id

问题是许多分区算法依赖于对组内的节点对进行操作。使用这种方法，我想我会浪费大量的计算来搜索向量以找出哪些节点属于同一组。

我也可以存储为一组 stl 集，这似乎更接近分区的数学定义，但我得到的印象是不建议或不需要嵌套集，我需要修改我不确定的内部集是可能的。

有什么建议么？

Answer 1

根据您想要对集合做什么，您可以尝试不相交的集合数据结构。在此结构中，每个元素都有一个方法，该方法find返回其所属集合的“代表”。

Boost中提供了 C++ 实现。

Answer 2

我想到了两种好的数据结构。

第一个数据结构（也是之前在这里提到的）是不相交集森林，它提供了“合并这两个集合”和“x 在哪个集合中？”的非常有效的实现。但是，它不支持将组彼此分开的操作。

我推荐的另一种结构是链接/切割树。这种结构使您可以构建可以连接到树中的图形的分区。与不相交集森林不同，描述分区的树可以被切割成更小的树，允许您将分区分成更小的组。这种结构比联合/查找结构效率低一点，但它仍然支持摊销 O(lg n) 中的所有操作。