在不损害索引的情况下删除由邻接表表示的图中的节点的策略
Strategy for deleting a node in a graph represented by an adjacency list without hurting indexing
我在理解邻接表时遇到了一些困难，想听听您的意见或更好的建议。 :-)
tl;dr：从邻接列表中删除节点会中断 "indices"。这是可以避免的吗？如果可以，如何避免？
长篇部分：在图论中，我们了解到邻接表是（在特定条件下）存储有向图的有效方式。让我们看一个用邻接表表示法编写的图的示例。
0 -> 1, 2, 5
1 -> 2, 3
2 -> 1
3 -> 4
4 -> 5
为了简单起见，假设我们在边或节点上没有其他属性（潜力、成本等）。为了实现这一点，我们会在我们选择的编程语言中遇到一些数组或列表类型的问题。我选择 python 作为演示。
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 的所有传出边，我们可以通过 adjacencies[1] 在恒定时间内简单地做到这一点。
假设我想删除一个节点，例如2.
adjacencies = [[1,5],[3],[4],[5]] # Node 2 was removed from the adjacency list
# <-0-> <1> <3> <4>
自然地我们失去了入边 (0,2), (1,2) 并且我们也失去了出边 (2,1)。
这就是困扰我的问题。 节点 3 现在位于位置 2，这意味着通过 adjacencies[3] 访问它是错误的！每次我想访问一个节点时，我是否必须迭代 adjacencies 列表，或者我是否误解了一些显而易见的事情？ （我在 Java 中实现了一个基于邻接表的图结构，我很想选择 Map<Integer,List<Edge>> 一种结构，但我想了解如何在使用普通数组时保持索引一致性。 ..)
感谢任何建议！
节点的"index"或"position"与图本身无关。它仅与您选择存储图形的方式有关。你在每个节点上的数字只是一个标签，可以是任何东西。
数字 0 到 5 是否表示存储位置取决于您的实现。 "Adjacency list" 是一种存储图形的概念方式，而不是一种实现方式。
如果您使用数组实现邻接列表，并使用您的标签作为数组的索引，您 运行 会遇到这个问题，因为它变得难以删除元素，并且迫使您的节点标签成为特定数字。
我在理解邻接表时遇到了一些困难，想听听您的意见或更好的建议。 :-)
tl;dr：从邻接列表中删除节点会中断 "indices"。这是可以避免的吗？如果可以，如何避免？
长篇部分：在图论中，我们了解到邻接表是（在特定条件下）存储有向图的有效方式。让我们看一个用邻接表表示法编写的图的示例。
0 -> 1, 2, 5
1 -> 2, 3
2 -> 1
3 -> 4
4 -> 5
为了简单起见，假设我们在边或节点上没有其他属性（潜力、成本等）。为了实现这一点，我们会在我们选择的编程语言中遇到一些数组或列表类型的问题。我选择 python 作为演示。
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 的所有传出边，我们可以通过 adjacencies[1] 在恒定时间内简单地做到这一点。
假设我想删除一个节点，例如2.
adjacencies = [[1,5],[3],[4],[5]] # Node 2 was removed from the adjacency list
# <-0-> <1> <3> <4>
自然地我们失去了入边 (0,2), (1,2) 并且我们也失去了出边 (2,1)。
这就是困扰我的问题。 节点 3 现在位于位置 2，这意味着通过 adjacencies[3] 访问它是错误的！每次我想访问一个节点时，我是否必须迭代 adjacencies 列表，或者我是否误解了一些显而易见的事情？ （我在 Java 中实现了一个基于邻接表的图结构，我很想选择 Map<Integer,List<Edge>> 一种结构，但我想了解如何在使用普通数组时保持索引一致性。 ..)
感谢任何建议！
节点的"index"或"position"与图本身无关。它仅与您选择存储图形的方式有关。你在每个节点上的数字只是一个标签，可以是任何东西。
数字 0 到 5 是否表示存储位置取决于您的实现。 "Adjacency list" 是一种存储图形的概念方式，而不是一种实现方式。 如果您使用数组实现邻接列表，并使用您的标签作为数组的索引，您 运行 会遇到这个问题，因为它变得难以删除元素，并且迫使您的节点标签成为特定数字。