Tag Archives: Euler Circuit

Euler circuits using backtracking in C

An Euler circuit on a graph is a tour that traverses every edge before returning to its starting point (compare to a Hamiltonian circuit, which visits every vertex). An Euler circuit may visit vertices more than once.

This is a backtracking algorithm to find all Euler circuits of a graph. It takes the graph in the form of an array of edges, and a user-specified callback, which it calls for every circuit found.

In order to extend a partial circuit with a new edge, the algorithm needs to check that the new edge:

  1. Isn’t in the circuit already
  2. Contains the terminal vertex of the partial circuit as one of its endpoints

In order to facilitate (2), the algorithm keeps track of the terminal vertex of the partial circuit.

The first edge of every circuit is fixed at edge 0, and the first terminal vertex is its second vertex. These two normalisation conditions ensure that no duplicate circuits are generated.

#include <stdlib.h>

typedef struct {
    unsigned int first;
    unsigned int second;
} edge;

static unsigned int circuit_contains(const unsigned int *circuit, unsigned int c, unsigned int e)
{
    unsigned int i;
    unsigned int contains = 0;
    for (i = 0; i < c && !contains; i++) {
        contains = circuit[i] == e;
    }
    return contains;
}

typedef void (*circuitfn)(const edge *, unsigned int, const unsigned int *);

static void euler_circuits_recursive(const edge *edges, unsigned int n, unsigned int *circuit, 
        unsigned int c, unsigned int tv, circuitfn fun)
{
    if (c == n) {
        /* Found a circuit */
        fun(edges, n, circuit);
    }
    else {
        unsigned int e;
        for (e = 1; e < n; e++) {
            if (!circuit_contains(circuit, c, e) 
                    && (edges[e].first == tv || edges[e].second == tv))
            {
                circuit[ c] = e;   
                euler_circuits_recursive(edges, n, circuit, c + 1,
                       edges[e].first == tv ? edges[e].second : edges[e].first,
                       fun);
            }
        }
    }
}

void euler_circuits(const edge *edges, unsigned int n, circuitfn fun)
{
    unsigned int *circuit;
    circuit = malloc(n * sizeof(unsigned int));
    if (circuit == NULL) {
        return;
    }
    circuit[0] = 0;
    euler_circuits_recursive(edges, n, circuit, 1, edges[0].second, fun);
    free(circuit);
}

Here is an example program that finds all of the Euler circuits on the complete graph of order 5:

#include <stdio.h>
#include <stdlib.h>

/* Calculate the nth triangular number T(n) */
unsigned int triangular_number(unsigned int n)
{
    return (n * (n + 1)) / 2;
}

/* Construct a complete graph on v vertices */
edge *complete_graph(unsigned int v)
{
    const unsigned int n = triangular_number(v - 1);
    unsigned int i, j, k;
    edge *edges = malloc(n * sizeof(edge));
    if (edges != NULL) {
        for (i = 0, k = 0; i < v - 1; i++) {
            for (j = i + 1; j < v; j++) {
                edges[k].first = i;
                edges[k].second = j;
                k++;
            }
        }
    }
    return edges;
}

/* Print the edges in a circuit */
static void print_circuit(const edge *edges, unsigned int n, const unsigned int *circuit)
{
    unsigned int e;
    for (e = 0; e < n; e++) {
        printf("(%u, %u) ", edges[circuit[e]].first, edges[circuit[e]].second);
    }
    putchar('\n');
}

int main(void)
{
    const unsigned int v = 5;
    const unsigned int n = triangular_number(v - 1);
    edge *edges;
    
    edges = complete_graph(v);
    if (edges == NULL) {
        return 1;
    }
    euler_circuits(edges, n, print_circuit);
    free(edges);

    return 0;
}

Here is the output. There are 132 Euler circuits on the complete graph of order 5:

