在邻接列表表示的图中删除节点而不影响索引的策略

Question

我对邻接表的理解有些困难，想听听你的意见，甚至更好的建议。：-）

0 -> 1, 2, 5
1 -> 2, 3
2 -> 1
3 -> 4
4 -> 5

adjacencies = [[1,2,5],[2,3],[1],[4],[5]]

这是5号的单子。列表中的每个索引映射到邻接符号中的一个索引。

adjacencies = [[1,2,5],[2,3],[1],[4],[5]]
#              <--0--> <-1-> <2> <3> <4>
# The angle brackets indicate which position maps to which node.

如果我们想要访问节点1的所有输出边，我们只需通过邻接[1]在允许的时间内实现这一点。

假设我想删除一个节点，例如2。

adjacencies = [[1,5],[3],[4],[5]] # Node 2 was removed from the adjacency list
#              <-0-> <1> <3> <4>

这就是我烦恼的地方。节点3现在位于位置2，这意味着通过邻接[3]访问它是错误的！每次要访问节点时，我是否必须迭代邻接列表，或者我是否误解了一些显而易见的东西？（我用Java实现了一个基于邻接列表的图结构，我很想选择map > 类型的结构，但我想了解如何在使用普通数组的同时保持索引一致性……)

谢谢你的建议！

Answer 1

节点的“索引”或“位置”与图本身无关。它只与您选择如何存储图有关。每个节点上的数字只是一个标签，它可以是任何东西。

数字0到5是否意味着存储位置取决于您的实现。“邻接列表”是一种概念性的图存储方式，而不是一种实现。如果使用数组实现邻接列表，并使用标签作为数组的索引，则会遇到这样的问题：删除元素变得困难，以及强制节点标签成为特定的数字。