Lab 12 — Eulerian Path & Hierholzer’s Algorithm

Goal

Decide the existence of an Eulerian path (uses every edge exactly once) or Eulerian circuit (path that returns to start) in directed and undirected graphs, and construct one in O(E) via Hierholzer’s algorithm. Apply to LeetCode 332 (Reconstruct Itinerary). After this lab you should state the degree conditions cold for both graph flavors and write the iterative Hierholzer in <15 minutes.

Background Concepts

An Eulerian circuit traverses every edge once and ends where it started; an Eulerian path traverses every edge once but may start and end at distinct vertices. Existence is a pure degree-and-connectivity question — no search needed to decide, only to construct.

Undirected. Let a graph be connected on the vertices that touch at least one edge (isolated vertices are irrelevant). Then:

• Eulerian circuit ⟺ every vertex has even degree.
• Eulerian path ⟺ exactly 0 or 2 vertices have odd degree. (2 odd ⇒ they are the endpoints; 0 odd ⇒ it is a circuit.)

Directed. Let the graph be connected when edge directions are ignored (on edge-touched vertices). Then:

• Eulerian circuit ⟺ in(v) == out(v) for every vertex.
• Eulerian path ⟺ exactly one vertex has out − in = +1 (the start), exactly one has in − out = +1 (the end), and all others satisfy in == out.

Hierholzer builds the trail in O(E). The clean formulation is the post-order append: walk greedily from the start, consuming edges as you go; when a vertex has no unused outgoing edge, append it to the output; reverse the output at the end. Equivalently: DFS that emits a vertex only once its adjacency list is exhausted. This is a correct, single-pass rendering of the “walk a cycle, splice in sub-cycles” idea — the recursion stack is the splice.

Why naive greedy-DFS fails. A plain DFS that commits to the first path it finds and returns it can strand edges: from JFK it might fly JFK→KUL (dead end) and never come back for JFK→NRT→JFK. The post-order trick avoids this because a vertex is only emitted after all its edges are drained, so stranded cycles get spliced automatically.

Euler vs Hamilton. Eulerian (every edge once) is decidable and constructible in O(E) by a degree check. Hamiltonian (every vertex once) is NP-complete — see Phase 13’s TSP lab. One is a local parity condition; the other is a global search. Do not confuse the two under interview pressure.

Interview Context

Eulerian-path problems are disguised: “reconstruct the itinerary,” “arrange the pairs into a chain,” “shortest string containing all codes.” The tell is use every edge/pair exactly once, order matters. Interviewers like it because the naive candidate reaches for backtracking (exponential) while the strong candidate recognizes the Euler structure and writes O(E) Hierholzer. Getting the lexicographic tie-break right on LC 332 while keeping linearity is the L5 signal.

Problem Statement (LC 332)

You are given a list of airline tickets where tickets[i] = [from_i, to_i]. Reconstruct the itinerary in order and return it. All tickets belong to a man who departs from "JFK", so the itinerary must begin with "JFK". If multiple valid itineraries exist, return the one that is lexicographically smallest when read as a single concatenated list of airports. You may assume all tickets form at least one valid itinerary; you must use all the tickets exactly once.

Constraints

• 1 ≤ tickets.length ≤ 300 (LC 332); generalize the technique to E up to 10⁵.
• Airport codes are 3 uppercase letters.
• A valid Eulerian path is guaranteed to exist.

Clarifying Questions

1. Must the path start at a fixed vertex? (Yes — "JFK" for LC 332; in the generic version the start is forced by the degree imbalance.)
2. Are multi-edges (duplicate tickets) allowed? (Yes — treat each ticket as its own edge.)
3. Is a valid Eulerian path guaranteed, or must I detect infeasibility? (LC 332 guarantees one; the generic find_euler_path must return None when none exists.)
4. Circuit or open path? (Either — the degree check tells you which; the algorithm is the same.)
5. Directed or undirected? (LC 332 is directed; undirected needs edge used-flags by id.)

Examples

tickets = [[MUC,LHR],[JFK,MUC],[SFO,SJC],[LHR,SFO]]
→ [JFK, MUC, LHR, SFO, SJC]

tickets = [[JFK,SFO],[JFK,ATL],[SFO,ATL],[ATL,JFK],[ATL,SFO]]
→ [JFK, ATL, JFK, SFO, ATL, SFO]   (not JFK,SFO,... — lexicographically smaller)

tickets = [[JFK,KUL],[JFK,NRT],[NRT,JFK]]
→ [JFK, NRT, JFK, KUL]   (greedy JFK→KUL would strand the NRT cycle)

Initial Brute Force

Backtracking: from the start vertex, try each unused outgoing edge in sorted order, recurse, and accept the first complete trail that consumes all E edges. Because ties are explored in lexicographic order, the first success is the lexicographically smallest itinerary.

Brute Force Complexity

Exponential in the worst case: the recursion branches over unused edges at each step, O(E!) in adversarial multigraphs, with backtracking on dead ends. Fine for LC 332’s E ≤ 300 only because valid solutions are dense; it collapses at E = 10⁵.

