Estructura de Datos y Algoritmos
1er. Sem 2004
Tarea 4: Búsqueda de ciclos en Grafos
El objetivo de esta tarea es
ejercitar el manejo de grafos, su representación y la
programación de los algortimos de búsqueda.
Desarrolle el programa testCiclo.
>$ testCiclo <nombre_de_archivo_de_entrada>
El programa nos permite identificar si un grafo posee ciclos. El grafo
será ingresado vía el archivo pasado como argumento. La
salida del programa será una notificación "NO HAY CICLOS"
o el listado de los nodos que componene el primer ciclo encontrado.
El fromato del archivo de entrada es:
<número de vértices>
<número de vertice en orden creciente> <lista de
adyacencia del vértice>
:
<número del último vértice>
<lista de adyacencia del vértice>
Por ejemplo un archivo podría ser:
5
0 1 3
1 4 3 2
2 4
3 2 4
4 0
Se asume que el grafo ingresado es válido y está bien
formado.
Para la lectura de la lista de adyacencia usted puede usar un
código como el
mostrado aquí.
Para la creación de una matriz bidimensional definida a
tiempo de ejecución, usted puede utilizar este programa. Ojo
cortesía de Rodrigo Pinto (2004)