邻接图-如何从图形中删除边线

Question

我在这个问题上待了好几个小时，因为找不到能在O（1）时间内从邻接图图中删除边缘的方法。

如果有人有任何想法，那将非常有帮助。

Answer 1

您应该拥有带有键的某种节点索引和值的HashMap（或python中的dict），例如，节点索引的HashSet（或python中的set），从给定Key节点的边缘到达。例如，{[1, [2, 3]], [2, [1, 3]], [3, [1]] }意味着您有3个节点：1, 2, 3和例如：[1, 2], [1, 3], [2, 1], [2, 3], [3, 1]-假定它是有向图。如果要删除边缘，比如说2，3，请在O（1）时间内从哈希图中获取键（边缘的起始节点）：像graph.get(2)这样的东西会返回您的值-在这种情况下，会导致[1, 3]。从这个集合中，您可以在O（1）时间中再次删除3（结束节点）。

对您可能拥有的所有边缘重复此过程。