Optimization Path

The problem is exactly “find an Eulerian path.” Hierholzer solves construction in O(E). For the lexicographic requirement, store each vertex’s outgoing edges in a min-heap (or pre-sort and consume with a pointer); popping the smallest destination first makes the post-order-reversed output lexicographically minimal. The heap variant is O(E log E); pre-sorting once is also O(E log E) but with a cheaper inner loop. Both beat backtracking decisively.

Final Expected Approach

1. Build adjacency lists; heapify each so the smallest next hop pops first.
2. Iterative Hierholzer with an explicit stack: push the start; while the top vertex has an unused edge, pop its smallest destination and push it; when it has none, pop it into route.
3. Reverse route.

import heapq
from collections import defaultdict

def find_itinerary(tickets):
    graph = defaultdict(list)
    for src, dst in tickets:
        graph[src].append(dst)
    for src in graph:
        heapq.heapify(graph[src])          # min-heap per vertex: lex tie-break
    route, stack = [], ["JFK"]
    while stack:
        while graph[stack[-1]]:            # drain smallest edges first
            stack.append(heapq.heappop(graph[stack[-1]]))
        route.append(stack.pop())          # post-order: emit when exhausted
    return route[::-1]                      # reverse to get forward trail

def find_euler_path(n, edges):
    """Generic directed Eulerian path over vertices 0..n-1, or None."""
    adj = [[] for _ in range(n)]
    indeg, outdeg = [0] * n, [0] * n
    for u, v in edges:
        adj[u].append(v); outdeg[u] += 1; indeg[v] += 1
    start = -1
    for v in range(n):                      # locate the unique +1 out-imbalance
        d = outdeg[v] - indeg[v]
        if d == 1:
            if start != -1: return None     # two candidate starts
            start = v
        elif d not in (0, -1):
            return None                      # imbalance beyond ±1
    ends = sum(1 for v in range(n) if indeg[v] - outdeg[v] == 1)
    if (start != -1) != (ends == 1):
        return None                          # start without a matching end
    if start == -1:                          # circuit: begin anywhere with edges
        start = next((v for v in range(n) if outdeg[v]), 0)
    ptr = [0] * n                            # next unused edge index per vertex
    route, stack = [], [start]
    while stack:
        v = stack[-1]
        if ptr[v] < len(adj[v]):
            stack.append(adj[v][ptr[v]]); ptr[v] += 1
        else:
            route.append(stack.pop())
    if len(route) != len(edges) + 1:         # unreached edges ⇒ disconnected
        return None
    return route[::-1]

Data Structures Used

• Adjacency lists (defaultdict(list)), min-heaps for the lexicographic variant.
• indeg[], outdeg[] int arrays for the directed degree test.
• An explicit stack for iterative Hierholzer, plus a per-vertex ptr[] (or the heap itself) tracking the next unused edge.
• route[] built in reverse.

Correctness Argument

Edge-disjoint cycle decomposition. If every vertex satisfies the balance condition, the edge set decomposes into edge-disjoint cycles (start any walk from a balanced vertex; it can only get stuck by returning to the start, forming a cycle; remove it and recurse). Hierholzer stitches these cycles: the outer walk is one cycle; whenever it revisits a vertex with leftover edges, the stack dives into another cycle and splices it in at exactly that point.

Why post-order append is correct. A vertex is appended only when its edge list is exhausted, i.e. after every cycle through it has been fully walked. Reversing yields a sequence where each vertex precedes the continuation of the trail that leaves it — a valid Eulerian ordering. The reversal is what turns “deepest-finished-first” into “first-traversed-first.”

Completeness check. If the graph is disconnected on edge-touched vertices, some edges are never reached, so len(route) != E + 1; returning None is correct. The degree scan rejects imbalances that make any Eulerian trail impossible before the walk begins.

Complexity

Implementation Requirements

• Build route in reverse and reverse once at the end — never insert(0, …) (that is O(E²)).
• Use an iterative stack, not recursion: E up to 10⁵ blows the Python recursion limit.
• For the heap variant, heapq.heapify each list once; do not re-sort per pop.
• For the generic version, return None on any of: imbalance beyond ±1, start-without-end mismatch, or unreached edges.

Tests

• LC 332 example 1 → [JFK,MUC,LHR,SFO,SJC].
• LC 332 example 2 → [JFK,ATL,JFK,SFO,ATL,SFO] (lex tie-break exercised).
• Greedy-killer [[JFK,KUL],[JFK,NRT],[NRT,JFK]] → [JFK,NRT,JFK,KUL].
• find_euler_path(3, [(0,1),(1,2),(2,0)]) → a valid circuit.
• find_euler_path(3, [(0,1),(0,2)]) → None (two out-imbalances).
• find_euler_path(4, [(0,1),(1,0),(2,3),(3,2)]) → None (disconnected).
• Stress: random directed multigraphs, compare find_euler_path existence against a backtracking oracle and validate every returned trail.

Follow-up Questions

