Tag Archives: Hamiltonian Circuit

Hamiltonian circuits using backtracking in C

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