深度优先搜索的 Big-O = O(V+E) 怎么样？

Question

我试图了解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|)因为你没有从列表中删除边，你只是将节点标记为已访问。最后的效果相同，但您仍然遍历每个节点的每条边。