用于实现邻接列表的Hashmap

Question

我使用向量向量实现邻接列表向量的第n个元素的方法引用节点n的好友列表。

我想知道如果哈希映射数据结构将更为有用。我仍然犹豫不决，因为我根本找不到它们之间的区别，例如，如果我想在第n个元素邻居（搜索，删除）中检查和执行操作，它如何比矢量向量方法更有效。载体

Answer 1

甲vector<vector<ID>>是一个很好的方法，如果节点集合是固定的。但是如果你突然决定删除一个节点，你会很烦。无法缩小矢量，因为它会取代存储在节点后面的元素，并且会丢失引用。另一方面，如果您保留了一面可用（可重复使用）的ID列表，则可以将插槽“废除”，然后再使用。非常有效。

一个unordered_map<ID, vector<ID>>可以让你更轻松地删除节点。您可以继续为新创建的节点分配新ID，并且不会丢失空插槽。它不是很紧凑，特别是在碰撞时，但也不是很糟糕。当需要使用较早的编译器移动向量时，重新调整可能会有一些缓慢的变化。

最后，unordered_multimap<ID, ID>大概是最容易管理的。它也分散内存的风，但嘿:)

就个人而言，我会开始原型与unordered_multimap<ID, ID>和切换到另一种表示，只有当它证明我的需求太慢。

注意：如果建立的邻接关系是对称的，则可以减少节点数量的一半，而关系(x, y)仅存储为min(x, y)。载体

Answer 2

矢量载体

矢量是当你不需要删除边缘很好的解决方案。

您可以在O增加边缘（1），你可以在O（N）迭代的邻居。 您可以通过vector[node].erase(edge)删除边缘，但它会很慢，复杂度只有O（顶点数）。

哈希映射

我不知道如何使用哈希映射。如果插入边缘意味着设置hash_map[edge] = 1，那么请注意您无法迭代节点的邻居。