Uso de las estructuras de grafos para la representación de información topólogica. Representación y manipulación de grafos utilizando listas de adyacencia.

Escribir un programa que encuentre un camino desde una entrada a un laberinto hasta alguna de sus posibles salidas. Para ello, primero se leerá la estructura del laberinto de un fichero y se generará el grafo que la represente. Para la representación se utilizarán listas de adyacencia. Posteriormente, se buscará uno de los puntos de entrada del grafo y se realizará un recorrido (cualquiera) hasta encontrar una salida.

El laberinto a representar se encuentra almacenado en un fichero de tipo texto (laberinto.txt). El laberinto puede verse como una matriz bidimensional de rango MxN. Los elementos de dicha matriz contienen la información que refleja su función dentro del laberinto: las ‘X’ representan paredes, las ‘E’ representan entradas, las ‘S’ representan salidas y las ‘C’ representan pasos libres del camino. La primera línea del fichero contiene el rango M, la segunda el rango N. El resto de las M líneas contienen cada una de ellas N caracteres con los símbolos anteriormente indicados.

La información topológica a introducir en el grafo viene dada por la posición de cada símbolo dentro de la matriz. El grafo relacionará cada casilla de tipo ‘E’, ‘S’ o ‘C’ (no ‘X’), con sus casillas contiguas en la matriz, siempre que pertenezcan a alguno de estos tipos. Las conexiones válidas serán únicamente las verticales y horizontales, no se considerarán conectados los elementos en diagonal. El grafo será no dirigido y su representación se hará mediante listas de adyacencia, donde los nodos del grafo se agruparán en forma de vector, utilizando como identificador de cada nodo su índice en dicho vector.

Una vez generado el grafo se seleccionará una de las posibles entradas y se procederá a buscar una salida, realizando para ello un recorrido del grafo. Cuando se encuentre una salida se finalizará el recorrido.

Se representará en pantalla de forma sencilla el recorrido que se esté realizando del grafo, utilizando’X’ para representar las paredes y el carácter ‘A’ para representar las casillas por las que está avanzando la búsqueda en el grafo

Por ejemplo:

Se pondrá un retardo entre cada paso del recorrido para visualizar la evolución durante el mismo.