Estructures de grafs per a la representació d’informació topologia. Representació i manipulació de grafs utilitzant llistes d’adjacència.

Escriure un programa que trobe un camí des d’una entrada a un laberint fins alguna de les seues possibles eixides. Per a fer-ho, primer es llegirà l’estructura del laberint d’un fitxer i es generarà el graf que la represente. Per a la representació s’utilitzaran llistes d’adjacència. Posteriorment, es buscarà un dels punts d’entrada del graf i es realitzarà un recorregut (qualsevol) fins trobar una eixida.

El laberint a representar es troba emmagatzemat en un fitxer de tipus text (‘laberinto.txt’). El laberint es pot vore com una matriu bidimensional de rang MxN. Els elements de la matriu contenen la informació que reflexa la seua funció dins del laberint: les ‘X’ representen parets, les ‘E’ representen entrades, les ‘S’ representen eixides i les ‘C’ representen passeres lliures del camí. La primera línia del fitxer conté el rang M, la segona el rang N. La resta de les M línies contenen cada una d’elles N caràcters amb els símbols anteriorment indicats.

La informació topològica a introduir en el graf bé donada per la posició de cada símbol dins de la matriu. El graf relacionarà cada casella de tipus ‘E’, ‘S’ o ‘C’ (no ‘X’), amb les seues caselles contigus en la matriu, sempre que perteneixca a algun d’estos tipus. Les connexions vàlides seran únicament les verticals i horitzontals, no es consideraran connectats els elements en diagonal. El graf serà no dirigit i la seua representació es farà mitjançant llistes d’adjacència, on els nodes del graf s’agruparan en forma de vector, utilitzant com identificador de cada node el seu índex en eixe vector.

Un camí generat el graf, es triarà una de les possibles entrades i es procedirà a cercar una eixida, realitzant per a fer-ho un recorregut del graf. Quant es trobe una eixida s’acabarà el recorregut.

Es representarà en pantalla de forma senzilla el recorregut que s’estiga realitzant del graf, utilitzant ’X’ per a representar les parets i el caràcter ‘A’ per a representar les caselles per on s’està avançant la cerca en el graf

Per exemple:

Es ficarà un retard entre cada passa del recorregut per a visualitzar l’evolució del mateix.