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.
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.
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": [] }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": [] }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 ] }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 ] }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:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
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.
- Ueber die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren
Carl Hierholzer; Chr Wiener (1873). Historical research paper.