Análisis de la búsqueda en anchura

¿Cuánto tarda una búsqueda en anchura para un grafo con un conjunto de vértices $V$‍ y un conjunto de aristas $E$‍? La respuesta es un tiempo $O(V+E)$‍.

Veamos qué significa un tiempo $O(V+E)$‍. Supón por el momento que $|E|\ge |V|$‍, que es el caso para la mayoría de los grafos, especialmente aquellos para los cuales ejecutamos una búsqueda en anchura. Entonces $|V|+|E|\le |E|+|E|=2\cdot |E|$‍. Como ignoramos factores constantes en la notación asintótica, vemos que cuando $|E|\ge |V|$‍, $O(V+E)$‍ en realidad significa $O(E)$‍. Sin embargo, si tenemos $|E|<|V|$‍, entonces $|V|+|E|\le |V|+|V|=2\cdot |V|$‍, y por lo tanto $O(V+E)$‍ en realidad significa $O(V)$‍. Podemos juntar ambos casos al decir que $O(V+E)$‍ en realidad significa $O(max(V,E))$‍. En general, si tenemos parámetros $x$‍ y $y$‍, entonces $O(x+y)$‍ en realidad significa $O(max(x,y))$‍.

(Ten en cuenta, por cierto, que un grafo está conectado si hay un camino desde cada vértice a todos los demás vértices. El número mínimo de aristas que un grafo puede tener y seguir estando conectado es $|V|-1$‍. Un grafo en el cual $|E|=|V|-1$‍ se llama un árbol libre).

¿Cómo es que una búsqueda en anchura se ejecuta en un tiempo $O(V+E)$‍? Se tarda un tiempo $O(V)$‍ en inicializar la distancia y el predecesor para cada vértice (en realidad, un tiempo $\mathrm{\Theta }(V)$‍). Cada vértice se visita a lo más una vez, porque solo la primera vez que es alcanzado su distancia es null, y entonces cada vértice está en la fila para ser visitado a lo más una vez. Como examinamos las aristas que inciden en cada vértice solo cuando visitamos desde él, cada arista es examinada a lo más dos veces, una vez por cada vértice sobre el cual incide. Por lo tanto, la búsqueda en anchura pasa un tiempo $O(V+E)$‍ visitando vértices.

Este contenido es una colaboración de los profesores de Dartmouth Computer Science Thomas Cormen y Devin Balkcom, con el equipo de contenidos de computación de Khan Academy. El contenido está bajo licencia CC-BY-NC-SA.