Dado un grafo G = (V, E) tenemos que encontrar el Circuito Hamiltoniano utilizando el enfoque de Backtracking. Comenzamos nuestra búsqueda desde cualquier vértice arbitrario digamos ‘a’. Este vértice ‘a’ se convierte en la raíz de nuestro árbol implícito. El primer elemento de nuestra solución parcial es el primer vértice intermedio del Ciclo Hamiltoniano que se va a construir. El siguiente vértice adyacente se selecciona por orden alfabético. Si en cualquier etapa cualquier vértice arbitrario hace un ciclo con cualquier vértice que no sea el vértice ‘a’ entonces decimos que se ha llegado a un punto muerto. En este caso, retrocedemos un paso, y de nuevo se inicia la búsqueda seleccionando otro vértice y retrocediendo el elemento de la solución parcial; hay que eliminarlo. La búsqueda mediante backtracking es exitosa si se obtiene un Ciclo Hamiltoniano.
Ejemplo: Consideremos un grafo G = (V, E) mostrado en la fig. Tenemos que encontrar un circuito hamiltoniano utilizando el método de Backtracking.
Solución: En primer lugar, comenzamos nuestra búsqueda con el vértice ‘a’. Este vértice ‘a’ se convierte en la raíz de nuestro árbol implícito.
A continuación, elegimos el vértice ‘b’ adyacente a ‘a’ por ser el primero en orden lexicográfico (b, c, d).
A continuación, seleccionamos ‘c’ adyacente a ‘b.’
A continuación, seleccionamos ‘d’ adyacente a ‘c.’
A continuación, seleccionamos ‘e’ adyacente a ‘d.’
A continuación, seleccionamos el vértice ‘f’ adyacente a ‘e.’ Los vértices adyacentes a ‘f’ son d y e, pero ya se han visitado. Así, obtenemos el callejón sin salida, y retrocedemos un paso y eliminamos el vértice ‘f’ de la solución parcial.
Desde el backtracking, el vértice adyacente a ‘e’ es b, c, d, y f del cual el vértice ‘f’ ya ha sido comprobado, y b, c, d ya han sido visitados. Por lo tanto, de nuevo retrocedemos un paso. Ahora, los vértices adyacentes a d son e, f de los cuales e ya ha sido comprobado, y los adyacentes de ‘f’ son d y e. Si el vértice ‘e’, los revisita obtenemos un estado muerto. Así que de nuevo retrocedemos un paso.
Ahora, el adyacente de c es ‘e’ y el adyacente de ‘e’ es ‘f’ y el adyacente de ‘f’ es ‘d’ y el adyacente de ‘d’ es ‘a’. Aquí obtenemos el ciclo hamiltoniano, ya que todos los vértices distintos del vértice inicial ‘a’ se visitan una sola vez. (a – b – c – e – f -d – a).
Otra vez vuelta atrás
Aquí hemos generado un circuito hamiltoniano, pero también se puede obtener otro circuito hamiltoniano considerando otro vértice.