我正在做面试准备和审查图表实现。我一直看到的大的是邻接表和邻接矩阵。当我们考虑基本操作的运行时时，为什么我从来没有看到使用哈希的数据结构？
例如，在 Java 中，邻接表通常是 ArrayList<LinkedList<Node>> , 但为什么人们不使用 HashMap<Node, HashSet<Node>> ？
设 n = 节点数，m = 边数。
在这两种实现中，删除节点 v 涉及搜索所有集合并删除 v。在邻接列表中，这是 O(n^2)，但在“邻接集”中，它是 O(n)。同样，删除边涉及从 v 的列表中删除节点 u 和从 u 的列表中删除节点 v。在邻接列表中，这是 O(n)，而在邻接集中，它是 O(1)。其他操作，例如查找节点后继，查找两个节点之间是否存在路径等，对于两种实现都是相同的。空间复杂度也是O(n + m)。
我能想到的邻接集的唯一缺点是添加节点/边的时间复杂度为 O(1)，而在邻接列表中这样做确实是 O(1)。
也许我没有看到什么或者我在计算运行时时忘记考虑一些事情，所以请告诉我。
最佳答案
与 DavidEisenstat 的回答一样，图形实现差异很大。这是在讲座中没有很好地体现出来的事情之一。有两种概念设计:
1) Adjacency list
2) Adjacency matrix
但是您可以轻松地增强任一设计以获得诸如更快的插入/移除/搜索等特性。代价通常只是存储额外的数据!考虑实现一个相对简单的图算法(例如...欧拉算法)，看看您的图实现如何对运行时复杂性产生巨大影响。
为了让我的观点更清楚一点，我是说“邻接列表”并不真的需要您使用 LinkedList。例如，wiki 在他们的 page 中引用了这个:
An implementation suggested by Guido van Rossum uses a hash table to associate each vertex in a graph with an array of adjacent vertices. In this representation, a vertex may be represented by any hashable object. There is no explicit representation of edges as objects.
关于algorithm - 图实现 : why not use hashing?，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/18325144/