Sign in to watch this lesson
Advanced - Graphs Ā· 4:16
Euler Paths & Circuits (Hierholzer)
An Euler path uses every edge of a graph exactly once, and an Euler circuit also ends where it started. In an undirected graph a circuit exists when all degrees are even and a path when exactly zero or two are odd, with all edges connected (directed: in-degree equals out-degree, with one extra out at the start and one extra in at the end). Hierholzer's algorithm finds one in O(m) with a stack: follow unused edges, pop a vertex into the answer only when it is stuck, and read the answer backwards.
You will learn
- Model a puzzle such as a set of dominoes as a multigraph whose Euler path is the answer
- State the degree and connectivity conditions for Euler paths and circuits, undirected and directed
- Run Hierholzer's stack algorithm by hand, including a walk that closes early and a spliced sub-tour
- Implement it in O(m) with a per-vertex pointer and used[] per edge, starting at the right vertex and checking that all edges were used