相关疑难解决方法(0)

在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会占用更多的空间然后链表.

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

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