Pattern Reference
Euler Path / Circuit
"Hierholzer's algorithm for Eulerian path. Chinese postman problem, de Bruijn sequence. Hierholzer, Fleury."
Loading...
Deep Dive Tutorial
Hierholzer's algorithm: start at a valid start node. Follow edges greedily (DFS), marking edges as used. When stuck (no more edges), backtrack and insert current node into the result. This builds the Euler path in reverse — the recursive DFS post-order naturally handles dead-ends before continuing the main path. Key: use adjacency list with efficient edge removal (splice or pointer).
Hierholzer's algorithm for directed graph
// Directed Euler path (Hierholzer's)
function eulerPath(n, edges) {
const adj = Array.from({length: n}, () => []);
const inDeg = new Array(n).fill(0);
const outDeg = new Array(n).fill(0);
for (const [u, v] of edges) {
adj[u].push(v);
outDeg[u]++;
inDeg[v]++;
}
// Find start node: prefer node with outDeg - inDeg = 1, else any node with outDeg > 0
let start = 0;
for (let i = 0; i < n; i++) if (outDeg[i] - inDeg[i] === 1) { start = i; break; }
// Hierholzer's: iterative post-order
const stack = [start], path = [];
while (stack.length) {
const u = stack.at(-1);
if (adj[u].length) {
stack.push(adj[u].pop()); // use next edge
} else {
path.push(stack.pop()); // dead end → add to path
}
}
return path.reverse(); // O(E) total
}Worked Problems
repeat
Euler conditions:
- Undirected circuit: all vertices have even degree
- Undirected path: exactly 2 vertices have odd degree (they are start/end)
- Directed circuit: in-degree = out-degree for every vertex
- Directed path: one vertex has out - in = 1 (start), one has in - out = 1 (end)
Hierholzer's key: When stuck (no outgoing edges), pop current node to the result path, backtrack. Post-order insertion naturally handles "bridge" edges.
Complexity: O(E) with adjacency list + pointer to next unvisited edge.
Applications: Itinerary reconstruction, De Bruijn sequences, word chains (each word's last char = next word's first char).
- Undirected circuit: all vertices have even degree
- Undirected path: exactly 2 vertices have odd degree (they are start/end)
- Directed circuit: in-degree = out-degree for every vertex
- Directed path: one vertex has out - in = 1 (start), one has in - out = 1 (end)
Hierholzer's key: When stuck (no outgoing edges), pop current node to the result path, backtrack. Post-order insertion naturally handles "bridge" edges.
Complexity: O(E) with adjacency list + pointer to next unvisited edge.
Applications: Itinerary reconstruction, De Bruijn sequences, word chains (each word's last char = next word's first char).