Eulerian path

An Eulerian path uses every edge of a graph exactly once; vertices may repeat. Hierholzer's algorithm finds one in O(n + m) or shows there is none. If every vertex must be visited once instead, that is a Hamiltonian path, a much harder problem, solved for small graphs with bitmask DP.

Explanation

Here is a house, a square with a roof. Starting from point 3, a pen can draw it without lifting or drawing a line twice: 3, 2, 1, 4, 3, 5, 4.

A house shape of five points, a square 1, 2, 3, 4 with a roof point 5, drawn line by line in red without lifting the pen: 3, 2, 1, 4, 3, 5, 4; points 3 and 4, which have three lines each, are ringed.

Fig. 1. Red lines are drawn. The ringed points have 3 lines each.

From point 1, taking the line to the lowest-numbered point each time, the pen goes 1, 2, 3, 4, 1 and is stuck with the roof undrawn.

Each time the pen passes through a point, it uses two lines there, one in and one out. So a point where the drawing neither starts nor ends has an even number of lines. Points 3 and 4 have three each, so the drawing starts at one and ends at the other.

If no point has an odd number of lines, start anywhere and come back. If two points are odd, start at one and end at the other. If more are odd, there is no drawing. (The number of odd points is always even: all the counts add up to twice the number of lines.) All lines must also be in one piece, since the pen can't jump.

In a bigger figure, knowing the start is not enough. Here points 1 and 4 have one line each and the rest are even, so the drawing must go from point 1 to point 4.

Seven points: 1, 2, 3, 4 in a row along the top, and 5, 6, 7 below forming two triangles, 2-5-6 and 3-6-7, joined at point 6; points 1 and 4 at the ends of the top row are ringed in blue as the two points with an odd number of lines.

Fig. 2. The ringed points are the two odd points.

Start at point 1 and keep taking the undrawn line to the lowest-numbered point. The pen goes 1, 2, 3, 4 and is stuck after 3 of the 9 lines: point 4 has no other line, and the two triangles are untouched.

The seven-point figure: the route 1, 2, 3, 4 is drawn thick in red along the top, the six lines of the triangles 2, 5, 6 and 3, 6, 7 below it are thin grey, and a red cross beside point 4 shows the pen is stuck there.

Fig. 3. Red: the route taken. The pen is stuck at point 4.

The start was right; the choice at point 3 was wrong, and a big figure gives no way to tell which choice is right.

So the question is what to do with the lines that are left. Keep the drawing and look back along it for a point that still has undrawn lines: point 3 is the last one. Every point now has an even number of undrawn lines, because the red route used one line at points 1 and 4 and two at each point it passed.

Seven points: 1, 2, 3, 4 in a row along the top, with the red route 1–2–3–4 drawn thick, and 5, 6, 7 below forming two triangles of thin grey lines, 2–5–6 and 3–6–7. Each point has a tag with its number of undrawn lines: 1 has 0, 2 has 2, 3 has 2, 4 has 0, 5 has 2, 6 has 4, 7 has 2.

Fig. 4. The tags count the undrawn lines at each point.

So a pen that starts at point 3 on undrawn lines can leave every other point it enters, and it can only get stuck back at point 3. It goes 3, 6, 2, 5, 6, 7, 3: the blue detour. Put the detour into the drawing at point 3: 1, 2, 3, then the detour, then the line to 4. That is all 9 lines, each once.

Seven points: the red route runs along the top row from point 1 through 2 and 3 to 4; blue arrows show the detour from point 3 to 6, 2, 5, 6, 7 and back to 3.

Fig. 5. Red: the first route. Blue: the detour from point 3.

If a detour leaves lines undrawn, do the same again from the last point that still has some.

Going back to the last point with something left to try is how a depth-first search walks back. Keep the drawing as a stack of points. Draw a line and push its end (extend the walk). When the top point has no undrawn line, append it to a list path and pop it (step back). When point 4 is popped, point 3 is on top again, the last point with undrawn lines, and the detour is pushed on top of it. The points come off the stack in reverse order of the drawing, with the detour already in place.

This is Hierholzer's algorithm. From here on, the points are vertices, the lines are edges, an undrawn line is an unused edge, and the stack holds the walk.

Step-by-step run of Hierholzer's algorithm on the 7-point figure from point 1: each step pushes a vertex along an unused edge or pops a stuck vertex onto the path row below the graph, used edges turning red, then blue for the detour 3, 6, 2, 5, 6, 7, 3, until path holds 4 3 7 6 5 2 6 3 2 1.

Points 1 and 4 are odd, so the walk starts at point 1: the stack, the first row under the graph, holds 1. The top of the stack is outlined in blue on the graph and in the row. The second row is path, still empty.

1/20

Fig. 6. Step through the algorithm with the buttons or the arrow keys. Red and blue edges are used; blue is the detour. The top of the stack is the current vertex.

Reversed, path is 1, 2, 3, 6, 2, 5, 6, 7, 3, 4: all 9 edges, with the detour found without guessing.

Implementation

