V

Algorithm Visualizer

ZHEN
Share on WeiboShare on XGitHub repositoryAuthor website
Learning ToolsAlgorithm Complexity ReferenceAlgorithm Learning Paths
Data StructuresArrayLinked ListStackQueue and DequeBinary Search TreeBinary HeapHash TableGraphTrieDisjoint Set UnionLRU CacheSkip ListSegment TreeB+ TreeBloom FilterFenwick Tree
SortingBubble SortCocktail Shaker SortBitonic SortSelection SortInsertion SortBinary Insertion SortShell SortMerge SortTop-Down Merge SortQuick SortThree-Way Quick SortDual-Pivot Quick SortHeap SortCounting SortRadix SortBucket Sort
Graph AlgorithmsDijkstra's Shortest PathKruskal's Minimum Spanning TreePrim's Minimum Spanning TreeBellman-Ford Shortest PathsTopological SortFloyd-WarshallStrongly Connected Components2-SATMaximum FlowBipartite MatchingLowest Common AncestorEulerian Path
Dynamic ProgrammingEdit Distance0/1 KnapsackUnbounded KnapsackLongest Common SubsequenceLongest Increasing SubsequenceCoin ChangeStone MergingTraveling Salesperson DPTree Dynamic ProgrammingDigit DPRerooting DP
Backtracking and SearchN-QueensSubsetsPermutationsCombination SumMaze Solving with DFSNumber of IslandsWord SearchSudoku SolverA* Search
StringsKMP String MatchingRabin-Karp String MatchingBoyer-Moore String MatchingManacher's Longest Palindromic SubstringSuffix ArrayLCP ArrayAho-Corasick AutomatonZ Function
Math and Number TheorySieve of EratosthenesLinear SieveEuclidean AlgorithmBinary ExponentiationExtended Euclidean AlgorithmChinese Remainder TheoremEuler's Totient FunctionMiller-Rabin Primality TestFast Fourier TransformPollard's Rho Factorization
Computational GeometryConvex HullRotating CalipersClosest Pair of PointsLine Segment IntersectionBentley-Ottmann Sweep Line
SearchingBinary SearchLower and Upper BoundSearch in a Rotated Sorted ArrayBinary Search on the AnswerTernary Search

Eulerian Path

Run Hierholzer stack traversal, consume every edge once, and append vertices while dead ends unwind.

Core idea

Hierholzer's algorithm walks unused edges until it reaches a dead end. Dead-end vertices are appended while the stack unwinds, automatically splicing every discovered cycle into one trail.

Read the visualization

Remaining-degree badges shrink as edges are consumed. The traversal stack records the live walk, and backtracking builds the answer in reverse order.

01234

Load the connected graph and the requirement to use every edge exactly once.

1function eulerPath(n: number, edges: [number, number][]): number[] {
2 const adj = Array.from({ length: n }, () => [] as { v: number; eid: number }[]);
3 edges.forEach(([u, v], i) => { adj[u].push({ v, eid: i }); adj[v].push({ v: u, eid: i }); });
4 const deg = adj.map((a) => a.length);
5 const odd = [...Array(n).keys()].filter((u) => deg[u] % 2 === 1); // verdict: odd-degree vertex 0/2
6 if (odd.length !== 0 && odd.length !== 2) return [];
7 const start = odd.length ? odd[0]: 0; // check odd-degree vertex check from check
8 const used = new Array(edges.length).fill(false);
9 const stack = [start];
10 const path: number[] = [];
11 while (stack.length) {
12 const u = stack[stack.length - 1];
13 const next = adj[u].find((e) => !used[e.eid]);
14 if (next) {
15 used[next.eid] = true; // walk edge: walk edge + walk stack
16 stack.push(next.v);
17 } else {
18 stack.pop(); // back: back stack back path
19 path.push(u);
20 }
21 }
22 return path.reverse(); // done pop order done Eulerian path
23}
stack( empty)
path( empty)
target7 count edge visit each once
1 / 12

Complexity and tradeoffs

Time: O(V+E). Space: O(V+E). Connectivity and odd-degree conditions determine whether an undirected Eulerian trail exists.

Invariant: Every consumed edge appears exactly once in the unfinished stack walk or the reversed output suffix.

Where it fits

Eulerian trails model route inspection, DNA assembly with de Bruijn graphs, and reconstruction from adjacent pairs. Hamiltonian paths instead require visiting vertices once and are much harder.