Gegeven een grafiek G = (V, E) moeten we het Hamiltonian Circuit vinden met behulp van Backtracking. We beginnen onze zoektocht vanaf een willekeurig hoekpunt, zeg ‘a’. Dit hoekpunt ‘a’ wordt de wortel van onze impliciete boom. Het eerste element van onze gedeeltelijke oplossing is het eerste tussenliggende hoekpunt van de te construeren Hamiltoniaanse kringloop. Het volgende aangrenzende hoekpunt wordt in alfabetische volgorde gekozen. Als op enig moment een willekeurig hoekpunt een cyclus maakt met een ander hoekpunt dan hoekpunt ‘a’, dan zeggen we dat een doodlopende weg is bereikt. In dat geval gaan we één stap terug, en begint het zoeken opnieuw door een ander hoekpunt te kiezen en het element uit de gedeeltelijke oplossing terug te volgen; het element moet worden verwijderd. Het zoeken met behulp van backtracking is geslaagd als een Hamiltoniaanse Cyclus wordt verkregen.
Voorbeeld: Beschouw een grafiek G = (V, E) in fig. we moeten een Hamiltoniaanse kring vinden met behulp van Backtracking methode.
Oplossing: Allereerst beginnen we onze zoektocht met hoekpunt ‘a.’ dit hoekpunt ‘a’ wordt de wortel van onze impliciete boom.
Volgende kiezen we hoekpunt ‘b’ dat grenst aan ‘a’, omdat deze in lexicografische volgorde (b, c, d) op de eerste plaats komt.
Volgende, we kiezen ‘c’ aangrenzend aan ‘b.’
Volgende, we kiezen ‘d’ aangrenzend aan ‘c.’
Naar aanleiding hiervan selecteren we ‘e’ dat grenst aan ‘d.’
Naar aanleiding hiervan selecteren we hoekpunt ‘f’ dat grenst aan ‘e.’ Het hoekpunt dat aan ‘f’ grenst zijn d en e, maar die hebben elkaar al bezocht. We krijgen dus een doodlopende weg, en we gaan een stap terug en verwijderen het hoekpunt ‘f’ uit de gedeeltelijke oplossing.
Uit backtracking blijkt dat het hoekpunt dat aan ‘e’ grenst b, c, d en f is, waarvan hoekpunt ‘f’ al is gecontroleerd, en b, c, d al zijn bezocht. Dus, we backtracken weer een stap. Nu, de hoekpunten grenzend aan d zijn e, f waarvan e al is gecontroleerd, en grenzend aan ‘f’ zijn d en e. Als ‘e’ hoekpunt, opnieuw bezocht zijn krijgen we een dode toestand. Dus gaan we weer een stap terug.
Nu, aangrenzend aan c is ‘e’ en aangrenzend aan ‘e’ is ‘f’ en aangrenzend aan ‘f’ is ‘d’ en aangrenzend aan ‘d’ is ‘a.’ Hier krijgen we de Hamiltoniaanse Cyclus, omdat alle andere hoekpunten dan het beginhoekpunt ‘a’ maar één keer worden bezocht. (a – b – c – e – f -d – a).
Wederom Backtrack
Hier hebben we één Hamiltonian circuit gegenereerd, maar een andere Hamiltoniaanse kring kan ook worden verkregen door een ander hoekpunt te beschouwen.