Algoritmo de busqueda en anchura

[Damian Schlimovich]

Alguien me podria explicar en palabras si es tan amable, para que es
la cola del algoritmo de busqueda en profundida. Y en consecuencia q
es lo q hace exactamente el algoritmo?
Muchas gracias
saludos

[Juan Daniel]

En el algoritmo de búsqueda en profundidad (el del libro) no aparece ninguna cola, el de la cola es el de búsqueda en anchura. La cola sirve para asegurarse de que se añadan todos los vértices del grafo al árbol generador. Fijate que el primer vértice de la cola se utiliza para determinar sus adyacentes, los cuales se agregan a la cola y en algún momento estos también serán el primer vértice de la cola. En criollo lo que hace este algoritmo es generarte un árbol ancho, ya que toma los vértices adyacentes a un vértice (que no estén en el árbol) y los pone como hijo de dicho vértice.

--
Prigioni Juan Daniel
<jdpri...@gmail.com>

[Emi Izquierdo]

Justamente yo tengo una duda leve sobre el tema. Quería saber por qué el algoritmo de Busqueda en Profundidad es recursivo y el de Busqueda en Anchura no. ¿es posible programar este último de esa forma o directamente no se puede por la definición del proceso?

[Diego Galizzi]

Que sea recursivo o no es simplemente una forma de describirlo. Ciertos algoritmos son más fáciles de entender de forma recursiva y otros de forma iterativa. La búsqueda en profundidad se puede escribir de forma iterativa y la búsqueda en anchura se puede escribir de forma recursiva. Son diferentes formas de verlo.

Saludos, Diego.