Taller Busqueda en Anchura (Ranas)

¿Que es Búsqueda en Anchura?

Búsqueda en anchura es un algoritmo para recorrer o buscar elementos de un grafo(usado frecuentemente en arboles). Se comienza por la raíz y se explora todos los hijos de este nodo. A continuación se explora cada unos de los hijos de los hermanos y así sucesivamente hasta encontrar la solución.

¿Cual es la complejidad temporal para la búsqueda en Anchura?

Su complejidad tanto espacial como temporal es exponencial, y está en O (n^p), siendo n el número medio de sucesores, y p el nivel donde se alcanza la solución; por ello, esta estrategia es sólo aplicable a problemas no demasiado amplios.

Este procedimiento es completo, ya que encontrará siempre una solución si es que la hay, pero en general no es óptimo. Para implementarlo se ha hecho uso de una cola FIFO.

Ejercicio 

Hay tres personas de bien y 3 políticos los cuales están en la orilla 1 y desean pasar el rió en una
balsa y llegar a la orilla 2 Resolverlo por el método de búsqueda en Anchura