• Why does the post-order append produce a valid trail rather than garbage? The edge set decomposes into edge-disjoint cycles; a vertex is emitted only after all its cycles are drained. The recursion/stack order is a DFS over that cycle structure, and reversing the finish order yields a topological-like ordering of the splice points — exactly one consistent Eulerian traversal.
• How do De Bruijn sequences relate (LC 753, Cracking the Safe)? Build a graph whose vertices are length-(n−1) strings over a k-symbol alphabet and whose edges are length-n strings (edge a·s → s·b). Every vertex has in-degree = out-degree = k, so an Eulerian circuit exists; walking it emits every length-n string exactly once, giving a shortest cyclic De Bruijn sequence. Cracking the Safe is precisely this Euler circuit.
• How does the undirected variant differ in bookkeeping? Each undirected edge is one resource shared by two endpoints, so you cannot just pop from an adjacency list — you tag each edge with an id and keep a used[id] flag (or remove it from both endpoints). Existence needs 0 or 2 odd-degree vertices; if 2, start at an odd one.
• Where does this appear in genome assembly? Real short-read assemblers build a de Bruijn graph over k-mers and find an Eulerian path through it to reconstruct the sequence — “k-universal string” and “DNA fragment assembly” are the same Eulerian-path problem. Euler beats the Hamiltonian-path formulation (overlap graph) precisely because Euler is polynomial and Hamilton is NP-complete.
• What is Valid Arrangement of Pairs (LC 2097)? The pure directed-Eulerian-path problem with no lexicographic constraint: arrange all pairs so consecutive pairs chain. Run find_euler_path starting from the vertex with out − in = +1 (or any vertex if balanced).
• What if some vertices have odd degree and I still want to cover every edge? That is the Chinese Postman (Route Inspection) problem: pair up odd-degree vertices via minimum-weight matching, duplicate the shortest paths between matched pairs to make all degrees even, then take an Eulerian circuit of the augmented graph.

Product Extension

Network monitoring and testing frameworks that must traverse every link exactly once (link-coverage test suites, packet-tracing) are Eulerian-circuit problems on the topology graph. Automated test-path generation over a state-transition model — cover every transition (edge) with the fewest walks — reduces to Eulerian path plus, when the model has odd-degree states, a Chinese-Postman augmentation. Genome assemblers (SPAdes, Velvet) are the highest-profile production use: the de Bruijn Eulerian path is the algorithmic core.

Language/Runtime Follow-ups

• Python: use an explicit stack, never recursion — sys.setrecursionlimit is a smell here. heapq on the adjacency lists gives the lex order; collections.defaultdict(list) avoids key checks.
• Java: PriorityQueue<String> per source for LC 332; use an ArrayDeque as the Hierholzer stack and Collections.reverse at the end, or addFirst into a LinkedList.
• C++: multiset<string> or a sorted vector with an iterator per vertex; std::reverse the route. Watch that erasing from a multiset invalidates only the erased iterator.
• Go: sort each adjacency slice once and consume via an index pointer; append to a slice and reverse in place.
• JS/TS: heaps aren’t built in — pre-sort adjacency arrays and shift() (or index-pointer to avoid O(n) shifts), then reverse().

Common Bugs

1. Naive greedy without splicing: committing to the first complete-looking path strands cycles (the JFK→KUL trap). The post-order emit is not optional — it is the algorithm.
2. route.insert(0, v) instead of append+reverse: turns O(E) into O(E²); TLE at E = 10⁵.
3. Recursion depth overflow: recursive Hierholzer hits Python’s ~1000-frame limit on long trails. Use the explicit stack.
4. Wrong start vertex in the generic version: an open path must start at the out − in = +1 vertex, not an arbitrary one; starting elsewhere strands the imbalanced tail.
5. Missing the connectivity check: the degree conditions are necessary but not sufficient — two balanced components pass the parity test yet have no single Eulerian trail. Verify len(route) == E + 1.
6. Undirected edge counted once: forgetting to mark an undirected edge used from both endpoints re-traverses it; use edge ids with a used[] flag.

Debugging Strategy

Print the degree table first: for the directed case list (v, in, out, out−in) and confirm at most one +1 and one −1. If existence is wrong, the bug is in the scan, not the walk. For the walk, trace the stack and route on the greedy-killer [[JFK,KUL],[JFK,NRT],[NRT,JFK]]: the stack should dive JFK→KUL, pop KUL (dead end) into route, then unwind and take the NRT cycle — final route before reversal is [KUL, JFK, NRT, JFK]. If your route length ≠ E + 1, you have a disconnected graph or a consumed-edge accounting bug.

Mastery Criteria

• Stated both directed and undirected existence conditions (degree + connectivity) from memory in <2 minutes.
• Wrote iterative Hierholzer for LC 332 with correct lex tie-break in <15 minutes.
• Explained why post-order append works via edge-disjoint cycle decomposition.
• Solved LC 332, LC 2097, and LC 753 from a cold start.
• Distinguished Eulerian (O(E)) from Hamiltonian (NP-complete) instantly.
• Name-dropped De Bruijn / genome assembly and the Chinese Postman extension.