Salida de un laberinto por búsqueda en profundidad

Ejercicio:

El problema del laberinto puede verse como una serie de habitaciones con puertas por las que se puede pasar a habitaciones adyacentes. La idea es que empezando por una habitación de entrada, hay que encontrar el camino que nos lleva a la habitación de salida. Para ello, de una habitación a otra sólo se puede pasar si hay una puerta entre las dos habitaciones. Todo esto se puede representar mediante un grafo. a) Indíquese cuáles serán los vértices, las aristas y qué tipo de grafo necesitaremos.

b) Escríbase un procedimiento que, tomando una habitación de entrada, otra de salida y el grafo representando el laberinto, escriba, si existe, las habitaciones que componen el camino desde la entrada a la salida. ¿En qué algoritmo se basa la solución propuesta?

Notas:
1. Si se usan estructuras auxiliares, justifíquese su uso.
2. Úsense todas las estructuras necesarias manipulándolas como TAD.
3. El camino resultante, si existe, se puede escribir tanto desde la entrada a la salida, como desde la salida a la entrada.
4. En el caso de que exista más de un camino desde la entrada a la salida, sólo se escribirá el primero que se encuentre.
5. Los vértices no tienen ningún tipo de información asociada, y no se puede modificar su estructura.

Una posible solución en pseudocódigo:

Los nodos son las habitaciones y las puertas las arístas. Necesitaremos un grafo no dirigido y no etiquetado ya que las puertas suponemos que se pueden abrir desde los dos lados.

clase SalidaLaberinto

proc SalidaLaberinto(u,dest: Object, g:Graph)
sol:List
visitados: Set
alg
sol:=List()
visitados:=Set()
si depthFirstSearchModified(u,dest,g,visitados,sol)
mostrar(sol)
| otros:
mostrar("No hay camino hacia la salida")
fsi
fin

func depthFirstSearchModified(u: Object, dest:Object, g: Graph; ent/sal visitados: Set, sol:List) dev(b:Boolean)
v: Object
adyacentes: Set
itd: Iterator
alg
b:=false
sol.add(u)
si u.equals(dest)
b:=true
|otros:
visitados.add(u)
adyacentes := g.getAdjacents(u)
itd := adyacentes.iterator()
mientras itd.hasNext() y no b
v := itd.next()
si no visitados.contains(v):// Equivalente a “si no visitado”
b:=depthFirstSearch(v, g, visitados, sol)
fsi
fmientras
si no b
sol.remove(u)
fsi
fsi
fin
finClase