7.10. Análisis de la búsqueda en anchura¶

Antes de continuar con otros algoritmos de grafos vamos a analizar el desempeño de tiempo de ejecución del algoritmo de búsqueda en anchura. Lo primero que debemos observar es que el ciclo while se ejecuta, como máximo, una vez para cada vértice del grafo $| V |$ . Usted puede verificar que esto es cierto porque un vértice debe ser blanco antes de que pueda ser examinado y agregado a la cola. Esto nos da $O (V)$ para el ciclo while. El ciclo for, que está anidado dentro del while, se ejecuta como máximo una vez para cada arista del grafo, $| E |$ . La razón es que cada vértice sale de la cola a lo sumo una vez y que examinamos una arista del nodo $u$ al nodo $v$ únicamente cuando el nodo $u$ sale de la cola. Esto nos da $O (E)$ para el ciclo for. Combinando los dos ciclos nos da $O (V + E)$ .

Por supuesto, hacer la búsqueda en anchura es sólo una parte de la tarea. Seguir los enlaces desde el nodo inicial hasta el nodo objetivo es la otra parte de la tarea. El peor caso para esto sería que el grafo fuera una única cadena larga. En ese caso, recorrer todos los vértices sería $O (V)$ . El caso normal será alguna fracción de $| V |$ pero en todo caso escribiríamos $O (V)$ .

Finalmente, al menos para este problema, también está el tiempo requerido para construir el grafo inicial. Dejamos el análisis de la función construirGrafo como ejercicio para usted.