CLRS excise 22.1-8（我是自学，没有在任何大学学习）
假设每个数组条目 Adj[u] 不是链表，而是一个
包含顶点 v 的哈希表，其中 (u,v) ∈ E。如果所有
边缘查找的可能性相同，预计的时间是多少
判断图中是否有边？有什么缺点
这个方案有吗？为每条边建议替代数据结构
解决这些问题的列表。您的替代方案有吗
与哈希表相比有什么缺点？
因此，如果我用哈希表替换每个链表，则会出现以下问题：
- 确定图中是否有边的预期时间是多少？
- 有什么缺点？
- 为每个边缘列表建议一个替代数据结构来解决这些问题
- 与哈希表相比，您的替代方案是否有缺点？
我有以下部分答案：
- 我认为预期时间是 O(1)，因为我只是去 Hashtable t = Adj[u]，然后 return t.get(v);
- 我认为缺点是哈希表会比链表占用更多的空间。
对于另外两个问题，我没有任何线索。
任何人都可以给我线索吗？
问题 3 的答案可能是二叉搜索树。
在邻接矩阵中，每个顶点后面都有一个 V 元素数组。这种 O(V) 空间成本导致快速（O(1) 时间）边缘搜索。
在邻接列表中，每个顶点后面都有一个列表，该列表仅包含 n 个相邻顶点。这种节省空间的方式会导致搜索速度缓慢 (O(n))。
哈希表是数组和列表之间的折衷方案。它使用的空间比 V 少，但需要处理搜索中的冲突。
二叉搜索树是另一种折衷方案——空间成本与列表一样最小，并且搜索的平均时间成本为 O(lg n)。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
