为什么不直接使用 object(map) 来表示邻接列表边缘？如果我们使用数组，我们需要做额外的线性查找操作，不是吗？

Question

我从文章中如何看待它，他们建议实现这样的邻接列表：

const adjacencyList = new Map()
// add vertex
adjacencyList.set(nodeLabel, [])
// add edge
adjacencyList.get(nodeLabel).push(edgeDestinationNodeLabel)
// remove edge
adjacencyList.get(nodeLabel).forEach(destLabel => /*... if match, remove */)

看到这个我想知道，你会如何，比如说，从这样的列表中删除边缘？我可以看到的唯一选项 - 遍历数组adjacencyList.get(nodeLabel)并删除匹配项。

我没有找到的是我想到的实现示例：

const adjacencyList = new Map()
// add vertex
adjacencyList.set(nodeLabel, Map())
// add edge
adjacencyList.get(nodeLabel).set(edgeDestinationNodeLabel, true)
// remove edge
adjacencyList.get(nodeLabel).delete(edgeDestinationNodeLabel)

在内存使用量相同的情况下，这不是更快吗，因为我们避免了线性find操作？

此外，第二个选项感觉更具可扩展性，因为我们可以存储任何引用，而不是true。

Answer 1

您描述的是邻接矩阵，而不是邻接列表。

您是对的，使用此结构插入和删除边缘会更快。关于内存大小，矩阵行可以为图形中的每个节点存储索引布尔值，或者使用包含链接节点的Set表示形式(就像您所做的那样)，这在很大程度上取决于图形的稀疏程度哪个更好。Set方法类似于邻接列表，但通常有一些开销，以便有效地进行搜索和更新。

邻接列表的主要优点是其简单性。它在稀疏图中仍然表现良好，其中节点仅链接到其他几个节点，无论是在内存大小还是速度上。在许多图形算法中，图形不会经常更新，迭代特定节点的邻居的查询更为常见 - 邻接列表很少支持。