Undirected Euler trail (Hierholzer): Examples & Code

Algorithm Visualizations November 16, 2026 javascript

Published by Dimitris Kougioumtzis · Updated

Consume every undirected edge exactly once using a stack, then reverse the backtracking order. Parallel edges and self-loops are distinct; weights are ignored.

Count incident edge ends, start at an odd vertex when there are two, and use a stack to consume unused incident edges. Reverse the vertices emitted on backtracking to obtain the trail.

Open the 3D visualization

Undirected Euler trail (Hierholzer) example state preview
Preview of the example's final state. Complete values are available in the worked example and interactive timeline.

When to use Undirected Euler trail (Hierholzer)

Route inspection and demonstrations of edge-covering walks in small undirected multigraphs.

Choosing an alternative

Hamiltonian search visits vertices once; Euler trails consume edges once. The directed Hierholzer view uses in-degree and out-degree rather than odd undirected degrees.

Worked example: input and state changes

Example input

0,1,1;1,2,1;2,0,1;0,3,1

These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.

  1. Step 0: Count incident edge ends; each self-loop contributes two to degree.

    State at this checkpoint
    {
      "values": [
        3,
        2,
        2,
        1
      ],
      "active": [],
      "kind": "graph",
      "chosen": [],
      "visited": [],
      "stack": [],
      "reverse": []
    }
  2. Step 3: Consume edge #2: 2 > 0.

    State at this checkpoint
    {
      "values": [
        3,
        2,
        2,
        1
      ],
      "active": [
        2,
        0
      ],
      "kind": "graph",
      "chosen": [
        0,
        1,
        2
      ],
      "visited": [],
      "stack": [
        0,
        1,
        2,
        0
      ],
      "reverse": []
    }
  3. Step 5: No unused incident edge at 3; append it to reverse order.

    State at this checkpoint
    {
      "values": [
        3,
        2,
        2,
        1
      ],
      "active": [
        3
      ],
      "kind": "graph",
      "chosen": [
        0,
        1,
        2,
        3
      ],
      "visited": [
        3
      ],
      "stack": [
        0,
        1,
        2,
        0
      ],
      "reverse": [
        3
      ]
    }
  4. Step 8: No unused incident edge at 1; append it to reverse order.

    State at this checkpoint
    {
      "values": [
        3,
        2,
        2,
        1
      ],
      "active": [
        1
      ],
      "kind": "graph",
      "chosen": [
        0,
        1,
        2,
        3
      ],
      "visited": [
        3,
        0,
        2,
        1
      ],
      "stack": [
        0
      ],
      "reverse": [
        3,
        0,
        2,
        1
      ]
    }
  5. Step 10: Euler trail: 0 > 1 > 2 > 0 > 3.

    State at this checkpoint
    {
      "values": [
        3,
        2,
        2,
        1
      ],
      "active": [],
      "kind": "graph",
      "chosen": [
        0,
        1,
        2,
        3
      ],
      "visited": [
        3,
        0,
        2,
        1
      ],
      "stack": [],
      "reverse": [
        3,
        0,
        2,
        1,
        0
      ],
      "result": 5,
      "path": [
        0,
        1,
        2,
        0,
        3
      ]
    }

Expected final state

Euler trail: 0 > 1 > 2 > 0 > 3.

Complexity and input bounds

Family: Graphs. Time complexity: O(V + E^2).

Implementation detail: This teaching implementation scans the input edge list on each step, so its running time is O(V + E^2). Adjacency lists with cursors reduce the standard construction to O(V + E). Isolated vertices are allowed. Downloads return the output length or -1, and an empty edge set returns [0].

Space complexity: O(V + E) auxiliary space; visualization snapshots use additional space.

Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.

Directed edges as source,target,weight; separated by semicolons. Nodes 0–7, positive weights 1–99. Start node is 0. Edges are undirected; weights ignored.

The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.

Common mistakes and limitations

A self-loop contributes two to degree. Parallel edges have separate identities. Zero or two odd degrees is insufficient when non-isolated edges are disconnected.

Further reading

For background on algorithm analysis and the JavaScript function interface:

Editorial and testing approach · Browse all algorithm guides

Complete JavaScript implementation

javascript
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
// Undirected multigraph, 1..8 vertices, 0..16 edges, endpoints in range; weights ignored. Output capacity at least edges+1. Returns output length, or -1 if no Euler trail exists; an empty edge set returns [0]. Isolated vertices do not prevent a trail. Edge scans take O(V + E^2) time and O(V + E) auxiliary space. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation.
function algorithm(from, to, weight, edges, vertices, output) {
    let degree = Array(256).fill(0); let used = Array(256).fill(0); let stack = Array(256).fill(0); let reversed = Array(256).fill(0);
    let odd = 0; let start = 0; let top = 0; let length = 0; let u = 0; let v = 0; let index = 0;
    for (index = 0; index < edges; index++) { degree[from[index]]++; degree[to[index]]++; }
    for (u = vertices - 1; u >= 0; u--) { if (degree[u] > 0) { start = u; } }
    for (u = vertices - 1; u >= 0; u--) { if (degree[u] % 2 != 0) { odd++; start = u; } }
    if (odd != 0 && odd != 2) { return -1; }
    stack[top++] = start;
    while (top > 0) {
        u = stack[top - 1]; index = 0;
        while (index < edges && (used[index] != 0 || (from[index] != u && to[index] != u))) { index++; }
        if (index < edges) {
            used[index] = 1; v = from[index]; if (from[index] == u) { v = to[index]; } stack[top++] = v;
        } else { reversed[length++] = stack[--top]; }
    }
    if (length != edges + 1) { return -1; }
    for (index = 0; index < length; index++) { output[index] = reversed[length - 1 - index]; }
    return length;
}

Source

The original 1873 paper studies Eulerian traversals. The playground uses its stack-and-backtracking construction on undirected multigraphs, with edge identity preserved for parallel edges and loops.