Algoritmo para encontrar un camino de Euler en un grafo no muy complicado
Comments(3) En una entrada anterior prometí publicar la solución al problema 291 - The House of Santa Claus. Aquí está:
El problema
Teniendo el siguiente grafo, el problema consiste en encontrar todos los caminos posibles en que se pueden recorrer todas las aristas del grafo una única vez, partiendo de la esquina inferior izquierda. Esto en matemática de grafos es conocido cómo un camino de Euler.
El grafo
Cada nodo está numerado como se muestra en la figura y cada arista es bidireccional, es decir, se puede ir del nodo 1 al 5 si y sólo si se puede ir del nodo 5 al 1.
La solución
El algoritmo que se me ocurrió para solucionar el problema fue crear una función recursiva que se llamara cada vez que se visite un nodo, y que a su vez vuelva a llamarse con los próximos nodos a visitar, usando cómo parámetro la lista de los nodos ya visitados en el orden de visita. Me explico: la primera vez la función se llamará con los nodos visitados, es decir, [1], y se llamará a ella misma para cada nodo que sea posible visitar a partir del nodo actual. En nuestro caso, la llamada anterior llamará a la misma función 3 veces: una para cada posible siguiente nodo, a saber, se llamará nuevamente con los parámetros [12], [13], [15]. Puede verse que si se tiene la lista de nodos visitados en el orden de visita, se sabrá que aristas ya han sido visitadadas. Por ejemplo, para saber si ya se visitó la arista que conecta los nodos 4 y 5, bastará con fijarse si en la lista están dichos números en posiciones adyacentes. De esta manera, la llamada recursiva de la función sólo se generará sobre los nodos destino a los que sea posible visitar (o sea que no se repita arista). La recursividad se detendrá o bien cuando no es posible moverse a otro nodo sin repetir arista o bien cuando se han recorrido 8 aristas.
La implementación
Mi solución está escrita en C++.
La semana pasada tuve la oportunidad de ir a 
