javascript - 为什么不直接使用 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

您所描述的是一个 adjacency matrix ，不是 adjacency list .

你是对的，使用这种结构插入和删除边会更快。关于内存大小，矩阵行可能为图中的每个节点存储一个索引 bool 值，或者使用包含链接节点的 Set 表示(就像你所做的那样)，这在很大程度上取决于稀疏程度该图是哪个更好。 Set 方法类似于邻接表，但通常需要一些开销以实现高效搜索和更新。

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