适合集合（图）分区的数据结构
我需要存储图形分区的数据分组节点，例如：
[node1,node2] [node3] [node4,node5,node6]
我的第一个想法是只有一个简单的向量或整数数组，其中的位置数组表示node_id，它的值是某种group_id
问题是许多分区算法依赖于对组内的节点对进行操作。使用这种方法，我认为我会浪费大量的计算来搜索向量来找出哪些节点属于同一组。
我还可以存储为一组 stl 集合，这似乎更接近分区的数学定义，但我得到的印象是不建议或不必要的嵌套集合，并且我需要修改我不确定的内部集合是可能的。
有什么建议吗？
I need to store data grouping nodes of a graph partition, something like:
[node1, node2] [node3] [node4, node5, node6]
My first idea was to have just a simple vector or array of ints, where the position in the array denoted the node_id and it's value is some kind of group_id
The problem is many partition algorithms rely on operating on pairs of nodes within a group. With this method, I think I would waste a lot of computation searching through the vector to find out which nodes belong to the same group.
I could also store as a stl set of sets, which seems closer to the mathematical definition of a partition, but I am getting the impression nested sets are not advised or unnecessary, and I would need to modify the inner sets which I am not sure is possible.
Any suggestions?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
根据您想要对集合执行的操作，您可以尝试不相交集合数据结构。在此结构中，每个元素都有一个方法
find，该方法返回其所属集合的“代表”。C++ 实现可在 Boost 中找到。
Depending on what exactly you want to do with the sets, you could try a disjoint set data structure. In this structure, each element has a method
findthat returns the "representative" of the set it belongs to.A C++ implementation is available in Boost.
我想到了两种很好的数据结构。
第一个数据结构（之前已经提到过）是不相交集森林，它提供了“合并这两个集合”和“x 位于哪个集合？”的极其有效的实现。但是，它不支持将组彼此分开的操作。
我推荐的另一个结构是链接/剪切树。这种结构允许您构建可以连接在一起形成树的图的分区。与不相交的集合森林不同，描述分区的树可以被切割成更小的树，从而允许您将分区分成更小的组。该结构比 union/find 结构效率稍低，但它仍然支持摊销 O(lg n) 中的所有操作。
There are two good data structures that come to mind.
The first data structure (and one that's been mentioned here before) is the disjoint-set forest, which gives extraordinarily efficient implementations of "merge these two sets" and "what set is x in?". However, it does not support the operation of splitting groups apart from one another.
The other structure I'd recommend is a link/cut tree. This structure lets you build up partitions of a graph that can be joined together into trees. Unlike the disjoint set forest, the tree describing the partition can be cut into smaller trees, allowing you to break partitions into smaller groups. This structure is a bit less efficient than the union/find structure, but it still supports all operations in amortized O(lg n).