Eulerian paths

Problem

You are given a pile of one-way tickets, links or dominoes and must order all of them into one unbroken chain. The chain has to use each item once, so what matters is the edges, not the nodes: a node may be visited many times. This is different from a Hamiltonian path (every node once), which is hard in general, while the edge version is easy.

Intuition

Every time a route passes through a node it enters on one edge and leaves on another, so the edges at a middle node come in pairs. For directed edges that means a middle node has as many tickets in as out. Only the start can have one extra ticket out and only the end one extra in. If the counts fit, a path exists as long as all the edges sit in one connected piece. That is Euler's theorem, and it turns "does a route exist" into counting.

Finding the route is where a greedy walk fails. Walk from the start taking any unused ticket and you may reach a node that has no tickets out while others remain unused: you walked into the dead end too early. The fix is the key idea of Hierholzer's algorithm. Keep walking until stuck, then take the stuck node as the last stop of the route, step back along the path and continue from the nearest node that still has unused tickets. Each stuck node is written down as you back out of it, so the finished list is the route in reverse.

Arrows point from the departure to the arrival; the number on each is its place in the route. The diagram scrolls sideways on a narrow screen.

Mechanics

When a path exists

For a directed graph, compute out-degree minus in-degree at every node. Every difference must be 0, except that one node may be +1 (the start) and one node may be -1 (the end). All the edges must also be reachable from one another when directions are ignored. With all differences 0 the route is a circuit and can start anywhere that has an edge. For an undirected graph the rule is that zero or two nodes have an odd degree.

Hierholzer's algorithm

1. Put the start node on a stack.
2. Look at the top node. If it still has an unused edge, remove that edge and push its far end.
3. If it has none, pop it and append it to the output.
4. When the stack is empty, reverse the output. That is the route.

To get the lexically smallest route, sort each node's destinations so that the smallest comes off first. No other change is needed.

Why the reversed pops are a route

A node is popped only when it has no unused edges. The first node popped is therefore a node where the walk got stuck, and in a graph that has a valid path that can only be the end. Everything pushed after the last node that still had spare edges forms a closed loop back to that node, because no node on it can be stuck except there. Popping that loop and continuing splices it into the path at the right place. Every edge is removed once, so the work is linear.

Where the plain greedy walk breaks

A walk that never backs up works only when the first dead end is the true end. On the example it takes the smallest name, ATL, and is stuck at once with 3 tickets unused. Hierholzer's algorithm makes the same first move, but because it records ATL as finished and resumes from JFK, the dead end lands at the end of the route.

Amber rows push a node; blue rows pop one. The finished column, read right to left, is the route.

Worked example

The tickets are JFK to ATL, JFK to LAX, LAX to SEA, SEA to JFK. JFK has one more ticket out than in and ATL one more in than out, so the degree check reports a path from JFK to ATL.

Running the algorithm takes 9 steps, shown in the table above. The smallest name from JFK is ATL, which has nothing to leave by, so ATL is popped first. The stack falls back to JFK, whose other ticket leads round the loop LAX, SEA, JFK. The pop order is ATL, JFK, SEA, LAX, JFK, and reversed it is JFK, LAX, SEA, JFK, ATL, using all 4 tickets.

When no route exists. Two separate round trips such as a→b, b→a, c→d, d→c have balanced degrees but the edges are not connected, and the check reports none. A shape with a branch such as a to b and a to c has two nodes with an extra in-edge, and also fails.

A circuit. The edges A→B, B→C, C→A, A→D, D→A are balanced everywhere, so they form a circuit, and Hierholzer's from A returns A, B, C, A, D, A.

Implementation

from collections import defaultdict

def find_itinerary(tickets, start="JFK"):
    graph = defaultdict(list)
    for src, dst in sorted(tickets, reverse=True):
        graph[src].append(dst)       # smallest destination ends up last

    route = []
    stack = [start]
    while stack:
        while graph[stack[-1]]:
            stack.append(graph[stack[-1]].pop())
        route.append(stack.pop())
    return route[::-1]

The inner while walks until the top node is stuck; the outer loop pops it. This is the same algorithm as the step list above, written with the pushes collapsed into one loop. The recursive form is shorter still but can exceed Python's recursion limit on long chains.

Variations and edge cases

def has_euler_path(edges):
    out, into = defaultdict(int), defaultdict(int)
    for u, v in edges:
        out[u] += 1
        into[v] += 1
    starts = ends = 0
    for node in set(out) | set(into):
        diff = out[node] - into[node]
        if diff == 1:
            starts += 1
        elif diff == -1:
            ends += 1
        elif diff != 0:
            return False
    return starts == ends and starts <= 1   # connectivity is checked separately

• Choosing the start. If one node has an extra out-edge, that is the start. For a circuit, any node with an edge works. When a problem fixes the start, as itinerary problems do, trust it.
• Undirected graphs. Remove the edge from both ends when it is used, for instance by giving each edge an id and a used flag.
• Arranging pairs. "Order these [start, end] pairs so each starts where the last ended" is the same problem with numbers as nodes: find the node with an extra out-edge (or any node for a circuit) and run Hierholzer's, keeping the edges in the output.
• Lexical order. Sort once up front; do not re-sort inside the loop.
• Reversal. Forgetting to reverse the output is the usual bug. For lexical order, popping from the end of a reverse-sorted list is O(1); popping from the front of a sorted list is O(n).
• Edge cases: a single ticket, repeated identical tickets (each is a separate edge), self-loops (a node with a ticket to itself) and tickets that cannot connect, which the length check on the route catches.

Complexity and tradeoffs

• Time: O(E) after sorting; with the sort, O(E log E).
• Space: O(V + E) for the adjacency lists, the stack and the output.
• Baseline. Backtracking over every ordering of tickets is exponential and, with a lexical rule, still needs a backtrack on dead ends. Backtracking with a used set works on small inputs but can revisit the same dead end repeatedly.
• When it fails. If the question needs every node once, this is the wrong tool. If the graph has no path, the length check on the route is the only signal, so check degrees first if "no route" must be reported precisely.

Problems

Reconstruct Itinerary is the standard question: tickets are directed edges, the start is fixed, and the smallest lexical route wins. It is solved exactly as the implementation above.

Hard

• 332. Reconstruct Itinerary NeetCode 150 NeetCode 250
  Visit destinations in lexical order with Hierholzer's algorithm, adding an airport to the route only when it has no tickets left, then reverse the route.

Connections

Hierholzer's algorithm is a depth-first search that records nodes in post-order, the same bookkeeping that topological sort uses; the difference is that edges, not nodes, are consumed. It also contrasts with backtracking, which would try orderings and undo them, where here the dead end is simply placed last.

Check yourself

References

• Euler, "Solutio problematis ad geometriam situs pertinentis", 1736 (the Königsberg bridges and the degree condition).
• Hierholzer and Wiener, "Über die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren", Mathematische Annalen 6, 1873.
• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, section 22.3 (depth-first search) and the problem on Euler tours.
• Skiena, The Algorithm Design Manual, the Eulerian cycle / Chinese postman entry in the catalog.
• Sedgewick and Wayne, Algorithms, section 4.2 (directed graphs and DFS order).
• The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.