c++ - Hashmap 实现邻接列表

Question

我已经使用向量向量方法实现了一个邻接列表，向量向量的第 n 个元素指的是节点 n 的朋友列表。

我想知道哈希映射数据结构是否会更有用。我仍然犹豫不决，因为我根本无法识别它们之间的区别，例如，如果我想检查并在第 n 个元素邻居中执行操作（搜索、删除），它怎么能比向量的向量方法更有效。

score 3 · Accepted Answer

vector<vector<ID>>如果节点集是固定的，A是一个很好的方法。但是，如果您突然决定删除一个节点，您会很生气。您不能缩小向量，因为它会替换节点之后存储的元素，并且您会丢失引用。另一方面，如果您在旁边保留一个免费（可重用）ID 列表，则可以“取消”该插槽，然后再重用。非常有效率。

Aunordered_map<ID, vector<ID>>允许您更轻松地删除节点。您可以继续为新创建的节点分配新的 ID，这样您就不会丢失空槽。它没有那么紧凑，尤其是在碰撞时，但也没有那么糟糕。当需要使用较旧的编译器移动向量时，重新散列可能会减慢一些速度。

最后，aunordered_multimap<ID, ID>可能是最容易管理的一种。它也会将记忆分散到风中，但是嘿:)

就我个人而言，我会开始使用 a 进行原型设计，unordered_multimap<ID, ID>并且只有当它证明对我的需求来说太慢时才会切换到另一种表示。

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

score 0 · Accepted Answer

向量的向量

当您不需要删除边缘时，向量的向量是一个很好的解决方案。

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

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