(0, 1) (1, 2) (0, 2) (0, 3) (1, 3) (1, 4) (2, 4) (2, 3) (3, 4) (0, 4) 
(0, 1) (1, 2) (0, 2) (0, 3) (1, 3) (1, 4) (3, 4) (2, 3) (2, 4) (0, 4) 
(0, 1) (1, 2) (0, 2) (0, 3) (2, 3) (2, 4) (1, 4) (1, 3) (3, 4) (0, 4) 
(0, 1) (1, 2) (0, 2) (0, 3) (2, 3) (2, 4) (3, 4) (1, 3) (1, 4) (0, 4) 
(0, 1) (1, 2) (0, 2) (0, 3) (3, 4) (1, 4) (1, 3) (2, 3) (2, 4) (0, 4) 
(0, 1) (1, 2) (0, 2) (0, 3) (3, 4) (2, 4) (2, 3) (1, 3) (1, 4) (0, 4) 
(0, 1) (1, 2) (0, 2) (0, 4) (1, 4) (1, 3) (2, 3) (2, 4) (3, 4) (0, 3) 
(0, 1) (1, 2) (0, 2) (0, 4) (1, 4) (1, 3) (3, 4) (2, 4) (2, 3) (0, 3) 
(0, 1) (1, 2) (0, 2) (0, 4) (2, 4) (2, 3) (1, 3) (1, 4) (3, 4) (0, 3) 
(0, 1) (1, 2) (0, 2) (0, 4) (2, 4) (2, 3) (3, 4) (1, 4) (1, 3) (0, 3) 
(0, 1) (1, 2) (0, 2) (0, 4) (3, 4) (1, 3) (1, 4) (2, 4) (2, 3) (0, 3) 
(0, 1) (1, 2) (0, 2) (0, 4) (3, 4) (2, 3) (2, 4) (1, 4) (1, 3) (0, 3) 
(0, 1) (1, 2) (2, 3) (0, 3) (0, 2) (2, 4) (1, 4) (1, 3) (3, 4) (0, 4) 
(0, 1) (1, 2) (2, 3) (0, 3) (0, 2) (2, 4) (3, 4) (1, 3) (1, 4) (0, 4) 
(0, 1) (1, 2) (2, 3) (0, 3) (0, 4) (1, 4) (1, 3) (3, 4) (2, 4) (0, 2) 
(0, 1) (1, 2) (2, 3) (0, 3) (0, 4) (3, 4) (1, 3) (1, 4) (2, 4) (0, 2) 
(0, 1) (1, 2) (2, 3) (1, 3) (1, 4) (0, 4) (0, 2) (2, 4) (3, 4) (0, 3) 
(0, 1) (1, 2) (2, 3) (1, 3) (1, 4) (0, 4) (0, 3) (3, 4) (2, 4) (0, 2) 
(0, 1) (1, 2) (2, 3) (1, 3) (1, 4) (2, 4) (0, 2) (0, 3) (3, 4) (0, 4) 
(0, 1) (1, 2) (2, 3) (1, 3) (1, 4) (2, 4) (0, 2) (0, 4) (3, 4) (0, 3) 
(0, 1) (1, 2) (2, 3) (1, 3) (1, 4) (3, 4) (0, 3) (0, 2) (2, 4) (0, 4) 
(0, 1) (1, 2) (2, 3) (1, 3) (1, 4) (3, 4) (0, 3) (0, 4) (2, 4) (0, 2) 
(0, 1) (1, 2) (2, 3) (3, 4) (0, 4) (0, 2) (2, 4) (1, 4) (1, 3) (0, 3) 
(0, 1) (1, 2) (2, 3) (3, 4) (0, 4) (0, 3) (1, 3) (1, 4) (2, 4) (0, 2) 
(0, 1) (1, 2) (2, 3) (3, 4) (1, 4) (1, 3) (0, 3) (0, 2) (2, 4) (0, 4) 
(0, 1) (1, 2) (2, 3) (3, 4) (1, 4) (1, 3) (0, 3) (0, 4) (2, 4) (0, 2) 
(0, 1) (1, 2) (2, 3) (3, 4) (2, 4) (0, 2) (0, 3) (1, 3) (1, 4) (0, 4) 
(0, 1) (1, 2) (2, 3) (3, 4) (2, 4) (0, 2) (0, 4) (1, 4) (1, 3) (0, 3) 
(0, 1) (1, 2) (2, 4) (0, 4) (0, 2) (2, 3) (1, 3) (1, 4) (3, 4) (0, 3) 
(0, 1) (1, 2) (2, 4) (0, 4) (0, 2) (2, 3) (3, 4) (1, 4) (1, 3) (0, 3) 
(0, 1) (1, 2) (2, 4) (0, 4) (0, 3) (1, 3) (1, 4) (3, 4) (2, 3) (0, 2) 
(0, 1) (1, 2) (2, 4) (0, 4) (0, 3) (3, 4) (1, 4) (1, 3) (2, 3) (0, 2) 
(0, 1) (1, 2) (2, 4) (1, 4) (1, 3) (0, 3) (0, 2) (2, 3) (3, 4) (0, 4) 
(0, 1) (1, 2) (2, 4) (1, 4) (1, 3) (0, 3) (0, 4) (3, 4) (2, 3) (0, 2) 
(0, 1) (1, 2) (2, 4) (1, 4) (1, 3) (2, 3) (0, 2) (0, 3) (3, 4) (0, 4) 
(0, 1) (1, 2) (2, 4) (1, 4) (1, 3) (2, 3) (0, 2) (0, 4) (3, 4) (0, 3) 
(0, 1) (1, 2) (2, 4) (1, 4) (1, 3) (3, 4) (0, 4) (0, 2) (2, 3) (0, 3) 
(0, 1) (1, 2) (2, 4) (1, 4) (1, 3) (3, 4) (0, 4) (0, 3) (2, 3) (0, 2) 
(0, 1) (1, 2) (2, 4) (3, 4) (0, 3) (0, 2) (2, 3) (1, 3) (1, 4) (0, 4) 
(0, 1) (1, 2) (2, 4) (3, 4) (0, 3) (0, 4) (1, 4) (1, 3) (2, 3) (0, 2) 
(0, 1) (1, 2) (2, 4) (3, 4) (1, 3) (1, 4) (0, 4) (0, 2) (2, 3) (0, 3) 
(0, 1) (1, 2) (2, 4) (3, 4) (1, 3) (1, 4) (0, 4) (0, 3) (2, 3) (0, 2) 
(0, 1) (1, 2) (2, 4) (3, 4) (2, 3) (0, 2) (0, 3) (1, 3) (1, 4) (0, 4) 
(0, 1) (1, 2) (2, 4) (3, 4) (2, 3) (0, 2) (0, 4) (1, 4) (1, 3) (0, 3) 
(0, 1) (1, 3) (0, 3) (0, 2) (1, 2) (1, 4) (2, 4) (2, 3) (3, 4) (0, 4) 
(0, 1) (1, 3) (0, 3) (0, 2) (1, 2) (1, 4) (3, 4) (2, 3) (2, 4) (0, 4) 
(0, 1) (1, 3) (0, 3) (0, 2) (2, 3) (3, 4) (1, 4) (1, 2) (2, 4) (0, 4) 
(0, 1) (1, 3) (0, 3) (0, 2) (2, 3) (3, 4) (2, 4) (1, 2) (1, 4) (0, 4) 
(0, 1) (1, 3) (0, 3) (0, 2) (2, 4) (1, 4) (1, 2) (2, 3) (3, 4) (0, 4) 
(0, 1) (1, 3) (0, 3) (0, 2) (2, 4) (3, 4) (2, 3) (1, 2) (1, 4) (0, 4) 
(0, 1) (1, 3) (0, 3) (0, 4) (1, 4) (1, 2) (2, 3) (3, 4) (2, 4) (0, 2) 
(0, 1) (1, 3) (0, 3) (0, 4) (1, 4) (1, 2) (2, 4) (3, 4) (2, 3) (0, 2) 
(0, 1) (1, 3) (0, 3) (0, 4) (2, 4) (1, 2) (1, 4) (3, 4) (2, 3) (0, 2) 
(0, 1) (1, 3) (0, 3) (0, 4) (2, 4) (2, 3) (3, 4) (1, 4) (1, 2) (0, 2) 
(0, 1) (1, 3) (0, 3) (0, 4) (3, 4) (2, 3) (1, 2) (1, 4) (2, 4) (0, 2) 
(0, 1) (1, 3) (0, 3) (0, 4) (3, 4) (2, 3) (2, 4) (1, 4) (1, 2) (0, 2) 
(0, 1) (1, 3) (2, 3) (0, 2) (0, 3) (3, 4) (1, 4) (1, 2) (2, 4) (0, 4) 
(0, 1) (1, 3) (2, 3) (0, 2) (0, 3) (3, 4) (2, 4) (1, 2) (1, 4) (0, 4) 
(0, 1) (1, 3) (2, 3) (0, 2) (0, 4) (1, 4) (1, 2) (2, 4) (3, 4) (0, 3) 
(0, 1) (1, 3) (2, 3) (0, 2) (0, 4) (2, 4) (1, 2) (1, 4) (3, 4) (0, 3) 
(0, 1) (1, 3) (2, 3) (1, 2) (1, 4) (0, 4) (0, 2) (2, 4) (3, 4) (0, 3) 
(0, 1) (1, 3) (2, 3) (1, 2) (1, 4) (0, 4) (0, 3) (3, 4) (2, 4) (0, 2) 
(0, 1) (1, 3) (2, 3) (1, 2) (1, 4) (2, 4) (0, 2) (0, 3) (3, 4) (0, 4) 
(0, 1) (1, 3) (2, 3) (1, 2) (1, 4) (2, 4) (0, 2) (0, 4) (3, 4) (0, 3) 
(0, 1) (1, 3) (2, 3) (1, 2) (1, 4) (3, 4) (0, 3) (0, 2) (2, 4) (0, 4) 
(0, 1) (1, 3) (2, 3) (1, 2) (1, 4) (3, 4) (0, 3) (0, 4) (2, 4) (0, 2) 
(0, 1) (1, 3) (2, 3) (2, 4) (0, 4) (0, 2) (1, 2) (1, 4) (3, 4) (0, 3) 
(0, 1) (1, 3) (2, 3) (2, 4) (0, 4) (0, 3) (3, 4) (1, 4) (1, 2) (0, 2) 
(0, 1) (1, 3) (2, 3) (2, 4) (1, 4) (1, 2) (0, 2) (0, 3) (3, 4) (0, 4) 
(0, 1) (1, 3) (2, 3) (2, 4) (1, 4) (1, 2) (0, 2) (0, 4) (3, 4) (0, 3) 
(0, 1) (1, 3) (2, 3) (2, 4) (3, 4) (0, 3) (0, 2) (1, 2) (1, 4) (0, 4) 
(0, 1) (1, 3) (2, 3) (2, 4) (3, 4) (0, 3) (0, 4) (1, 4) (1, 2) (0, 2) 
(0, 1) (1, 3) (3, 4) (0, 4) (0, 2) (1, 2) (1, 4) (2, 4) (2, 3) (0, 3) 
(0, 1) (1, 3) (3, 4) (0, 4) (0, 2) (2, 4) (1, 4) (1, 2) (2, 3) (0, 3) 
(0, 1) (1, 3) (3, 4) (0, 4) (0, 3) (2, 3) (1, 2) (1, 4) (2, 4) (0, 2) 
(0, 1) (1, 3) (3, 4) (0, 4) (0, 3) (2, 3) (2, 4) (1, 4) (1, 2) (0, 2) 
(0, 1) (1, 3) (3, 4) (1, 4) (1, 2) (0, 2) (0, 3) (2, 3) (2, 4) (0, 4) 
(0, 1) (1, 3) (3, 4) (1, 4) (1, 2) (0, 2) (0, 4) (2, 4) (2, 3) (0, 3) 
(0, 1) (1, 3) (3, 4) (1, 4) (1, 2) (2, 3) (0, 3) (0, 2) (2, 4) (0, 4) 
(0, 1) (1, 3) (3, 4) (1, 4) (1, 2) (2, 3) (0, 3) (0, 4) (2, 4) (0, 2) 
(0, 1) (1, 3) (3, 4) (1, 4) (1, 2) (2, 4) (0, 4) (0, 2) (2, 3) (0, 3) 
(0, 1) (1, 3) (3, 4) (1, 4) (1, 2) (2, 4) (0, 4) (0, 3) (2, 3) (0, 2) 
(0, 1) (1, 3) (3, 4) (2, 4) (0, 2) (0, 3) (2, 3) (1, 2) (1, 4) (0, 4) 
(0, 1) (1, 3) (3, 4) (2, 4) (0, 2) (0, 4) (1, 4) (1, 2) (2, 3) (0, 3) 
(0, 1) (1, 3) (3, 4) (2, 4) (1, 2) (1, 4) (0, 4) (0, 2) (2, 3) (0, 3) 
(0, 1) (1, 3) (3, 4) (2, 4) (1, 2) (1, 4) (0, 4) (0, 3) (2, 3) (0, 2) 
(0, 1) (1, 3) (3, 4) (2, 4) (2, 3) (0, 3) (0, 2) (1, 2) (1, 4) (0, 4) 
(0, 1) (1, 3) (3, 4) (2, 4) (2, 3) (0, 3) (0, 4) (1, 4) (1, 2) (0, 2) 
(0, 1) (1, 4) (0, 4) (0, 2) (1, 2) (1, 3) (2, 3) (2, 4) (3, 4) (0, 3) 
(0, 1) (1, 4) (0, 4) (0, 2) (1, 2) (1, 3) (3, 4) (2, 4) (2, 3) (0, 3) 
(0, 1) (1, 4) (0, 4) (0, 2) (2, 3) (1, 3) (1, 2) (2, 4) (3, 4) (0, 3) 
(0, 1) (1, 4) (0, 4) (0, 2) (2, 3) (3, 4) (2, 4) (1, 2) (1, 3) (0, 3) 
(0, 1) (1, 4) (0, 4) (0, 2) (2, 4) (3, 4) (1, 3) (1, 2) (2, 3) (0, 3) 
(0, 1) (1, 4) (0, 4) (0, 2) (2, 4) (3, 4) (2, 3) (1, 2) (1, 3) (0, 3) 
(0, 1) (1, 4) (0, 4) (0, 3) (1, 3) (1, 2) (2, 3) (3, 4) (2, 4) (0, 2) 
(0, 1) (1, 4) (0, 4) (0, 3) (1, 3) (1, 2) (2, 4) (3, 4) (2, 3) (0, 2) 
(0, 1) (1, 4) (0, 4) (0, 3) (2, 3) (1, 2) (1, 3) (3, 4) (2, 4) (0, 2) 
(0, 1) (1, 4) (0, 4) (0, 3) (2, 3) (2, 4) (3, 4) (1, 3) (1, 2) (0, 2) 
(0, 1) (1, 4) (0, 4) (0, 3) (3, 4) (2, 4) (1, 2) (1, 3) (2, 3) (0, 2) 
(0, 1) (1, 4) (0, 4) (0, 3) (3, 4) (2, 4) (2, 3) (1, 3) (1, 2) (0, 2) 
(0, 1) (1, 4) (2, 4) (0, 2) (0, 3) (1, 3) (1, 2) (2, 3) (3, 4) (0, 4) 
(0, 1) (1, 4) (2, 4) (0, 2) (0, 3) (2, 3) (1, 2) (1, 3) (3, 4) (0, 4) 
(0, 1) (1, 4) (2, 4) (0, 2) (0, 4) (3, 4) (1, 3) (1, 2) (2, 3) (0, 3) 
(0, 1) (1, 4) (2, 4) (0, 2) (0, 4) (3, 4) (2, 3) (1, 2) (1, 3) (0, 3) 
(0, 1) (1, 4) (2, 4) (1, 2) (1, 3) (0, 3) (0, 2) (2, 3) (3, 4) (0, 4) 
(0, 1) (1, 4) (2, 4) (1, 2) (1, 3) (0, 3) (0, 4) (3, 4) (2, 3) (0, 2) 
(0, 1) (1, 4) (2, 4) (1, 2) (1, 3) (2, 3) (0, 2) (0, 3) (3, 4) (0, 4) 
(0, 1) (1, 4) (2, 4) (1, 2) (1, 3) (2, 3) (0, 2) (0, 4) (3, 4) (0, 3) 
(0, 1) (1, 4) (2, 4) (1, 2) (1, 3) (3, 4) (0, 4) (0, 2) (2, 3) (0, 3) 
(0, 1) (1, 4) (2, 4) (1, 2) (1, 3) (3, 4) (0, 4) (0, 3) (2, 3) (0, 2) 
(0, 1) (1, 4) (2, 4) (2, 3) (0, 3) (0, 2) (1, 2) (1, 3) (3, 4) (0, 4) 
(0, 1) (1, 4) (2, 4) (2, 3) (0, 3) (0, 4) (3, 4) (1, 3) (1, 2) (0, 2) 
(0, 1) (1, 4) (2, 4) (2, 3) (1, 3) (1, 2) (0, 2) (0, 3) (3, 4) (0, 4) 
(0, 1) (1, 4) (2, 4) (2, 3) (1, 3) (1, 2) (0, 2) (0, 4) (3, 4) (0, 3) 
(0, 1) (1, 4) (2, 4) (2, 3) (3, 4) (0, 4) (0, 2) (1, 2) (1, 3) (0, 3) 
(0, 1) (1, 4) (2, 4) (2, 3) (3, 4) (0, 4) (0, 3) (1, 3) (1, 2) (0, 2) 
(0, 1) (1, 4) (3, 4) (0, 3) (0, 2) (1, 2) (1, 3) (2, 3) (2, 4) (0, 4) 
(0, 1) (1, 4) (3, 4) (0, 3) (0, 2) (2, 3) (1, 3) (1, 2) (2, 4) (0, 4) 
(0, 1) (1, 4) (3, 4) (0, 3) (0, 4) (2, 4) (1, 2) (1, 3) (2, 3) (0, 2) 
(0, 1) (1, 4) (3, 4) (0, 3) (0, 4) (2, 4) (2, 3) (1, 3) (1, 2) (0, 2) 
(0, 1) (1, 4) (3, 4) (1, 3) (1, 2) (0, 2) (0, 3) (2, 3) (2, 4) (0, 4) 
(0, 1) (1, 4) (3, 4) (1, 3) (1, 2) (0, 2) (0, 4) (2, 4) (2, 3) (0, 3) 
(0, 1) (1, 4) (3, 4) (1, 3) (1, 2) (2, 3) (0, 3) (0, 2) (2, 4) (0, 4) 
(0, 1) (1, 4) (3, 4) (1, 3) (1, 2) (2, 3) (0, 3) (0, 4) (2, 4) (0, 2) 
(0, 1) (1, 4) (3, 4) (1, 3) (1, 2) (2, 4) (0, 4) (0, 2) (2, 3) (0, 3) 
(0, 1) (1, 4) (3, 4) (1, 3) (1, 2) (2, 4) (0, 4) (0, 3) (2, 3) (0, 2) 
(0, 1) (1, 4) (3, 4) (2, 3) (0, 2) (0, 3) (1, 3) (1, 2) (2, 4) (0, 4) 
(0, 1) (1, 4) (3, 4) (2, 3) (0, 2) (0, 4) (2, 4) (1, 2) (1, 3) (0, 3) 
(0, 1) (1, 4) (3, 4) (2, 3) (1, 2) (1, 3) (0, 3) (0, 2) (2, 4) (0, 4) 
(0, 1) (1, 4) (3, 4) (2, 3) (1, 2) (1, 3) (0, 3) (0, 4) (2, 4) (0, 2) 
(0, 1) (1, 4) (3, 4) (2, 3) (2, 4) (0, 4) (0, 2) (1, 2) (1, 3) (0, 3) 
(0, 1) (1, 4) (3, 4) (2, 3) (2, 4) (0, 4) (0, 3) (1, 3) (1, 2) (0, 2)