使用HashSet的O(1)邻接表查找时间? [英] Adjacency list with O(1) look up time using HashSet?

问题描述

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

In my algorithms class I've been told that a draw back of Adjacency Lists for graph representation is the O(n) look up time for iterating through the array of adjacent nodes corresponding to each node. I implement my adjacency list by using a HashMap that maps nodes to a HashSet of their adjacent nodes, wouldn't that only take O(1) look up time? Is there something I'm missing?

推荐答案

如您所知，在HashMap中使用键查找值是O(1).但是，在邻接列表中，HashMap的值也是其相邻节点的列表.邻接表的主要目的是迭代相邻节点.例如:图遍历算法，例如DFS和BFS.您的情况是HashSet.假设HashSet中的元素数为n.然后，即使在HashSet中也要迭代所有元素，所以O(n).

As you know look up for value using key in HashMap is O(1). However, in adjacency list the value of the HashMap is also a list of its adjacent nodes. The main purpose of the adjacency list is to iterate the adjacent nodes. For example: graph traversal algorithms like DFS and BFS. In your case HashSet. Suppose number of elements in HashSet is n. Then for iterating all the elements even in HashSet is 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的键)中相邻元素的数量更少.因此，查找元素不会花费更多.

Generally, Adjacency List is preferable for sparse graph because it is the graph with only a few edges. It means the number of adjacent elements in each node(key of HashMap) is less. So the look up for a element wont cost more.

这篇关于使用HashSet的O(1)邻接表查找时间?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！