在不相交集数据结构中迭代类别

Question

3

我为我的程序实现了一个不相交集数据结构，我意识到需要遍历所有等价类。

在搜索网络时，我没有找到任何有关最佳实现方法或其对复杂性的影响的有用信息。这让我感到惊讶，因为它似乎是经常需要的东西。

是否有标准的方法来完成这个任务？我考虑使用链表（我使用C，所以计划将一些指针存储在每个等价类的顶部元素中），并在每次联合操作时更新它。是否有更好的方法？

- martinkunev

你的目标是迭代等价类中的代表还是等价类的元素？ - templatetypedef

@templatetypedef 目前我只需要每个类中的一个代表。我认为在将来，我可能需要迭代类中的所有元素（给定代表）。 - martinkunev

1

如果你只需要在最后执行它，那么如果仅迭代所有集合并挑选出根不起作用，通常的做法是使用你的不相交集合结构来构建其他东西，比如从集合到列表的映射，这样你可以轻松地进行迭代。 - Matt Timmermans

2个回答

1

你的提议看起来非常合理。如果你在代表元素中穿过一个双向链接列表，你可以在O(1)时间内从代表元素列表中裂开一个元素，然后每次需要列出代表元素时遍历该列表。

@ardenit提到你也可以使用外部哈希表或二叉搜索树来存储代表元素。虽然这肯定更容易编写，但我怀疑它不会像仅穿过项目的链接列表那样快。

- templatetypedef

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ardenit · Accepted Answer

您可以将指向散列集或任何平衡二叉搜索树中顶部元素的指针存储起来。您只需要删除和添加元素 - 这些结构中的两个操作分别以 O(1)* 和 O(logN) 运行。在链表中，它们运行时间为 O(N)。