¿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(V+E) .
Veamos qué significa un tiempo O(V+E) O(V+E) . Supón por el momento que EV |E| \geq |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+EE+E=2E |V| + |E| \leq |E| + |E| = 2 \cdot |E| . Como ignoramos factores constantes en la notación asintótica, vemos que cuando EV |E| \geq |V| , O(V+E) O(V+E) en realidad significa O(E) O(E) . Sin embargo, si tenemos E<V |E| < |V| , entonces V+EV+V=2V |V| + |E| \leq |V| + |V| = 2 \cdot |V| , y por lo tanto O(V+E) O(V+E) en realidad significa O(V) O(V) . Podemos juntar ambos casos al decir que O(V+E) O(V+E) en realidad significa O(max(V,E)) O(\max(V,E)) . En general, si tenemos parámetros x x y y y , entonces O(x+y) O(x+y) 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 V1 |V|-1 . Un grafo en el cual E=V1 |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) O(V+E) ? Se tarda un tiempo O(V) O(V) 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(V+E) 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.
Cargando