Design and Analysis of Algorithms

Abstract Algorithms 4—Backtracking 325

12.4.3 Example 3: Hamiltonian Circuits

Let G = < V, E > be a connected graph with n nodes. A Hamiltonian circuit or cycle is a round trip path along

n edges, which visits each node exactly once and returns to the starting node. In the following two graphs, the

fi rst has at least one circuit, while the second one does not have any. See Fig. 12.4.

The solution vector is x[0 : n − 1], such that x[i] represents the ith visited node in the circuit. We have

to select a set of possible vertices for x[k], once x[0], x[1], ..., x[k − 1] are already chosen. It should of course

be connected by an edge to x[k − 1]. The fi nal node x[n − 1] must be connected to both x[n − 2] and x[0].

Referring to the Listings section, ...