← Advanced Graphs · guided lesson
Advanced Graphs: Euler Paths, Bridges & SCCs
the story
Euler paths and Hierholzer's algorithm
Every tool here exists because something was too slow or broke without it. Here is what.
Euler's Königsberg paper (1736 — see the Graphs chapter) gave the degree rule for walking every bridge once, but did not prove the rule was enough. Carl Hierholzer, a lecturer in Karlsruhe, found the proof and its method — walk until stuck, then splice in a loop from any vertex with unused edges — and presented it to fellow mathematicians. He died in September 1871 without writing it down. Christian Wiener reconstructed it from memory, with Jacob Lüroth's help, and published it in Mathematische Annalen in 1873. In 1883 Fleury published a slower rule: never cross a bridge of the unused edges unless you must. In 2001 Pevzner, Tang and Waterman's EULER assembler made Euler paths in de Bruijn graphs practical for DNA, sidestepping the NP-complete Hamiltonian model.
the problem it solved
Proving exactly when a walk that uses every edge once exists — and building one in time proportional to the number of edges.
why it matters: without it
"Use every link exactly once" would be a search over orders — hopeless beyond a few dozen edges — and DNA assembly would be stuck with an NP-complete model.
sources: Hierholzer — Ueber die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren (Mathematische Annalen 6, 1873) ↗ · Sachs, Stiebitz & Wilson — An historical note: Euler's Königsberg letters (J. Graph Theory, 1988) ↗ · Wikipedia — Eulerian path (Euler's unproved 'if' direction; Fleury's 1883 algorithm) ↗ · Pevzner, Tang & Waterman — An Eulerian path approach to DNA fragment assembly (PNAS, 2001) ↗ · Compeau, Pevzner & Tesler — How to apply de Bruijn graphs to genome assembly (Nature Biotechnology, 2011) ↗
also in this chapter: Bridges and articulation points (low-link DFS) · Strongly connected components (Kosaraju, Tarjan) · Ratios as a weighted graph (and weighted union-find) · BFS over a derived graph (choose the vertices)
the idea
The idea in 30 seconds
BFS, DFS, shortest paths, MST and topological sort answer reach, distance, cost and order. This chapter asks new questions with the same DFS/BFS skeleton.
Use every edge once? Euler path (Hierholzer). Which link is a single point of failure? Bridges (low-links). Who can reach whom both ways? Strongly connected components (Kosaraju).
Plus two modelling moves: ratios are weighted edges (multiply along a path), and choose the right vertices (in Bus Routes, a bus is a vertex).
picture this
Picture your company's microservice map. An Euler path is one test run that calls every API link exactly once. A bridge is the one link whose failure cuts a group of services off — a single point of failure. An SCC is a cluster of services that all end up calling each other, so they must be deployed and debugged as one unit.
watch it
Hierholzer — rebuild the itinerary
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
Hierholzer — rebuild the itinerary
Each airport keeps a min-heap of unused tickets. An airport joins the route only when it is stuck — so BLR, a dead end, lands at the end of the trip.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
watch it
Bridges with tin and low (Tarjan)
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
Bridges with tin and low (Tarjan)
Every vertex shows tin · low. Dashed edges are back edges (a second way up). An edge turns red when low[child] > tin[parent].
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
key idea 1 of 10
Read it once. Say it out loud once. Bas.
Euler path = a walk that uses every EDGE exactly once. Directed: all edges connected, and every vertex has out = in, except one start (out − in = 1) and one end (in − out = 1). Undirected: 0 or 2 odd-degree vertices.
key idea 2 of 10
Read it once. Say it out loud once. Bas.
Hierholzer: walk until you are stuck; when a vertex has no unused edges left, add it to the route; reverse at the end. Dead ends land at the end of the route by themselves, and loops get spliced in. O(E) — O(E log E) with a min-heap per vertex.
key idea 3 of 10
Read it once. Say it out loud once. Bas.
Euler ≠ Hamiltonian. Visiting every VERTEX once (Hamiltonian) is NP-complete; using every EDGE once (Euler) is linear. Recasting a problem in Euler form is a superpower — it's how short-read DNA assemblers work.
key idea 4 of 10
Read it once. Say it out loud once. Bas.
tin and low: DFS stamps tin[u] when it first reaches u; low[u] = the smallest tin that u's subtree can reach with one back edge. A tree edge u–v is a bridge iff low[v] > tin[u].
key idea 5 of 10
Read it once. Say it out loud once. Bas.
Articulation point (cut vertex): a non-root u with a DFS child v where low[v] ≥ tin[u]; the DFS root iff it has 2+ DFS children. In both tests, skip the edge you came in on.
key idea 6 of 10
Read it once. Say it out loud once. Bas.
SCC = a largest group of vertices that all reach each other (directed). Shrink every SCC to one node and the graph becomes a DAG — so topological sort works again.
key idea 7 of 10
Read it once. Say it out loud once. Bas.
Kosaraju: pass 1 records the DFS finish order; pass 2 runs DFS on the REVERSED graph in reverse finish order, and each DFS collects exactly one SCC. Tarjan: one DFS with low-links and a stack. Both O(V + E).
key idea 8 of 10
Read it once. Say it out loud once. Bas.
Ratios are a weighted graph: a / b = k gives a → b with weight k and b → a with 1/k. A query is a path: multiply the weights. A variable that never appears → -1.
key idea 9 of 10
Read it once. Say it out loud once. Bas.
Choose the vertices: when the cost counts groups (buses, flights), make the groups the vertices. Bus Routes as BFS over buses is O(Σ route lengths); over stops a single long route can mean ~5·10⁹ edges.
key idea 10 of 10
Read it once. Say it out loud once. Bas.
Java depth: these are recursive DFS algorithms. A 10⁵-vertex chain can overflow the call stack — know the explicit-stack version (ArrayDeque + a per-vertex neighbour index).
spot the pattern
When you see this, think this
"Use every ticket / edge / domino exactly once"
Euler path: degree check + Hierholzer (add when stuck, reverse)
"Critical connection", "single point of failure", "removing one link disconnects"
Bridges with a tin/low DFS (articulation points if it's a node)
Directed graph: "groups that can all reach each other", "collapse the cycles"
SCCs (Kosaraju or Tarjan), then work on the condensation DAG
"a / b = k", conversion factors, "x is k times y"
Weighted graph: multiply along a path (or weighted union-find)
+2 more signals on the chapter page
watch out
A trap or two
Many wrong answers in interviews come from small slips like these, not from the hard part.
- LC 332: taking the smallest ticket greedily and stopping at a dead end, or adding an airport when you arrive (pre-order). Add it when it's stuck (post-order) and reverse at the end.
- LC 332: removing from the front of an
ArrayListfor every ticket is O(E) each. Use aPriorityQueue(or a sortedArrayDeque) per airport.
quick check
One question. No pressure.
Directed edges 0→1, 1→2, 2→0, 0→3. Where must an Euler path start?
now try
Your first real problem
You know enough to try this one. Stuck? Use the hints; that is what they are for.
Reconstruct Itinerary
open the problem →recall
Flip a few cards
Answer in your head first, then flip. Grade yourself honestly; the schedule brings back what you forget.
When does a directed graph have an Euler path?
Question 1: When does a directed graph have an Euler path?
done
Lesson complete
Chalo, that is the core. The full chapter has the rest: cost tables, Java details and more problems.