graph - first - ¿Por qué la complejidad del tiempo para BFS/DFS no es simplemente O(E) en lugar de O(E+V)?

dfs pseudocode

Question

Sé que hay una pregunta similar en el desbordamiento de pila, donde una persona ha preguntado por qué la complejidad del tiempo de BFS / DFS no es simplemente O (V).

La respuesta adecuada dada fue que E puede ser tan grande como V ^ 2 en el caso de un gráfico completo, y por lo tanto, es válido incluir E en la complejidad del tiempo.

Pero, si V no puede ser mayor que E + 1. Entonces, en ese caso no tener V en la complejidad del tiempo, debería funcionar?

Answer 1

Si se da que E = kV + c , para algunas constantes reales k y c , entonces,
O(E + V) = O(kV + c + V) = O(V) = O(E) y su argumento es correcto.

Un ejemplo de esto son los árboles.

En general, sin embargo, E = O(V^2) , y por lo tanto no podemos hacer mejor que O(V^2) .

¿Por qué no escribir solo O (E) siempre?
Tenga en cuenta que puede haber casos en los que no haya bordes en el gráfico (es decir, O(E) ~ O(1) ). Incluso para tales casos, tendremos que ir a cada uno de los vértices ( O(V) ), no podemos terminar en O(1) vez.

Por lo tanto, solo escribir O(E) no funcionará en general.