邻接列表中的大O-移除顶点和边缘(在图上执行各种操作的时间复杂度成本)

Question

我必须准备解释在邻接列表中删除顶点（O(|V| + |E|)）和边（O(|E|)）的时间复杂性。

当从具有V顶点和E边的图中移除顶点时，我们需要遍历所有边（O(|E|)），当然，以检查哪些边需要与顶点一起移除，但为什么我们需要检查所有顶点？

我不明白为什么为了去除边缘，我们需要穿过所有的边缘。我想我可能从一开始就理解不好，所以你能帮我解决上面两个问题吗？

Answer 1

要删除顶点，首先需要在数据结构中找到该顶点。此查找操作的时间复杂性取决于您使用的数据结构；如果您使用HashMap，它将是O(1)；如果使用List，它将是O(V)。

一旦确定了需要删除的顶点，现在就需要删除该顶点的所有边。由于使用的是邻接列表，因此只需迭代上一步中找到的顶点的边列表，并更新所有这些节点。此步骤的运行时间为O(Deg(V))。假设一个简单的图，maximum degree of a node is O(V)。对于稀疏图，它会低得多。

因此，removeVertex的运行时间将仅为O(V)。

Answer 2

考虑这样一个图：

A -> A
A -> B
A -> C
A -> D
B -> C

相邻列表将如下所示。

A: A -> B -> C -> D -> NULL
B: C -> NULL
C: NULL
D: NULL

让我们移除顶点C，我们必须遍历所有边，看看是否需要移除该边，即O（|E|）否则-如何找到A->C需要移除。然后，我们需要从顶级容器中删除列表C:NULL。根据顶级容器的不同，您可能需要或不需要O（|V|）时间。例如，如果顶层容器是一个数组，并且不允许有孔，则需要复制该数组。或者顶层是一个列表，您需要扫描列表以找到代表C的节点来删除。

从原始图中，让我们移除边A->D，我们必须遍历整个链表A->B->C->D才能找到节点D并将其移除。这就是为什么你需要遍历所有顶点。在更糟糕的情况下，一个顶点连接到所有其他顶点，因此它需要遍历所有顶点才能删除该元素或O（|V|）。同样，根据您的顶级容器，您可能无法快速找到列表，这将花费您另一个O（|V|），但在任何情况下，我都无法想象在邻接列表表示中删除O（|E|）的边。