Adjency List 中的大 O - 去除顶点和去除边（对图执行各种操作的时间复杂度成本）

Question

我必须准备在 Adjency List中去除顶点 ( O(|V| + |E|)) 和边 ( O(|E|))的时间复杂度的解释。

当从图中删除带有 V 个顶点和 E 个边的顶点时，我们需要遍历所有边 ( O(|E|))，当然，要检查是否需要与顶点一起删除哪些顶点，但为什么我们需要检查所有顶点？

我不明白为什么为了去除边缘，我们需要遍历所有边缘。我想我可能从一开始就不太理解，所以你能帮助上面那两个吗？

Answer 1

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

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

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