¿Por qué decir que la búsqueda de amplitud se ejecuta en el tiempo

A menudo se dice (por ejemplo, en Wikipedia ) que el tiempo de ejecución de la búsqueda de amplitud primero (BFS) en un gráfico $G=(V,E)$ es $O(|V|+|E|)$ . Sin embargo, cualquier gráfico conectado tiene $|V|\leq |E|+1$ e, incluso en un gráfico no conectado, BFS nunca mirará un vértice fuera del componente que contiene el vértice de inicio. Ese componente contiene como máximo $|E|$ bordes, por lo que contiene como máximo $|E|+1$ vértices, y esos son los únicos que visitará el algoritmo.

Esto significa que $|V|+|E|\leq 2|E|+1$ , entonces ¿por qué no decimos que el tiempo de ejecución es solo $O(|E|)$ ?

_{Esto surgió en los comentarios sobre una pregunta sobre el tiempo de ejecución del algoritmo de Disjkstra .}

BFS generalmente se describe de manera similar a lo siguiente (de Wikipedia ).

 1  procedure BFS(G,start_v):
 2      let Q be a queue
 3      label start_v as discovered
 4      Q.enqueue(start_v)
 5      while Q is not empty
 6          v = Q.dequeue()
 7          if v is the goal:
 8              return v
 9          for all edges from v to w in G.adjacentEdges(v) do
10             if w is not labeled as discovered:
11                 label w as discovered
12                 w.parent = v
13                 Q.enqueue(w)

El problema es algo sutil: ¡se esconde en la línea 3! La pregunta es, ¿qué estructura de datos vamos a utilizar para almacenar qué vértices se han descubierto?

false$\Theta(|V|)$$|V|$$|E|$$O(|V|+|E|)$

$\Theta(|V|)$$O(|V|\,|E|)$$O(|E|^2)$$|V|^4$$|V|\,|E|\leq |V|^3$

$O(\log|V|)$$O(|E|\log|V|)$

$c$$|E|+1$$c + 2c + 4c + \dots + 2|E|\leq 4|E|$ $O(1)$$O(|E|)$

$O(|E|)$$4|E|$$O(|E|)$$O(|V|+|E|)$