algorithm - 使用 HashSet 查找时间为 O(1) 的邻接表？

Question

在我的算法课上，有人告诉我，用于图形表示的邻接列表的缺点是 O(n) 查找时间，用于遍历与每个节点对应的相邻节点数组。我通过使用将节点映射到其相邻节点的 HashSet 的 HashMap 来实现我的邻接列表，这不是只需要 O(1) 的查找时间吗？有什么我想念的吗？

Answer 1

如您所知，在 HashMap 中使用键查找值的复杂度为 O(1)。但是，在邻接列表中，HashMap 的值也是其相邻节点的列表。邻接表的主要目的是迭代相邻节点。例如:DFS、BFS 等图遍历算法。在你的情况下哈希集。假设 HashSet 中的元素个数为 n。然后迭代所有元素，即使在 HashSet 中也是 O(n)。

So, total complexity would be O(1)+O(n).

    Where O(1)= look up in HashMap
          O(n)= iterate all the elements

一般来说，邻接表更适合稀疏图，因为它是只有几条边的图。这意味着每个节点(HashMap 的键)中相邻元素的数量较少。所以查找一个元素不会花费更多。