我正在做面试准备和审查图表实现。我经常看到的是邻接表和邻接矩阵。当我们考虑基本操作的运行时，为什么我从来没有看到使用散列的数据结构？
例如，在 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
但是您可以轻松地增强任一设计以获得更快的插入/删除/搜索等属性。代价往往只是存储额外的数据！考虑实现一个相对简单的图算法（如... Euler's），看看您的图实现如何对运行时复杂度产生巨大影响。
为了让我的观点更清楚一点，我是说“邻接列表”实际上并不要求您使用LinkedList. 例如，wiki 在他们的页面上引用了这个：
Guido van Rossum 建议的实现使用哈希表将图中的每个顶点与相邻顶点数组相关联。在这种表示中，顶点可以由任何可散列对象表示。没有将边明确表示为对象。
我们可能通常看不到这种表示，因为很少需要检查图中是否存在任意边（我想不出任何依赖于它的日常图算法），并且在需要它的地方，我们可以只使用一个整个图的哈希图，存储对(v1, v2)来表示边。这似乎更有效率。
（大多数常见的图算法都说“对于顶点 v 的每个邻居，做......”，然后邻接表是完美的。）
许多理论问题涉及一组固定的顶点和边——没有删除。
许多/大多数图算法涉及简单地遍历邻接列表中的所有边或更复杂的东西（需要额外的数据结构）。
鉴于上述情况，您将获得数组的所有优点（例如 O(1) 随机访问、节省空间）来表示没有任何缺点的顶点（例如固定大小、O(n) 搜索/索引插入/删除），以及链表的所有优点（例如 O(1) 插入，对于未知数量的元素的空间效率）来表示没有任何缺点的边缘（O(n) 搜索/随机访问）。
但是......哈希呢？
当然，散列对于所需操作具有相当的效率，但常数因素更差并且存在不可预测性，因为性能取决于良好的散列函数和分布良好的数据。
现在，你不应该使用散列，如果你的问题需要它，那就去吧。
为什么人们不使用
HashMap<Node, HashSet<Node>>？
除非在同一组节点上有多个图，否则HashMap可以用 的成员变量替换Node。
HashSet对比的问题LinkedList更有趣。我猜想，对于稀疏图，LinkedList在时间（对于等效渐近复杂度的操作）和空间上都会更有效。我对这两种表示方式都没有太多经验，因为根据算法要求，我通常更喜欢（i）将邻接列表存储为连续的子数组，或者（ii）为每条边提供一个明确的对象或存储信息的对象对关于边（例如，权重）并参与两个循环双向链表（我自己的实现，因为Java和C++标准库不支持侵入式数据结构），使得节点删除与节点和边删除的程度成正比 O (1)。
您为哈希引用的运行时间并不是最坏的情况，只是针对不知情的对手的高概率，尽管它们可以以进一步降低常数因素为代价进行摊销。