graph - 如果用hash表替换adjacency-list中的每个链表,有什么缺点？

Question

在CLRS消费税22.1-8(我自学,不在任何大学)

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

因此,如果我用哈希表替换每个链表,则存在以下问题:

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

我有以下部分答案:

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

对于其他两个问题,我无法得到线索.

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

Answer 1

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

在邻接矩阵中,每个顶点后跟一个V元素数组.该O(V)空间成本导致边缘的快速(O(1) - 时间)搜索.

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

哈希表是数组和列表之间的折衷.它使用的空间比V小,但在搜索时需要碰撞处理.

二叉搜索树是另一种折衷方案 - 空间成本与列表的成本相比最小,搜索的平均时间成本为O(lg n).

Answer 2

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

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

1. 确定边是否在图中的预期时间是O(n/m)
2. 比链接列表更多的空间和比邻接矩阵更多的查询时间.如果我们的哈希表支持动态调整大小那么我们就需要额外的时间来对新老哈希表空间之间,如果没有,我们需要O(n)的移动元素的每个哈希表,以便有O(1)查询时间,这导致O(n ^ 2)空间.我们也刚刚检查预计查询时间,在最坏的情况下,我们可能有查询的时候,就像链表(O(度(U))),所以它看起来更好地使用邻接矩阵,以具有确定性的O(1)查询时间和O(n ^ 2)空间.
3. 阅读以上部分
4. 是的,例如,如果我们知道,我们图的每个顶点至多有d相邻顶点和d小于n,则使用哈希表需要O(ND)的空间,而不是为O(n ^ 2)本来期望O( 1)查询时间.