Eulerian Tour

An Eulerian tour is any path in a graph that uses every edge exactly once. An Eulerian tour that starts and ends on the same vertex is called an Eulerian circuit. If and only if a graph is connected and has either all verticies of even degree or exactly two with an odd degree, then it has an Eulerian tour. In the first case, the graph has an Eulerian circuit; in the latter case, the graph does not have an Eulerian curcuit, and the tour starts on one of the odd degree vertex and ends on the other.

There is a relatively simple algorithm for finding an Eulerian tour in a graph: pick a starting vertex and recurse on it. At each step:

  • If the vertex has no neighbors, then append the vertex to the circuit.
  • If the vertex has a neighbor, then make a list of the neighbors and process them until the vertex has no more neighbors.
  • To process a vertex, delete the edge between the current vertex and its neighbor, recurse on the neighbor, and append the current vertex to the circuit.

Here's an $O(E+V)$ implementation in C++; the assumed input format is the number of edges and then an edge list:

E
v1,1 v1,2
v2,1 v2,2

vE,1 vE,2

This is a simple implementation with an adjacency list.

#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define MAXE 10000
#define INFTY 1000000000
using namespace std;
 
ifstream fin ("euler.in");
ofstream fout ("euler.out");
 
vector<int> adjl[MAXE];
set<int> vs;
int f, cpos = 0, circuit[MAXE], fv = INFTY, lv = 0;
 
void euler (int n) {
    // If there are no neighbors, append node to circuit
    if (adjl [n].size() == 0)
        circuit [cpos++] = n;
    else {
        // Process all neighbors
        while (adjl [n].size () > 0) {
            int edg = adjl [n].back ();
            adjl [n].pop_back ();
            for (int i = 0; i < adjl [edg].size (); i++)
                if (adjl [edg][i] == n) {
                    adjl [edg].erase (adjl [edg].begin () + i);
                    break;
                }
            euler (edg);
        }
        circuit [cpos++] = n;
    }
    return;
}
 
main () {
    fin >> f;
    for (int i = 0; i < f; i++) {
        int v1, v2;
        fin >> v1 >> v2;
        fv = min (fv, min (v2, v1));
        lv = max (lv, max (v2, v1));
        adjl [v1].push_back (v2);
        adjl [v2].push_back (v1);
    }
    int j = 1;
    // Find a vertex of odd degree to start with, if one exists
    for (j = fv1; j <= lv1; j++)
        if (adjl [j].size () % 2 == 1) 
            break;
    j = (j >= lv - 1) ? fv : j;
    euler (j);
    // The circuit was constructed in reverse order, so print it out backwards
    // This is in case the problem requires that you start at node j (you can
    // print it out "normally" otherwise)
    for (int i = cpos - 1; i >= 0; i--)
        fout << circuit [i] << endl;
    exit(0);
}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License