快速派系查询的数据结构

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）空间。

希望这会有所帮助！