图形实现:为什么不使用散列？

Question

我正在做面试准备和审查图表实现.我一直看到的最重要的是邻接列表和邻接矩阵.当我们考虑基本操作的运行时,为什么我从未看到使用散列的数据结构？

例如,在Java中,通常会使用邻接列表ArrayList<LinkedList<Node>>,但为什么人们不使用HashMap<Node, HashSet<Node>>？

设n =节点数,m =边数.

在这两种实现方式,去掉了节点U包括通过所有的收藏和取出诉搜索.在邻接表,这是为O(n ^ 2),但在"邻接集",这是为O(n).同样,删除边缘涉及从v列表中删除节点u,从u列表中删除节点v.在邻接列表中,那是O(n),而在邻接集中,它是O(1).其他操作,例如查找节点后继,查找两个节点之间是否存在路径等,对于这两种实现都是相同的.空间复杂度也都是O(n + m).

我能想到的邻接集的唯一缺点是添加节点/边是分摊O(1),而在邻接列表中这样做是真正的O(1).

也许我没有看到任何东西,或者我在计算运行时忘了考虑事情,所以请告诉我.

Answer 1

与DavidEisenstat的回答一样,图形实现也有很大不同.这是演讲中没有遇到的事情之一.有两种概念设计:

1) Adjacency list
2) Adjacency matrix

但是您可以轻松地增加任一设计以获得更快的插入/移除/搜索等属性.价格往往只是存储额外的数据!考虑实现一个相对简单的图形算法(如... Euler's),看看你的图形实现如何对运行时复杂性产生巨大影响.

为了使我的观点更清楚,我说的是"邻接列表"并不需要你使用LinkedList.例如,维基在他们的页面上引用了这个:

Guido van Rossum建议的实现使用哈希表将图中的每个顶点与相邻顶点的数组相关联.在该表示中,顶点可以由任何可清洗对象表示.边缘没有明确表示为对象.

Answer 2

为什么人们不使用HashMap<Node, HashSet<Node>>？

除非同一组节点上有多个图，否则HashMap可以用 的成员变量替换Node。

HashSet对比的问题LinkedList更有趣。我猜想，对于稀疏图，LinkedList在时间（对于等效渐近复杂性的操作）和空间上都会更有效。我对这两种表示形式都没有太多经验，因为根据算法要求，我通常更喜欢（i）将邻接列表存储为连续的子数组或（ii）为每个边有一个显式对象或一对存储信息的对象关于边（例如权重）并参与两个循环双向链表（我自己的实现，因为Java和C++标准库不支持侵入式数据结构），使得节点删除与节点和边删除的程度成正比O (1).

您引用的哈希值的运行时间并不是最坏的情况，只是针对不经意的对手的高概率，尽管它们可以以进一步降低常数因子为代价进行摊销。