DSA Roadmap/Graphs

Topological Sort & Eulerian Paths

Order a DAG with Kahn's or DFS postorder — plus Hierholzer's algorithm when the ask is an Eulerian path that uses every edge once (Reconstruct Itinerary).

!!!3/5Theory: 1h 50m7 problems

What problem this solves

Topological sort produces a linear ordering of a graph's vertices such that for every directed edge u -> v, u appears somewhere before v in the ordering. It answers questions of the shape "given these dependencies, in what order can I do these things?" — course prerequisites, build-system compilation order, package installation order, spreadsheet formula evaluation, task scheduling. It is defined only for Directed Acyclic Graphs (DAGs); if the graph has a cycle, no valid ordering exists (you cannot finish task A before B, B before C, and C before A), and detecting that impossibility is itself a core part of this subtopic.

There are two standard algorithms — Kahn's (BFS, in-degree based) and DFS-based (postorder reversal) — and interviewers commonly ask you to know both, because they generalize differently: Kahn's naturally extends to "process level by level" and lexicographic-smallest-ordering variants, while DFS-based extends more naturally to "find one dependency chain" and connects directly to the DFS coloring technique used for cycle detection elsewhere in graphs.

This subtopic also covers a related-but-different post-order walk: Hierholzer's algorithm for Eulerian paths (use every edge once). Reconstruct Itinerary lives here because it shares the "append on exit" DFS shape with topo sort — not because tickets form a DAG. The Hierholzer section below draws that line explicitly so you don't force a topological sort onto a cyclic multigraph of flights.

Kahn's algorithm (BFS with in-degree tracking)

The intuition: a vertex can safely go first in the ordering if and only if it has no unprocessed prerequisites — that is, its in-degree (number of incoming edges) is 0. Repeatedly peel off in-degree-0 vertices, and removing a vertex "frees up" its neighbors by decrementing their in-degree.

from collections import deque, defaultdict def kahn_topological_sort(n, edges): graph = defaultdict(list) in_degree = [0] * n for u, v in edges: # u must come before v graph[u].append(v) in_degree[v] += 1 queue = deque(node for node in range(n) if in_degree[node] == 0) order = [] while queue: node = queue.popleft() order.append(node) for neighbor in graph[node]: in_degree[neighbor] -= 1 if in_degree[neighbor] == 0: queue.append(neighbor) if len(order) != n: return None # cycle detected — not all nodes could be ordered return order

Cycle detection falls out for free: nodes on a cycle never reach in-degree 0 (each depends on another node in the same cycle), so they're never enqueued. If len(order) != n at the end, some nodes were left stranded — the graph has a cycle and no topological order exists.

DFS-based (postorder reversal)

The intuition here is different but equally important to internalize: run a DFS, and append each vertex to a list only after all of its descendants have already been fully explored (i.e., on exit, not on entry). The reasoning: by the time you finish exploring everything reachable from v, every vertex v depends on is already in the list. Reversing that list gives a valid topological order.

def dfs_topological_sort(n, edges): graph = defaultdict(list) for u, v in edges: graph[u].append(v) WHITE, GRAY, BLACK = 0, 1, 2 # unvisited, in-progress, fully done color = [WHITE] * n order = [] has_cycle = False def dfs(node): nonlocal has_cycle color[node] = GRAY for neighbor in graph[node]: if color[neighbor] == GRAY: has_cycle = True # back edge to an ancestor -> cycle return if color[neighbor] == WHITE: dfs(neighbor) color[node] = BLACK order.append(node) # postorder: append on exit for node in range(n): if color[node] == WHITE and not has_cycle: dfs(node) if has_cycle: return None return order[::-1]

The three-color scheme (white/gray/black) is the general-purpose directed-cycle-detection technique: a plain boolean visited array is not sufficient for directed graphs, because it can't distinguish "currently on the recursion stack" (gray) from "fully finished and safe" (black). A back edge — one that points to a gray node — is exactly what a cycle looks like during DFS.

Kahn's vs. DFS-based: which to reach for

Kahn's (BFS)DFS-based (postorder)
TimeO(V + E)O(V + E)
SpaceO(V) — no recursion stackO(V) — but includes call stack, up to O(V) deep
Cycle detectionFree: len(order) != nFree: gray-node back edge
Natural extensionProcess one "level" (all currently-unblocked tasks) at a time; lexicographically-smallest order via a min-heap instead of a plain queueFind any single valid chain quickly; reuses the exact DFS template from Backtracking and Trees
Failure mode to watchForgetting to decrement in-degree for every outgoing edgeForgetting the third color state and using a plain visited set, which misses cycles in graphs with multiple paths to the same node
Best when the problem also asks"How many rounds/semesters minimum?" (each BFS layer = one round)"Give me any one valid order fast," or you're already deep in a DFS-based solution for another reason

