Before you keep reading...
Runestone Academy can only continue if we get support from individuals like you. As a student you are well aware of the high cost of textbooks. Our mission is to provide great books to you for free, but we ask that you consider a $10 donation, more if you can or less if $10 is a burden.
Before you keep reading...
Making great stuff takes time and $$. If you appreciate the book you are reading now and want to keep quality materials free for other students please consider a donation to Runestone Academy. We ask that you consider a $10 donation, but if you can give more thats great, if $10 is too much for your budget we would be happy with whatever you can afford as a show of support.
7.10. Análisis de la búsqueda en anchura
Antes de continuar con otros algoritmos de grafos vamos a analizar el desempeño de tiempo de ejecución del algoritmo de búsqueda en anchura. Lo primero que debemos observar es que el ciclo while se ejecuta, como máximo, una vez para cada vértice del grafo . Usted puede verificar que esto es cierto porque un vértice debe ser blanco antes de que pueda ser examinado y agregado a la cola. Esto nos da para el ciclo while. El ciclo for, que está anidado dentro del while, se ejecuta como máximo una vez para cada arista del grafo, . La razón es que cada vértice sale de la cola a lo sumo una vez y que examinamos una arista del nodo al nodo únicamente cuando el nodo sale de la cola. Esto nos da para el ciclo for. Combinando los dos ciclos nos da .
Por supuesto, hacer la búsqueda en anchura es sólo una parte de la tarea. Seguir los enlaces desde el nodo inicial hasta el nodo objetivo es la otra parte de la tarea. El peor caso para esto sería que el grafo fuera una única cadena larga. En ese caso, recorrer todos los vértices sería . El caso normal será alguna fracción de pero en todo caso escribiríamos .
Finalmente, al menos para este problema, también está el tiempo requerido para construir el grafo inicial. Dejamos el análisis de la función construirGrafo
como ejercicio para usted.
You have attempted
1 of
1 activities on this page