7.26. Ejercicios de programación¶

Modifique la función de búsqueda en profundidad para producir un ordenamiento topológico.
Modifique la búsqueda en profundidad para producir componentes fuertemente conectados.
Escriba el método transponer para la clase Grafo.
Utilizando la búsqueda en anchura, escriba un algoritmo que puede determinar la ruta más corta de cada vértice a cada uno de los otros vértices. Ésto se llama el problema de la ruta más corta de todas las parejas.
Utilizando la búsqueda en anchura, revise el programa del laberinto del capítulo de recursividad para encontrar la ruta más corta para salir del laberinto.
Escriba un programa para resolver el siguiente problema: Usted tiene dos jarras, una jarra de 4 galones y una jarra de 3 galones. Ninguna de las jarras tiene marcas en ella. Hay una bomba que se puede utilizar para llenar las jarras con agua. ¿Cómo se pueden obtener exactamente dos galones de agua en la jarra de 4 galones?
Generalice el problema anterior para que los parámetros de su solución incluyen los tamaños de cada jarra y la cantidad final de agua que queda en la jarra más grande.
Escriba un programa que resuelva el siguiente problema: Tres misioneros y tres caníbales llegan a un río y encuentran un bote con capacidad para dos personas. Todos deben cruzar el río para continuar en el viaje. Sin embargo, si los caníbales sobrepasan en número a los misioneros en cada orilla, los misioneros serán comidos. Encuentra una serie de cruces que llevarán a todos a salvo al otro lado del río.