21

在 CLRS 消费税 22.1-8 中（我是自学，不在任何大学）

假设每个数组条目 Adj[u] 不是一个链表，而是一个哈希表，其中包含 (u,v) ∈ E 的顶点 v。如果所有边查找的可能性相同，那么确定一个边缘在图中？这个方案有什么缺点？为解决这些问题的每个边缘列表建议一个替代数据结构。与哈希表相比，您的替代方案有缺点吗？

所以，如果我用哈希表替换每个链表，就会出现以下问题：

  1. 确定一条边是否在图中的预期时间是多少？
  2. 有什么缺点？
  3. 为解决这些问题的每个边缘列表建议一个替代数据结构
  4. 与哈希表相比，您的替代方案有缺点吗？

我有以下部分答案：

  1. 我认为预期的时间是O(1)，因为我只是去Hashtable t = Adj[u]，然后return t.get(v);
  2. 我认为缺点是Hashtable会比链表占用更多的空间。

对于其他两个问题，我无法获得线索。

任何人都可以给我一个线索？

4

3 回答 3

14

问题 3 的答案可能是二叉搜索树。

在邻接矩阵中，每个顶点后跟一个 V 元素数组。这种 O(V) 空间成本导致快速（O(1) 时间）搜索边缘。

在邻接表中，每个顶点后跟一个列表，该列表仅包含 n 个相邻顶点。这种节省空间的方式导致搜索速度慢（O（n））。

哈希表是数组和列表之间的折衷。它使用的空间比 V 少，但在搜索中需要处理冲突。

二叉搜索树是另一种折衷方案——空间成本与列表一样最小，搜索的平均时间成本为 O(lg n)。

于 2012-12-16T06:41:34.923 回答
11

它取决于哈希表以及它如何处理冲突，例如假设在我们的哈希表中，每个条目都指向具有相同键的元素列表。

如果元素的分布足够均匀，则查找的平均成本仅取决于每个列表的平均元素数（负载因子）。所以每个列表的平均元素数是 n/m，其中 m 是我们哈希表的大小。

  1. 确定一条边是否在图中的预期时间是 O(n/m)
  2. 比链表更多的空间和比邻接矩阵更多的查询时间。如果我们的哈希表支持动态调整大小，那么我们将需要额外的时间在旧哈希表和新哈希表之间移动元素，如果不是，我们将需要 O(n) 空间为每个哈希表提供 O(1) 查询时间导致 O(n^2) 空间。我们也刚刚检查了预期的查询时间，在最坏的情况下，我们可能有像链表一样的查询时间(O(degree(u))) 所以最好使用邻接矩阵来获得确定性的 O(1) 查询时间和 O(n^2) 空间。
  3. 阅读以上部分
  4. 是的，例如，如果我们知道图的每个顶点最多有 d 个相邻顶点且 d 小于 n，那么使用哈希表将需要 O(nd) 空间而不是 O(n^2) 并且会期望 O( 1）查询时间。
于 2012-03-17T16:26:33.283 回答
1

问题 3 和 4 非常开放。除了其他两位的想法之外，哈希表的一个问题是它不是一种从头到尾扫描元素的有效数据结构。在现实世界中，有时枚举给定顶点的所有邻居（例如，BFS、DFS）是很常见的，这在某种程度上损害了直接哈希表的使用。

一种可能的解决方案是将哈希表中的现有存储桶链接在一起，以便它们形成一个双向链表。每次添加新元素时，将其连接到列表末尾；每当删除一个元素时，将其从列表中删除并相应地修复链接关系。当您想要进行全面扫描时，只需浏览此列表即可。

当然，这种策略的缺点是空间更大。每个元素有两个指针开销。此外，添加/删除元素需要更多时间来建立/修复链接关系。

我不太担心碰撞。顶点的哈希表存储它的邻居，每个邻居都是唯一的。如果它的密钥是唯一的，就没有碰撞的机会。

于 2015-07-25T03:58:53.260 回答