La respuesta es, valen las dos. Porque todo depende de cómo estés analizando las cosas.
Las preguntas que deberías hacerte son, ¿qué estoy recorriendo? ¿Qué tan grande es el árbol que forma el algoritmo? ¿Sé que tan grande es? ¿Para el algoritmo en algún momento?
Para recorrer todo el grafo debo atravesar todos los nodos pasando por todos los ejes (en el peor caso tenemos n2
ejes, con n
la cantidad de nodos).
Ahora bien, BFS forma un árbol, asumiendo que la cantidad de ejes por nodos es x
y x
es máximo, para ir de un nivel a otro del árbol recorro x-1
ejes por cada nodo del nivel.
Pues si estoy el nodo v
y llegué a él mediante el eje (u,v)
no voy a recorrer nuevamente ese eje (lo voy a ignorar). Es decir, que al llegar a las hojas del árbol se habrán recorrido xn
ejes, donde n
es la distancia de las hojas a la raíz.
Veamos que esto se cumple en un grafo finito y completo (el de n2
ejes).
De la raíz al siguiente nivel el algoritmo recorrerá n
ejes.
Luego en el siguiente nivel, que tiene n
nodos, el recorrerá n-1
ejes por nodo del nivel, es decir recorrerá (n-1)*n
ejes.
Es decir, en total n+(n-1)*n
. Lo cuál da n2
.