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

Question

在我的算法类中,我被告知用于图表表示的邻接列表的缺点是迭代通过对应于每个节点的相邻节点阵列的O(n)查找时间.我通过使用HashMap实现我的邻接列表,HashMap将节点映射到它们相邻节点的HashSet,这不是只需要O(1)查找时间吗？有什么我想念的吗？

Answer 1

如您所知,使用HashMap中的键查找值为O(1).但是,在邻接列表中,HashMap的值也是其相邻节点的列表.邻接列表的主要目的是迭代相邻节点.例如:图形遍历算法,如DFS和BFS.在你的情况下HashSet.假设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的键)中相邻元素的数量较少.因此,查找元素不会花费更多.