用于快速集团查找的数据结构

Question

找到一个集团并获得该集团的所有成员的好算法是什么？例如，我有：

a-b-c-d
e-f-g
h-i
x-y-x

其中每条线代表一个集团，其中所有成员都相互认识。现在，给定一个节点(比如a)，我希望快速找到集团a-b-c-d并获得成员[a, b, c, d]的列表

我总是可以有一个节点字典来列出节点，并让每个成员指向其余成员的列表：

a -> [b, c, d]
b -> [a, c, d]
c -> [a, b, d]
...

但我会复制很多数据。

编辑:更新不频繁，应假定为静态更新。成员只属于一个集团

Answer 1

一种选择是使用混合的哈希表/链表。将每个团存储为所有团元素的循环双向链表。然后，让一个哈希表将每个元素映射到表示它的链接列表单元格。要列出包含某些元素的集团的所有元素，请查找该元素的单元格，然后按照循环列表列出该集团的其余元素。

该数据结构还支持在O(1)时间内组合两个团(通过哈希表查找团的任意两个元素并将循环列表拼接在一起)，以及在O(1)时间内通过将元素拼接在循环列表中或从循环列表中删除元素。您可以在O(k)时间内列出集团成员，其中k是集团中元素的数量，整个过程使用O(n)空间。

希望这能有所帮助！