Eulerian path (Hierholzer's algorithm)

How does Eulerian path (Hierholzer's algorithm) work?

Check the degrees before anything else. An undirected path allows at most two nodes with an odd degree.

In a directed graph, at most one node may have an extra outgoing edge. That node has to be the start.

Walk forward greedily and delete each edge as you use it. A used edge is never walked again.

When a node has no edges left, push it onto an output stack. It is stuck, so it belongs near the end.

Step back to the previous node and carry on. Any unused edges there are still reachable.

Reverse the output stack at the very end. That puts the path in the right order.

Sources: Wikipedia: Eulerian path

1. at JFK, edges to A and BTake A first when the smallest route is wanted.
2. at A, then back to JFKThe only edge out of A returns to JFK.
3. at B: no edges leftB is stuck, so it is pushed first.
4. push JFK, A, JFKEach node is pushed once it runs dry.
5. reversed: JFK, A, JFK, BReading the stack backwards gives the route.

function eulerianPath(tickets, start) {
    const adj = {};
    for (const [from, to] of tickets) {
        (adj[from] ||= []).push(to);
    }
    for (const from in adj) adj[from].sort().reverse(); // pop smallest first
    const route = [];
    const stack = [start];
    while (stack.length) {
        const node = stack[stack.length - 1];
        if (adj[node] && adj[node].length) {
            stack.push(adj[node].pop());
        } else {
            route.push(stack.pop()); // dead end: record and back up
        }
    }
    return route.reverse();
}

function eulerianPath(tickets: string[][], start: string): string[] {
    const adj: Record<string, string[]> = {};
    for (const [from, to] of tickets) {
        (adj[from] ??= []).push(to);
    }
    for (const from in adj) adj[from].sort().reverse(); // pop smallest first
    const route: string[] = [];
    const stack: string[] = [start];
    while (stack.length) {
        const dests = adj[stack[stack.length - 1]] ?? [];
        if (dests.length) {
            stack.push(dests.pop()!);
        } else {
            route.push(stack.pop()!); // dead end: record and back up
        }
    }
    return route.reverse();
}

def eulerian_path(tickets, start):
    adj = {}
    for frm, to in tickets:
        adj.setdefault(frm, []).append(to)
    for frm in adj:
        adj[frm].sort(reverse=True)  # pop smallest first
    route = []
    stack = [start]
    while stack:
        node = stack[-1]
        if adj.get(node):
            stack.append(adj[node].pop())
        else:
            route.append(stack.pop())  # dead end: record and back up
    return route[::-1]

function eulerianPath(array $tickets, string $start): array {
    $adj = [];
    foreach ($tickets as [$from, $to]) {
        $adj[$from][] = $to;
    }
    foreach ($adj as $from => &$list) {
        rsort($list); // pop smallest first
    }
    unset($list);
    $route = [];
    $stack = [$start];
    while ($stack) {
        $node = end($stack);
        if (!empty($adj[$node])) {
            $stack[] = array_pop($adj[$node]);
        } else {
            $route[] = array_pop($stack); // dead end: record and back up
        }
    }
    return array_reverse($route);
}

    public static List<String> eulerianPath(String[][] tickets, String start) {
        Map<String, List<String>> adj = new HashMap<>();
        for (String[] ticket : tickets) {
            adj.computeIfAbsent(ticket[0], k -> new ArrayList<>()).add(ticket[1]);
        }
        for (List<String> dests : adj.values()) {
            dests.sort(Comparator.reverseOrder()); // pop smallest first
        }
        List<String> route = new ArrayList<>();
        Deque<String> stack = new ArrayDeque<>();
        stack.push(start);
        while (!stack.isEmpty()) {
            List<String> dests = adj.get(stack.peek());
            if (dests != null && !dests.isEmpty()) {
                stack.push(dests.remove(dests.size() - 1));
            } else {
                route.add(stack.pop()); // dead end: record and back up
            }
        }
        Collections.reverse(route);
        return route;
    }

    public static List<string> EulerianPath(string[][] tickets, string start) {
        var adj = new Dictionary<string, List<string>>();
        foreach (var ticket in tickets) {
            if (!adj.ContainsKey(ticket[0])) adj[ticket[0]] = new List<string>();
            adj[ticket[0]].Add(ticket[1]);
        }
        foreach (var dests in adj.Values) {
            dests.Sort();
            dests.Reverse(); // pop smallest first
        }
        var route = new List<string>();
        var stack = new Stack<string>();
        stack.Push(start);
        while (stack.Count > 0) {
            if (adj.TryGetValue(stack.Peek(), out var dests) && dests.Count > 0) {
                string next = dests[dests.Count - 1];
                dests.RemoveAt(dests.Count - 1);
                stack.Push(next);
            } else {
                route.Add(stack.Pop()); // dead end: record and back up
            }
        }
        route.Reverse();
        return route;
    }

A worked example of Eulerian path (Hierholzer's algorithm)

Rebuild a travel itinerary

You get a list of flight tickets. Every ticket must be used exactly once, starting at JFK.

When several routes exist, return the smallest in alphabetical order.

Sort each airport's destinations so the smallest is taken first.

Walk greedily and push an airport once it has no tickets left. Reverse the stack at the end.

function findItinerary(tickets) {
    const graph = new Map();
    for (const [from, to] of tickets) {
        if (!graph.has(from)) graph.set(from, []);
        graph.get(from).push(to);
    }
    // reversed, so pop() hands back the smallest destination
    for (const list of graph.values()) list.sort().reverse();

    const route = [];
    const stack = ["JFK"];

    while (stack.length) {
        const airport = stack[stack.length - 1];
        const next = graph.get(airport);

        if (next && next.length) {
            stack.push(next.pop()); // the ticket is used up
        } else {
            route.push(stack.pop()); // stuck, so this airport ends the route
        }
    }

    return route.reverse();
}

When should you use Eulerian path (Hierholzer's algorithm)?

Use Eulerian path (Hierholzer's algorithm) when the problem statement says “use every edge exactly once”, “reconstruct an itinerary from tickets” or “one-stroke drawing / draw without lifting the pen”. A solution built on it usually runs in O(E).

• •use every edge exactly once
• •reconstruct an itinerary from tickets
• •one-stroke drawing / draw without lifting the pen
• •walk every road/domino exactly once
• •flights or dominoes must chain into one trip

The signal words of every pattern sit in one table, the algorithm patterns cheat sheet.

What is Eulerian path (Hierholzer's algorithm) confused with?

Eulerian path (Hierholzer's algorithm) is most often confused with Graph BFS / DFS, Backtracking, Connected components and Stack (LIFO).

• Graph BFS / DFS: A traversal has to reach every node. This one has to use every edge.
• Backtracking: Trying routes and undoing them is exponential. This walk never has to take a step back.
• Connected components: Every edge must sit in one component, which is one of the conditions here. Counting groups is not the goal.
• Stack (LIFO): The stack is what makes the walk work. This page is about when to push onto it.

Common mistakes with Eulerian path (Hierholzer's algorithm)

• Returning the path in walk order

  The output stack has to be reversed. Walk order puts the dead ends in the wrong place.

• Not deleting the edge you used

  The same edge is then walked forever. Remove it at the moment you take it.

• Skipping the degree check

  Plenty of graphs have no such walk at all. Test the degrees before starting.

• Reaching for backtracking

  Trying and undoing routes explodes on a large graph. The stack rule never needs a retry.

Which interview problems use Eulerian path (Hierholzer's algorithm)?

Interview problems solved with Eulerian path (Hierholzer's algorithm) include Reconstruct itinerary, Valid arrangement of pairs, Cracking the safe, Eulerian circuit check, Domino chain, Rebuild a genome from fragments and The bridges of Konigsberg.

• Reconstruct itinerary: Directed edges, with alphabetical order as the tie-break.
• Valid arrangement of pairs: The start is decided by the degrees.
• Cracking the safe: A de Bruijn sequence is an Eulerian circuit.
• Eulerian circuit check: Every degree even, and all edges in one component.
• Domino chain: Each domino is an edge between two numbers.
• Rebuild a genome from fragments: The overlap graph carries an Eulerian path.
• The bridges of Konigsberg: The original proof that no such walk exists.

What is the time and space complexity of Eulerian path (Hierholzer's algorithm)?

The target complexity of Eulerian path (Hierholzer's algorithm) is O(E).

V nodes and E edges give O(E log E) once the edges are sorted. Without sorting it is O(E).