在不相交的集合数据结构中迭代 类
Iterating over classes in a disjoint set data structure
我已经为我的程序实现了一个不相交的集合数据结构，我意识到我需要遍历所有等价 classes。
在网上搜索时，我没有找到任何关于实现它的最佳方法或它如何影响复杂性的有用信息。我很惊讶，因为这似乎是经常需要的东西。
有标准的方法吗？我正在考虑使用链表（我使用 C，所以我计划在每个等价 class 的顶部元素中存储一些指针）并在每个联合操作中更新它。有没有更好的方法？
您可以在基于散列的集合或任何平衡二叉搜索树中存储指向顶部元素的指针。您只需要删除和添加元素 - 这两个操作分别在 O(1)* 和 O(logN) 中的这些结构 运行 中进行。在链表中它们 运行 在 O(N).
你的提议看起来很合理。如果你通过代表线程一个双向链表，你可以在时间 O(1) 内从代表列表中拼接出一个元素，然后每次需要列出代表时遍历列表。
@ardenit 提到您还可以使用外部哈希 table 或 BST 来存储代表。这当然更容易编写代码，但我怀疑它不会像通过项目线程链接列表那样快。
我已经为我的程序实现了一个不相交的集合数据结构，我意识到我需要遍历所有等价 classes。
在网上搜索时，我没有找到任何关于实现它的最佳方法或它如何影响复杂性的有用信息。我很惊讶，因为这似乎是经常需要的东西。
有标准的方法吗？我正在考虑使用链表（我使用 C，所以我计划在每个等价 class 的顶部元素中存储一些指针）并在每个联合操作中更新它。有没有更好的方法？
您可以在基于散列的集合或任何平衡二叉搜索树中存储指向顶部元素的指针。您只需要删除和添加元素 - 这两个操作分别在 O(1)* 和 O(logN) 中的这些结构 运行 中进行。在链表中它们 运行 在 O(N).
你的提议看起来很合理。如果你通过代表线程一个双向链表，你可以在时间 O(1) 内从代表列表中拼接出一个元素，然后每次需要列出代表时遍历列表。
@ardenit 提到您还可以使用外部哈希 table 或 BST 来存储代表。这当然更容易编写代码，但我怀疑它不会像通过项目线程链接列表那样快。