为什么BFS / DFS的时间复杂度不只是O（E）而不是O（E + V）？

Question

[我知道堆栈溢出中有一个类似的问题，有人问过为什么BFS / DFS的时间复杂度不只是O（V）。

给出的适当答案是，在完整图的情况下，E可以大到V ^ 2，因此在时间复杂度中包括E是有效的。

但是，如果V不能大于E + 1。因此，在这种情况下，时间复杂度不为V，应该工作吗？

Answer 1

如果给定E = kV + c，那么对于某些实常数k和c，O(E + V) = O(kV + c + V) = O(V) = O(E)，您的论点是正确的。

一个例子是树。

但是，一般来说，E = O(V^2)，因此我们做不到O(V^2)。

为什么不总是只写O（E）？请注意，在某些情况下，图表中根本没有边缘（即O(E) ~ O(1)）。即使在这种情况下，我们也必须转到每个顶点（O(V)），我们无法在O(1)时间内完成。

因此，通常只写O(E)不会。

Answer 2

V必须包含在内，因为BFS和DFS都依赖于大小为| V |的数组。跟踪已处理/发现/探索了哪些顶点（无论情况如何）。如果图形具有0条边和100000个顶点，则与只有5个顶点的情况相比，此类数组将花费更多的时间进行初始化。因此，BFS和DFS的时间复杂度在| V |上缩放。