用於實現鄰接列表的Hashmap

Question

我使用向量向量實現鄰接列表向量的第n個元素的方法引用節點n的好友列表。

我想知道如果哈希映射數據結構將更爲有用。我仍然猶豫不決，因爲我根本找不到它們之間的區別，例如，如果我想在第n個元素鄰居（搜索，刪除）中檢查和執行操作，它如何比矢量向量方法更有效。載體

Answer 1

甲vector<vector<ID>>是一個很好的方法，如果節點集合是固定的。但是如果你突然決定刪除一個節點，你會很煩。無法縮小矢量，因爲它會取代存儲在節點後面的元素，並且會丟失引用。另一方面，如果您保留了一面可用（可重複使用）的ID列表，則可以將插槽「廢除」，然後再使用。非常有效。

一個unordered_map<ID, vector<ID>>可以讓你更輕鬆地刪除節點。您可以繼續爲新創建的節點分配新ID，並且不會丟失空插槽。它不是很緊湊，特別是在碰撞時，但也不是很糟糕。當需要使用較早的編譯器移動向量時，重新調整可能會有一些緩慢的變化。

最後，unordered_multimap<ID, ID>大概是最容易管理的。它也分散內存的風，但嘿:)

就個人而言，我會開始原型與unordered_multimap<ID, ID>和切換到另一種表示，只有當它證明我的需求太慢。

注意：如果建立的鄰接關係是對稱的，則可以減少節點數量的一半，而關係(x, y)僅存儲爲min(x, y)。載體

Answer 2

矢量載體

矢量是當你不需要刪除邊緣很好的解決方案。

您可以在O增加邊緣（1），你可以在O（N）迭代的鄰居。 您可以通過vector[node].erase(edge)刪除邊緣，但它會很慢，複雜度只有O（頂點數）。

哈希映射

我不知道如何使用哈希映射。如果插入邊緣意味着設置hash_map[edge] = 1，那麼請注意您無法迭代節點的鄰居。