快速派系查詢的數據結構

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

希望這會有所幫助！