Gegeben einen Graphen G = (V, E) müssen wir den Hamiltonian Circuit mittels Backtracking-Ansatz finden. Wir beginnen unsere Suche an einem beliebigen Knoten, sagen wir ‚a‘. Dieser Vertex ‚a‘ wird zur Wurzel unseres impliziten Baums. Das erste Element unserer Teillösung ist der erste Zwischenvertex des zu konstruierenden Hamiltonkreises. Der nächste benachbarte Vertex wird in alphabetischer Reihenfolge ausgewählt. Wenn zu irgendeinem Zeitpunkt ein beliebiger Vertex einen Zyklus mit einem anderen Vertex als dem Vertex ‚a‘ bildet, sagen wir, dass eine Sackgasse erreicht ist. In diesem Fall gehen wir einen Schritt zurück, und die Suche beginnt erneut, indem wir einen anderen Scheitelpunkt auswählen und das Element aus der Teillösung zurückverfolgen; es muss entfernt werden. Die Suche mit Backtracking ist erfolgreich, wenn ein Hamilton-Zyklus erhalten wird.
Beispiel: Betrachten wir den in Abb. dargestellten Graphen G = (V, E), so müssen wir mit der Backtracking-Methode einen Hamiltonschen Kreislauf finden.
Lösung: Zunächst beginnen wir unsere Suche mit dem Knoten ‚a‘. Dieser Knoten ‚a‘ wird zur Wurzel unseres impliziten Baums.
Nächstens wählen wir den an ‚a‘ angrenzenden Knoten ‚b‘, da er in lexikografischer Reihenfolge (b, c, d) an erster Stelle steht.
Als nächstes wählen wir ‚c‘ neben ‚b‘.‘
Als nächstes wählen wir ‚d‘ neben ‚c‘.‘
Als nächstes wählen wir ‚e‘ neben ‚d.‘
Als nächstes wählen wir den Scheitelpunkt ‚f‘ neben ‚e‘. Der an ‚f‘ angrenzende Scheitelpunkt ist d und e, aber sie haben bereits besucht. So kommen wir in die Sackgasse, und wir gehen einen Schritt zurück und entfernen den Scheitelpunkt ‚f‘ aus der Teillösung.
Aus dem Backtracking ergibt sich, dass der an ‚e‘ angrenzende Knoten b, c, d und f ist, von denen der Knoten ‚f‘ bereits geprüft wurde, und b, c, d bereits besucht wurden. Also gehen wir wieder einen Schritt zurück. Nun sind die Vertexe, die an d angrenzen, e, f, von dem aus e bereits überprüft wurde, und angrenzend an ‚f‘ sind d und e. Wenn der Vertex ‚e‘ erneut besucht wird, erhalten wir einen toten Zustand. Also gehen wir wieder einen Schritt zurück.
Nun ist benachbart zu c ‚e‘ und benachbart zu ‚e‘ ist ‚f‘ und benachbart zu ‚f‘ ist ‚d‘ und benachbart zu ‚d‘ ist ‚a‘. Hier erhalten wir den Hamilton-Zyklus, da alle Vertexe außer dem Startvertex ‚a‘ nur einmal besucht werden. (a – b – c – e – f -d – a).
Zurück
Hier haben wir einen Hamiltonschen Kreis erzeugt, aber eine andere Hamilton’sche Schaltung kann auch durch die Betrachtung eines anderen Scheitelpunktes erhalten werden.