Graph AlgosGraph Algorithms

Eulerian Path (Hierholzer's algorithm)

A walk that uses every edge exactly once; exists under simple degree conditions and is built greedily by Hierholzer's algorithm in O(E).

Learn Eulerian Path →
A2B2C4D2E3F1
Stack (top → bottom)
empty
Path (built backwards)
empty
1/18Degrees: A=2, B=2, C=4, D=2, E=3, F=1. Odd-degree vertices: E, F. An Euler path needs 0 or 2 of them — every pass through a vertex uses two edges.
Top of stackOn the stackPopped into the pathEdge just traversedUsed edgeFinal Euler path
PseudocodeLearn Eulerian Path →
1odd = vertices with odd degree; if len(odd) not in {0, 2}: no Euler path
2start = odd[0] if odd else any vertex with an edge
3stack = [start]; path = []
4while stack not empty:
5  u = stack.top()
6  if u has an unused edge (u, v): mark it used; stack.push(v)
7  else: path.append(stack.pop())   # dead end: u is finished
8return reversed(path)
Variables
odd2
Complexity
best O(V + E)
avg O(V + E)
worst O(V + E)
space O(V + E)
Speed