Overview
Hierholzer's algorithm follows unused edges until a cycle closes, then expands the route from vertices that still have unused edges.
CoreSource checked
Hierholzer's Algorithm
Builds an Eulerian path or circuit by splicing cycles that consume every edge once.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Graph Traversal
- Difficulty
- Intermediate
- Family
- Eulerian Traversal
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 0
- Relationships
- 3
- Code example
- Ready
- Visualization
- Ready
Core Concepts
eulerian pathedge consumptioncycle splicingstack traversal
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(E)
Average
O(E)
Worst
O(E)
Space
O(E)
When to Use
- Use when analyzing graph structure needs eulerian path.
- Use when the input matches the assumptions behind eulerian Traversal.
When Not to Use
- Avoid when the graph is so large that it needs streaming or external-memory handling.
- Avoid when a simpler algorithm gives the required result with less setup.
What It Does
- Builds an Eulerian path or circuit by splicing cycles that consume every edge once
- Uses eulerian path and edge consumption to guide the work.
- Produces visited nodes.
Use Cases
- Analyzing graph structure
- Finding connectivity patterns
- Preparing graph-derived orderings
Inputs
- Graph
- Start nodes or query nodes
- Traversal state
Outputs
- Visited nodes
- Derived graph relationships
Pseudocode
- 1.Prepare the inputs and state needed for Hierholzer's Algorithm.
- 2.Apply the eulerian path step while the stopping condition has not been met.
- 3.Update intermediate state and discard invalid candidates.
- 4.Return visited nodes.
Canonical Example
- Input
- Hierholzer's Algorithm input with a small representative case
- Output
- Visited nodes
- Explanation
- Hierholzer's Algorithm applies eulerian path to produce visited nodes.
Implementation Notes
- Keep visitation state and edge classification state separate.
- Keep the eulerian path step separate enough to test independently.
Common Pitfalls
- Mixing directed and undirected edge assumptions can produce incorrect graph relationships.
- Forgetting to check edge cases can make Hierholzer's Algorithm look correct on only ideal inputs.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationHighlight active nodes, discovered edges, and the graph structure produced by each step.
Step 1 of 4: Prepare the inputs and state needed for Hierholzer's Algorithm.
graph-traversal-mechanismNotes
Hierholzer's Algorithm should be used with the assumptions and tradeoffs of eulerian Traversal in mind.
Sources (2)
What each reference supports for this entry.
Introduction to Algorithms (CLRS)
BookTextbook support for Hierholzer's Algorithm's standard algorithm design, invariants, and complexity analysis.
Open sourceThe Algorithm Design Manual
BookAlgorithm catalog support for Hierholzer's Algorithm's problem context, known alternatives, and practical selection tradeoffs.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Used byFleury's Algorithm
Graph Traversal · Core
Fleury's Algorithm uses Hierholzer's Algorithm as a subroutine, representation, or supporting idea while walking unused edges while avoiding bridges unless no alternative remains.
Compare with thisRelationships
View full relationship pageDepends onConnected Components
Euler tour construction assumes the relevant graph component is connected after ignoring isolated vertices.
Related Algorithms
Tags
GraphEulerian PathTraversalCircular Buffer