Depth-First-Search 的 Big-O 如何 = O(V+E)？

Question

我试图理解 how/why DFS 的复杂度是 O(V+E)。 这是我尝试分析伪-代码迭代 DFS.

DFS(G, t)
{

1   stack S = new empty Stack of size G.|V|  ... O(1)
2   S.push(t)                                ... O(1)

3   while(S is not Empty)                    ... O(|V|), this will always be =<|V|
    {
4       u = S.pop()                          ... O(1)

5       if(u.visited = false)                ... O(1)
        {
6            u.visited = true                ... O(1)

7            for-each edge (u,v) in G.E      ... O(|E|), this will always be =<|E|
8                if(v.visited = false)       ... O(1)
9                    S.push(v)               ... O(1)
        }
    }
}

现在结合每行的复杂度我们有：

O(1) + O(1) + O(|V|)[O(1) + O(1) + O(1) + O(E)[O(1) + O(1 )]] = O(2) + O(V) + O(V) + O(V) + O(V) + O(V * E) + O(V * E) = 4*O(V) + 2*O(V * E) = O(V * E)

我没有得到 O(V+E)？ 谁能从数学上告诉我我们是如何达到 O(V+E) 的？

任何人都可以提供见解吗？

Answer 1

让我们简单点。

外循环，它只循环 S 一次，删除它看到的每个元素。因此 O(|V|) 在你的符号中。

内部循环，它只在你的边上循环一次，删除它看到的每个元素。因此 O(|E|) 在你的符号中。

然而，并不是 S 的每个元素都删除了每条边。您删除所有节点和所有边，因此 O(|V|+|E|).

然而，应该注意的是，以上内容仅出于本意。你的实现比较糟糕，它实际上是 O(|V|*|E|) 因为你没有从列表中删除边缘，你只将节点标记为已访问。最后的效果相同，但您仍然为每个节点遍历每个边。