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, left parenthesis, V, plus, E, right parenthesis.
Veamos qué significa un tiempo O, left parenthesis, V, plus, E, right parenthesis. Supón por el momento que 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 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 vertical bar, E, vertical bar, is greater than or equal to, vertical bar, V, vertical bar, O, left parenthesis, V, plus, E, right parenthesis en realidad significa O, left parenthesis, E, right parenthesis. Sin embargo, si tenemos vertical bar, E, vertical bar, is less than, vertical bar, V, vertical bar, entonces 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, left parenthesis, V, plus, E, right parenthesis en realidad significa O, left parenthesis, V, right parenthesis. Podemos juntar ambos casos diciendo que O, left parenthesis, V, plus, E, right parenthesis en realidad significa O(max(V,E)) O(\max(V,E)) . En general, si tenemos parámetros x y y, entonces O, left parenthesis, x, plus, y, right parenthesis en realidad significa O(max(x,y)) 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 vertical bar, V, vertical bar, minus, 1. Un grafo en el cual 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, left parenthesis, V, plus, E, right parenthesis? Se tarda un tiempo O, left parenthesis, V, right parenthesis en inicializar la distancia y el predecesor para cada vértice (en realidad, un tiempo Θ(V) \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, 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.