Both produce a valid ordering — for a DAG with any branching, there are generally many valid topological orders, and returning any one of them is correct unless the problem asks for something more specific (like lexicographically smallest, which requires swapping Kahn's queue for a min-heap at the cost of an extra O(log V) factor).

The ordering is unique exactly when...

A subtle point worth having ready: the topological ordering is unique if and only if, at every step of Kahn's algorithm, the queue holds exactly one element. That condition means every vertex has exactly one possible successor at each point — the graph is a single chain (a Hamiltonian path through the DAG). Most real dependency graphs branch, so most topological sort problems have many valid answers, and "return any of them" is the norm.

Complexity, precisely

Both algorithms are O(V + E) time and O(V) space (excluding the output array), identical to plain BFS/DFS — topological sort is traversal with bookkeeping, not a fundamentally more expensive operation. Building the in-degree array or the adjacency list up front is itself O(V + E), so it doesn't change the asymptotics.

Pitfalls and interview gotchas

  • Using a plain visited set for cycle detection in a directed graph. This is the most common bug: unlike undirected-graph cycle detection (where you just track a parent to avoid), directed cycles require distinguishing "on the current path" from "already fully processed elsewhere." A node can be visited via two different paths without that being a cycle — only revisiting a node still on the stack (gray) is a cycle.
  • Forgetting the len(order) != n check in Kahn's. If you skip this, a cyclic input silently returns a partial, incorrect ordering instead of signaling failure.
  • Self-loops. An edge (u, u) immediately makes in-degree(u) ≥ 1 forever from itself — u can never reach in-degree 0, correctly flagging a cycle, but only if you actually count self-loops in the in-degree array (an easy thing to accidentally filter out).
  • Disconnected DAGs. If the graph has multiple independent components, both algorithms handle this correctly only if you loop over all vertices, not just the ones reachable from a single start node — Kahn's naturally does this by seeding the queue with every in-degree-0 vertex up front; the DFS version needs an explicit outer loop.
  • 0-indexed vs. 1-indexed course/task numbering. Same trap as in Graph Representation & Traversal — verify before sizing your in-degree array.
  • Confusing "topological sort" with "sorting by value." It has nothing to do with comparing vertex labels; it's purely about respecting the edge direction constraints. A "lexicographically smallest" variant is a different, harder ask that requires a priority queue.
  • Greedy forward walks for Eulerian itineraries. Always taking the lex-smallest next ticket (even with a special case for the global sink) fails when a non-sink airport is a dead-end you must postpone. Hierholzer's post-order is the fix — don't invent patches around greedy.

Hierholzer's algorithm: Eulerian paths (not topological sort)

Reconstruct Itinerary and similar "use every edge exactly once" problems are not topological sort — the graph usually has cycles, and you're ordering edges into a walk, not vertices into a dependency order. The right tool is Hierholzer's algorithm for an Eulerian path/circuit.

What an Eulerian path is

A walk that uses every edge exactly once (vertices may repeat). Existence conditions:

GraphEulerian circuit (closed)Eulerian path (open)
Undirectedevery vertex even degreeexactly 0 or 2 odd-degree vertices
Directedevery vertex in = outall balanced except one start with out = in + 1 and one end with in = out + 1

Interview problems that guarantee a valid itinerary (e.g. LC 332) let you skip proving existence and jump straight to constructing the path. Start is often fixed ("JFK").

The algorithm

Do not walk greedily to completion. For each vertex:

  1. While it still has unused outgoing edges, take one and recurse (or push on a stack).
  2. When it has no unused edges left, append it to the route (post-order).
  3. Reverse the route at the end.

Dead-end side trips are fully consumed and recorded first; leftover edges from earlier airports are used afterward. That stitches local tours into one global walk that covers every edge.

from collections import defaultdict def find_itinerary(tickets): adj = defaultdict(list) for a, b in tickets: adj[a].append(b) for v in adj: adj[v].sort(reverse=True) # pop() yields lex-smallest destination route = [] def dfs(airport): while adj[airport]: dfs(adj[airport].pop()) # consume one edge route.append(airport) # finished: no unused tickets left dfs("JFK") return route[::-1]

The reverse-sorted adjacency list is the Reconstruct Itinerary twist: among unused edges, always prefer the lexicographically smallest destination. Hierholzer still decides when a vertex is finished; the sort only breaks ties among edges.

Why greedy fails (and why Hierholzer doesn't)

tickets: JFK→A, JFK→B, A→C, B→JFK greedy: JFK → A → C stuck; B unused Hierholzer post-order reverse: JFK → B → JFK → A → C

Greedy commits to A too early. Hierholzer explores A→C as a finished side trip, then still has JFK→B available when backtracking — the post-order placement puts that side trip at the end of the reconstructed route.

Same skeleton, different meaning than DFS topo sort

DFS topological sortHierholzer
Consumesvertices (visit once)edges (each exactly once; vertices repeat)
Graph shapemust be a DAGusually has cycles
Append on exit means"all dependents explored""all outgoing edges used"
Outputvertex orderedge-covering walk (as a vertex sequence)

The shared idea is post-order: append only when the current node's remaining work is done. What "remaining work" means differs — neighbors vs unused tickets.

Complexity

O(E log E) if you sort each adjacency list (or use a heap per vertex for lex order), otherwise O(E) with a plain stack/recursion over edges. Space O(E) for the adjacency multigraph plus the route.

Where this reappears

Topological sort is the backbone of scheduling and build-dependency problems, and it resurfaces later as a prerequisite technique inside Dynamic Programming on Trees & Graphs (processing nodes in dependency order is often exactly what makes a graph DP well-defined), and it's the natural first step whenever a problem gives you a DAG and asks for "the order to process things" or "is this even possible."

Hierholzer reappears whenever the prompt is "reconstruct a tour / itinerary that uses every ticket/road exactly once" — recognize Eulerian path, not "DFS the airports" or "topo-sort the flights."

Further Resources (Optional)

Practice Problems

Interview relevancy:!!!Critical — must-have!!Important — highly recommended!Good to have~Niche — rarely asked

Optional Practice (Extra Reps)

For once you've cleared the main set above and want more reps on this pattern. These don't count toward the roadmap's progress stats — solve them purely for your own benefit.