Eulerian Path/Circuit
Eulerian path visits every edge exactly once; Eulerian circuit starts and ends at the same vertex. Characterized by vertex degrees (0 odd-degree vertices ⇒ circuit; exactly 2 odd-degree vertices ⇒ path). Constructed efficiently using Hierholzer's algorithm.
Visualization
Interactive visualization for Eulerian Path/Circuit
Sample Graph (adjacency):
0: [1,2] | 1: [0,2,3] | 2: [0,1,3] | 3: [1,2]
Interactive visualization with step-by-step execution
Implementation
1function hierholzer(graph: Map<number, number[]>): number[] {
2 const adj = new Map<number, number[]>();
3 for (const [u, neighbors] of graph) {
4 adj.set(u, [...neighbors]);
5 }
6
7 const stack: number[] = [];
8 const path: number[] = [];
9 let curr = Array.from(graph.keys())[0];
10
11 stack.push(curr);
12
13 while (stack.length > 0) {
14 const neighbors = adj.get(curr) || [];
15
16 if (neighbors.length > 0) {
17 const next = neighbors.pop()!;
18 stack.push(next);
19 curr = next;
20 } else {
21 path.push(curr);
22 curr = stack.pop()!;
23 }
24 }
25
26 return path.reverse();
27}Deep Dive
Theoretical Foundation
A connected graph has an Eulerian circuit iff every vertex has even degree; it has an Eulerian path (but not a circuit) iff exactly two vertices have odd degree (start/end). Hierholzer's algorithm builds the tour by walking cycles and splicing them together, removing edges as they are traversed in the residual multigraph.
Complexity
Time
O(E)
O(E)
O(E)
Space
O(E)
Applications
Industry Use
Route inspection / Chinese postman problem
Street sweeping and garbage collection routing
DNA fragment assembly (edge usage models)
Network maintenance visiting each link once
Drawing graphs without lifting pen
Mail delivery and logistics on edge networks
Use Cases
Related Algorithms
Depth-First Search (DFS)
Graph traversal exploring as deep as possible before backtracking. DFS is a fundamental algorithm that uses a stack (either implicitly through recursion or explicitly) to explore graph vertices. It's essential for cycle detection, topological sorting, and pathfinding problems.
Breadth-First Search (BFS)
Level-by-level graph traversal guaranteeing shortest paths in unweighted graphs. BFS uses a queue to explore vertices level by level, making it optimal for finding shortest paths and solving problems that require exploring nearest neighbors first.
Dijkstra's Algorithm
Finds shortest path from source to all vertices in weighted graph with non-negative edges. Uses greedy approach with priority queue.
Floyd-Warshall Algorithm
Floyd-Warshall is an all-pairs shortest path algorithm that finds shortest distances between every pair of vertices in a weighted graph. Unlike Dijkstra (single-source), it computes shortest paths from all vertices to all other vertices simultaneously. The algorithm can handle negative edge weights but not negative cycles. Developed independently by Robert Floyd, Bernard Roy, and Stephen Warshall in the early 1960s.