A Hamiltonian circuit of a graph is a tour that visits every vertex once, and ends at its starting vertex. Finding out if a graph has a Hamiltonian circuit is an NP-complete problem.

This is a backtracking algorithm to find all of the Hamiltonian circuits in a graph. The input is an adjacency matrix, and it calls a user-specified callback with an array containing the order of vertices for each Hamiltonian circuit it finds.

The first vertex for all circuits is fixed at `0`, and the last vertex is limited to being less than the second vertex. These are normalisation conditions that prevent duplicates that are cyclic permutations or reversals respectively.

#include <stdlib.h> static unsigned int circuit_contains(const unsigned int *circuit, unsigned int c, unsigned int v) { unsigned int i; unsigned int contains = 0; for (i = 0; i < c && !contains; i++) { contains = circuit[i] == v; } return contains; } typedef void (*circuitfn)(const unsigned int *, size_t); static void hamiltonian_circuits_recursive(unsigned int **adjmat, size_t n, unsigned int *circuit, unsigned int c, circuitfn fun) { if (c == n) { /* Found a circuit */ fun(circuit, n); } else { unsigned int v; for (v = 1; v < n; v++) { if (!circuit_contains(circuit, c, v) /* Vertex is not in the circuit already */ && adjmat[circuit[ c - 1]][v] == 1 /* Vertex is adjacent to the previous vertex */ && (c < n - 1 || (adjmat[0][v] == 1 /* Last vertex is adjacent to the first */ && v < circuit[1]))) /* Last vertex is less than the second */ { circuit[ c] = v; hamiltonian_circuits_recursive(adjmat, n, circuit, c + 1, fun); } } } } void hamiltonian_circuits(unsigned int **adjmat, size_t n, circuitfn fun) { unsigned int *circuit; circuit = malloc(n * sizeof(unsigned int)); if (circuit == NULL) { return; } circuit[0] = 0; hamiltonian_circuits_recursive(adjmat, n, circuit, 1, fun); free(circuit); }

This is an example program that finds all Hamiltonian circuits on the complete graph of order 5. With the constraints on cyclic permutations and direction mentioned above, there are \((n – 1)!/2\) Hamiltonian circuits on a complete graph of order \(n\).

#include <stdio.h> #include <stdlib.h> static void print_circuit(const unsigned int *circuit, size_t len) { unsigned int v; for (v = 0; v < len; v++) { printf("%d ", circuit[v]); } putchar('\n'); } int main(void) { unsigned int **adjmat; const size_t n = 5; unsigned int i, j; /* Create a complete graph on 5 vertices */ adjmat = malloc(n * sizeof(unsigned int *)); for (i = 0; i < n; i++) { adjmat[i] = malloc(n * sizeof(unsigned int)); for (j = 0; j < n; j++) { adjmat[i][j] = 1; } } hamiltonian_circuits(adjmat, n, print_circuit); for (i = 0; i < n; i++) { free(adjmat[i]); } free(adjmat); return 0; }

Here is the output. Notice there are \((5 – 1)!/2 = 12\) circuits:

0 2 3 4 1 0 2 4 3 1 0 3 1 4 2 0 3 2 4 1 0 3 4 1 2 0 3 4 2 1 0 4 1 2 3 0 4 1 3 2 0 4 2 1 3 0 4 2 3 1 0 4 3 1 2 0 4 3 2 1