An Eulerian path that ends where it started is an Eulerian cycle. The number of edges at a vertex is its degree. An undirected graph has an Eulerian path when its edges lie in one connected component (vertices with no edges don't matter) and 0 or 2 vertices have odd degree; with 0 it is a cycle.

Each edge gets a number id, its place in the input. The adjacency list adj[v] holds pairs (u, id), and an undirected edge is in both lists with the same id, so used[id] = true marks it from either end.

The pointer ptr[v] is the index of the first edge in adj[v] that may be unused; it only moves forward. Without it, each visit to v would rescan the used edges: with 2 vertices and 10^5 parallel edges, about m^2 / 2 steps. On Fig. 4, when vertex 3 is back on top after 4 is popped, ptr[3] moves past the used edge 3–4 and lands on 3–6.

  1. Check the degrees: more than 2 odd vertices means no path. Start s at an odd vertex, or at any vertex with an edge.

  2. Initialise: the stack st = {s}, every ptr[v] = 0, every edge unused.

  3. Extend the walk: for the top v, move ptr[v] past used edges; if an unused edge (u, id) is left, mark it used and push u.

  4. Step back: otherwise append v to path and pop it.

  5. Stop when st is empty.

  6. Check every edge is used: path must hold m + 1 vertices (on Fig. 4, 10 = 9 + 1). Then reverse and print it.

The last check tests connectivity: edges in another component are never reached, so path comes out shorter. On two separate triangles, a program without this check prints 1 2 3 1.

The input is n and m, then m edges a b, with vertices from 1 to n. The program prints an Eulerian path, or -1. For Fig. 4 the input is:

7 9
1 2
2 3
3 4
2 5
2 6
3 6
3 7
5 6
6 7
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> adj(n + 1);   // adj[v] holds pairs (u, id)
    vector<int> deg(n + 1, 0);
    for (int id = 0; id < m; id++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back({b, id});
        adj[b].push_back({a, id});
        deg[a]++;
        deg[b]++;
    }

    // check the degrees
    int odd = 0;
    for (int v = 1; v <= n; v++)
        if (deg[v] % 2 == 1) odd++;
    if (odd > 2) {
        cout << -1 << '\n';
        return 0;
    }
    int s = 1;
    while (s < n && deg[s] == 0) s++;      // a vertex with an edge
    for (int v = 1; v <= n; v++)
        if (deg[v] % 2 == 1) { s = v; break; }   // an odd vertex, if there is one

    // initialise
    vector<int> ptr(n + 1, 0);
    vector<bool> used(m, false);
    vector<int> st = {s}, path;

    while (!st.empty()) {   // stop: when the stack is empty
        int v = st.back();
        while (ptr[v] < (int)adj[v].size() && used[adj[v][ptr[v]].second]) ptr[v]++;
        if (ptr[v] < (int)adj[v].size()) {
            // extend the walk
            auto [u, id] = adj[v][ptr[v]];
            used[id] = true;
            st.push_back(u);
        } else {
            // step back
            path.push_back(v);
            st.pop_back();
        }
    }

    // check every edge is used
    if ((int)path.size() != m + 1) {
        cout << -1 << '\n';
        return 0;
    }
    reverse(path.begin(), path.end());
    for (int i = 0; i < (int)path.size(); i++) cout << path[i] << (i + 1 < (int)path.size() ? ' ' : '\n');
}

Loops and multiple edges need no special code: a loop a a goes into adj[a] twice with one id, and parallel edges get different ids.

Each edge is pushed once and ptr[v] passes each entry of adj[v] once, so the time and memory are O(n + m).

Directed graphs

A walk enters a vertex on one edge and leaves on another. So a directed graph has an Eulerian cycle when every vertex has as many edges in as out, and a path when one vertex has one more out (the start), one has one more in (the end) and the rest are balanced. The edges must be in one component ignoring directions, which the m + 1 check still tests.

Each edge goes only into adj of its start, and the degree check changes:

    vector<int> out(n + 1, 0), in(n + 1, 0);
    for (int id = 0; id < m; id++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back({b, id});
        out[a]++;
        in[b]++;
    }

    // check the degrees
    int starts = 0, ends = 0, s = 1;
    while (s < n && out[s] == 0) s++;   // if all are balanced, any vertex with an edge out
    for (int v = 1; v <= n; v++) {
        if (out[v] == in[v] + 1) { starts++; s = v; }
        else if (in[v] == out[v] + 1) ends++;
        else if (in[v] != out[v]) starts = 2;      // any other difference: no path
    }
    if (starts > 1 || ends > 1) {
        cout << -1 << '\n';
        return 0;
    }

Correctness proof

The Explanation showed that the condition on odd degrees is needed. With all edges in one component, it is also enough.

Each push uses one unused edge, so no edge is used twice. Let be the other odd vertex (t = s if there is none). The first walk from can leave every vertex it enters except , so it gets stuck at . As at vertex 3 in Fig. 6, every vertex then has an even number of unused edges.

The invariant is that whenever the stack pops back to a vertex with unused edges, every vertex has an even number of them. A walk from then gets stuck only at , so it is a closed detour, and the counts stay even.

Consecutive vertices in path are joined by an edge. When is popped, the vertex below it on the stack is the one was pushed from, along an edge. The next vertex appended is that same vertex: either it has no unused edge and is popped at once, or a detour leaves from it, gets stuck back at it, and that copy is appended. So path read backwards is a walk from that uses each edge at most once.

Suppose some edge stays unused. The edges are in one component, so some unused edge touches a vertex of the walk. But was popped only when it had no unused edge left. So every edge is used.

Common mistakes

  • Marking vertices instead of edges, the habit from DFS. On the house, such a search from vertex 3 reaches 3, 2, 1, 4, 5 and stops, but vertex 3 must be passed twice. Mark edges by id.

  • Appending a vertex to path when it is pushed. On Fig. 4 the push order is 1 2 3 4 6 2 5 6 7 3, and there is no edge 4–6. Append it at the step back, then reverse.

  • Starting at vertex 1 when every degree is even. With 4 vertices and the triangle 2–3–4, the walk from vertex 1 uses no edge and the program prints -1 instead of 2 3 4 2. Start at a vertex with an edge.

Similar algorithms

Depth-first search records a vertex when it first reaches it; Hierholzer's algorithm appends a vertex to path when it steps back.

Practice

In 2976, a point with no lines also means -1.

Was this page helpful?