Ohne das Problem der Zyklen zu lösen, lassen sich Probleme in ungerichteten Graphen nicht lösen. Ein sinnvoller Ansatz, dieses Problem zu bewältigen, ist aber sehr naheliegend. Wir müssen nur dafür sorgen, dass wir uns die Knoten merken, an denen wir schon gewesen sind.
Das führt zu folgendem veränderten Programm:
Eine sinnvolle Lösung besteht darin, die besuchten Knoten in einer besucht - Liste zu führen. Diese besucht - Liste enthält am Beginn nur den Startknoten, dann den nächsten besuchten Knoten zusätzlich usw.
Es gibt mehrere Möglichkeiten, diese Liste zu verwalten. Nutzt man die Rekursion, dann kann uns auch hier wieder der Systemstack die Arbeit abnehmen: Bei einem backtracking wird die besucht - Liste automatisch wieder in den vorherigen Zustand versetzt, der zum Knoten vorher gehört, da die besucht - Liste als Variable in jeder Rekursionsebene geführt wird und beim Rücksprung in der Rekursion jeweils die dort gültige besucht - Liste wieder vom stack geholt wird, die den beim Schritt in die Tiefe hinzugekommenen Knoten nicht enthält.
So wird die besucht - Liste jeweils auf den aktuell gültigen Weg aktualisiert, ein erfolgloser Knoten wird aus der besucht - Liste entfernt, wenn man ihn aus dem Weg entfernt.
Ein sehr vorteilhafter "Nebeneffekt" kommt hinzu: Die besucht - Liste enthält nun unseren gesuchten Weg zum Knoten und kann am Ende also einfach als Lösung des Problems ausgegeben werden.