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$V y un conjunto de aristas $E$E? La respuesta es un tiempo $O(V+E)$O, left parenthesis, V, plus, E, right parenthesis.

Veamos qué significa un tiempo $O(V+E)$O, left parenthesis, V, plus, E, right parenthesis. Supón por el momento que $|E| \geq |V|$vertical bar, E, vertical bar, is greater than or equal to, vertical bar, V, vertical bar, 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| \leq |E| + |E| = 2 \cdot |E|$vertical bar, V, vertical bar, plus, vertical bar, E, vertical bar, is less than or equal to, vertical bar, E, vertical bar, plus, vertical bar, E, vertical bar, equals, 2, dot, vertical bar, E, vertical bar. Como ignoramos factores constantes en la notación asintótica, vemos que cuando $|E| \geq |V|$vertical bar, E, vertical bar, is greater than or equal to, vertical bar, V, vertical bar, $O(V+E)$O, left parenthesis, V, plus, E, right parenthesis en realidad significa $O(E)$O, left parenthesis, E, right parenthesis. Sin embargo, si tenemos $|E| < |V|$vertical bar, E, vertical bar, is less than, vertical bar, V, vertical bar, entonces $|V| + |E| \leq |V| + |V| = 2 \cdot |V|$vertical bar, V, vertical bar, plus, vertical bar, E, vertical bar, is less than or equal to, vertical bar, V, vertical bar, plus, vertical bar, V, vertical bar, equals, 2, dot, vertical bar, V, vertical bar, y por lo tanto $O(V+E)$O, left parenthesis, V, plus, E, right parenthesis en realidad significa $O(V)$O, left parenthesis, V, right parenthesis. Podemos juntar ambos casos al decir que $O(V+E)$O, left parenthesis, V, plus, E, right parenthesis en realidad significa $O(\max(V,E))$O, left parenthesis, \max, left parenthesis, V, comma, E, right parenthesis, right parenthesis. En general, si tenemos parámetros $x$x y $y$y, entonces $O(x+y)$O, left parenthesis, x, plus, y, right parenthesis en realidad significa $O(\max(x,y))$O, left parenthesis, \max, left parenthesis, x, comma, y, right parenthesis, right parenthesis.

(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$vertical bar, V, vertical bar, minus, 1. Un grafo en el cual $|E| = |V|-1$vertical bar, E, vertical bar, equals, vertical bar, V, vertical bar, minus, 1 se llama un árbol libre).

¿Cómo es que una búsqueda en anchura se ejecuta en un tiempo $O(V+E)$O, left parenthesis, V, plus, E, right parenthesis? Se tarda un tiempo $O(V)$O, left parenthesis, V, right parenthesis en inicializar la distancia y el predecesor para cada vértice (en realidad, un tiempo $\Theta(V)$\Theta, left parenthesis, V, right parenthesis). 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)$O, left parenthesis, V, plus, E, right parenthesis 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.