Gdy mamy graf G = (V, E) musimy znaleźć Hamiltonian Circuit używając podejścia Backtracking. Rozpoczynamy nasze poszukiwania od dowolnego dowolnego wierzchołka powiedzmy 'a'. Ten wierzchołek 'a' staje się korzeniem naszego drzewa implicite. Pierwszym elementem naszego częściowego rozwiązania jest pierwszy pośredni wierzchołek Cyklu Hamiltonowskiego, który ma zostać skonstruowany. Następny sąsiedni wierzchołek wybierany jest w kolejności alfabetycznej. Jeśli na dowolnym etapie dowolny wierzchołek tworzy cykl z dowolnym wierzchołkiem innym niż wierzchołek 'a' to mówimy, że osiągnięty został ślepy zaułek. W takim przypadku cofamy się o jeden krok i ponownie rozpoczynamy poszukiwanie wybierając kolejny wierzchołek i cofamy się o element z częściowego; rozwiązania, który musi zostać usunięty. Poszukiwanie z wykorzystaniem backtrackingu kończy się sukcesem, jeśli otrzymamy Cykl Hamiltonowski.
Przykład: Rozważmy graf G = (V, E) pokazany na rys. musimy znaleźć obieg Hamiltonowski używając metody Backtracking.
Rozwiązanie: Po pierwsze, rozpoczynamy nasze poszukiwania od wierzchołka 'a.' ten wierzchołek 'a' staje się korzeniem naszego drzewa implicite.
Następnie wybieramy wierzchołek 'b' sąsiadujący z 'a', ponieważ jest on pierwszy w porządku leksykograficznym (b, c, d).
Następnie wybieramy wierzchołek 'c' sąsiadujący z 'b.'
Następnie wybieramy 'd' sąsiadujący z 'c.'.
Następnie wybieramy wierzchołek 'e' przylegający do 'd.'
Następnie wybieramy wierzchołek 'f' przylegający do 'e.'. Wierzchołki sąsiadujące z 'f' to d i e, ale one już się odwiedziły. Otrzymujemy więc ślepy zaułek, cofamy się o jeden krok i usuwamy wierzchołek 'f' z rozwiązania częściowego.
Z backtrackingu wynika, że wierzchołkami sąsiadującymi z 'e' są b, c, d i f, z których wierzchołek 'f' został już sprawdzony, a b, c, d już odwiedzili. Zatem ponownie cofamy się o jeden krok. Teraz, wierzchołki sąsiadujące z d to e, f, z których e został już sprawdzony, a sąsiadujące z 'f' to d i e. Jeśli wierzchołek 'e', ponownie odwiedził je otrzymamy martwy stan. Więc znowu cofamy się o jeden krok.
Teraz, przylegający do c jest 'e' i przylegający do 'e' jest 'f' i przylegający do 'f' jest 'd' i przylegający do 'd' jest 'a.' Tutaj otrzymujemy Cykl Hamiltonowski, ponieważ wszystkie wierzchołki inne niż wierzchołek początkowy 'a' są odwiedzane tylko raz. (a – b – c – e – f -d – a).
Ponownie Backtrack
Tutaj wygenerowaliśmy jeden obieg hamiltonowski, ale inny obwód Hamiltonowski można również uzyskać, biorąc pod uwagę inny wierzchołek.
.