Contenido principal
Ciencias de la computación
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 y un conjunto de aristas ? La respuesta es un tiempo .
Veamos qué significa un tiempo . Supón por el momento que , que es el caso para la mayoría de los grafos, especialmente aquellos para los cuales ejecutamos una búsqueda en anchura. Entonces . Como ignoramos factores constantes en la notación asintótica, vemos que cuando , en realidad significa . Sin embargo, si tenemos , entonces , y por lo tanto en realidad significa . Podemos juntar ambos casos al decir que en realidad significa . En general, si tenemos parámetros y , entonces en realidad significa .
(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 . Un grafo en el cual se llama un árbol libre).
¿Cómo es que una búsqueda en anchura se ejecuta en un tiempo ? Se tarda un tiempo en inicializar la distancia y el predecesor para cada vértice (en realidad, un tiempo ). Cada vértice se visita a lo más una vez, porque solo la primera vez que es alcanzado su distancia es visitando vértices.
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 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.
¿Quieres unirte a la conversación?
- porq tengo q hacer esto?(2 votos)
- Para qué sirve el calcular la achura para un grafo(2 votos)
- muy bien falta un poco mas de practica(1 voto)
- Hola ana que te parece este curso estas aprendiendo(2 votos)