graph - 为什么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)不会。