Topological sort and cycle detection

coreCommon atGoogleMetaAmazonAnthropicStripeRead firstGraph representationBreadth-first searchDepth-first searchPractise in the Sandbox →

A topological order lists the nodes of a directed graph so that for every edge a → b, a comes before b. One exists exactly when the graph has no directed cycle (it’s a DAG, a directed acyclic graph). Two standard algorithms find it in O(V + E): Kahn’s (repeatedly remove a node with no incoming edges) and DFS (reverse the order in which nodes finish). Both double as cycle detectors.

The idea in plain words

You’re getting dressed. Socks before shoes, trousers before shoes and belt, shirt before tie, tie and belt before jacket. Any order that respects every “before” rule works, and there are usually many.

How do you build one? Ask: what can I do right now, with nothing left to wait for? Do one of those, cross it off, and some other item may now have nothing left to wait for. Repeat. That’s Kahn’s algorithm.

When does it fail? When every remaining item waits for another remaining item. That only happens if the waits form a loop: a cycle. So “I got stuck before finishing” is the cycle test, for free.

Vocabulary:

• In-degree of a node: how many edges point into it. In-degree 0 means “no prerequisites left”.
• DAG: a directed graph with no cycles. Every DAG has at least one topological order. A graph with a cycle has none.

See it

The default graph is an evening plan (buy > shop means “buy before shop”). Step through Kahn’s algorithm: the badge under each node is its current in-degree. Then load With a cycle and watch the queue run dry with nodes left over. Switch to DFS for the other algorithm.

Peel off nodes with nothing left to wait for

step through

directed edges (before>after)

DAGWith a cycle

queue (in-degree 0)

buywash

topological order

(empty)

output0/7

queue2

in the queuejust taken / edges removedjust reached in-degree 0outputstuck: on or behind a cycle

Count incoming edges for every node (badges). Nodes with in-degree 0 have no prerequisites, so they start in the queue: buy, wash.

↺◀▶ Play▶1 / 9

When to reach for it

The problem says…	Why topological sort fits
“prerequisites”, “depends on”, “must happen before”	Dependencies are directed edges; an order respecting them is a topological order.
“can all of these be finished?”	Equivalent to “is the dependency graph acyclic?”
“build order”, “install order”, “evaluation order” of formulas	Evaluate each item after the items it reads.
“detect a circular dependency / deadlock”	Kahn leftovers or a DFS back edge are the cycle.
longest / shortest path in a DAG, counting paths in a DAG	Process nodes in topological order and relax edges once: DP on a DAG.

How it works

Kahn’s algorithm (BFS-like)

1. Build the adjacency list and count each node’s in-degree.
2. Put every in-degree-0 node in a queue.
3. Pop a node, append it to the output, and decrement the in-degree of each successor. Any successor that hits 0 joins the queue.
4. When the queue is empty: if the output has all V nodes, it’s a valid order. Otherwise the leftovers are on or downstream of a cycle.

Python

kahn.py

from collections import deque


def kahn(n: int, edges: list[tuple[int, int]]) -> list[int] | None:
    """Order nodes 0..n-1 so every edge (a, b) has a before b. None if there's a cycle."""
    succ: list[list[int]] = [[] for _ in range(n)]
    indeg = [0] * n
    for a, b in edges:                      # 1. build adjacency and count incoming edges
        succ[a].append(b)
        indeg[b] += 1
    ready = deque(v for v in range(n) if indeg[v] == 0)   # 2. nothing to wait for
    order: list[int] = []
    while ready:
        u = ready.popleft()                 # 3. emit u and "delete" its outgoing edges
        order.append(u)
        for v in succ[u]:
            indeg[v] -= 1
            if indeg[v] == 0:               # v's last prerequisite just finished
                ready.append(v)
    return order if len(order) == n else None   # 4. leftovers mean a cycle


if __name__ == "__main__":
    order = kahn(6, [(5, 2), (5, 0), (4, 0), (4, 1), (2, 3), (3, 1)])
    assert order is not None
    pos = {v: i for i, v in enumerate(order)}
    assert all(pos[a] < pos[b] for a, b in [(5, 2), (5, 0), (4, 0), (4, 1), (2, 3), (3, 1)])
    assert kahn(3, [(0, 1), (1, 2), (2, 0)]) is None
    assert kahn(2, []) == [0, 1]
    print("ok")

TypeScript

kahn.ts

import assert from "node:assert/strict";

/** Order nodes 0..n-1 so every edge [a, b] has a before b. null if there's a cycle. */
export function kahn(n: number, edges: [number, number][]): number[] | null {
  const succ: number[][] = Array.from({ length: n }, () => []);
  const indeg = new Array<number>(n).fill(0);
  for (const [a, b] of edges) { // 1. build adjacency and count incoming edges
    succ[a].push(b);
    indeg[b]++;
  }
  const ready: number[] = []; // 2. nothing to wait for
  for (let v = 0; v < n; v++) if (indeg[v] === 0) ready.push(v);
  const order: number[] = [];
  for (let head = 0; head < ready.length; head++) {
    const u = ready[head]; // 3. emit u and "delete" its outgoing edges
    order.push(u);
    for (const v of succ[u]) {
      if (--indeg[v] === 0) ready.push(v); // v's last prerequisite just finished
    }
  }
  return order.length === n ? order : null; // 4. leftovers mean a cycle
}

const edges: [number, number][] = [[5, 2], [5, 0], [4, 0], [4, 1], [2, 3], [3, 1]];
const order = kahn(6, edges);
assert.ok(order);
const pos = new Map(order.map((v, i) => [v, i]));
assert.ok(edges.every(([a, b]) => pos.get(a)! < pos.get(b)!));
assert.equal(kahn(3, [[0, 1], [1, 2], [2, 0]]), null);
assert.deepEqual(kahn(2, []), [0, 1]);
console.log("ok");

C#

kahn.cs

(int, int)[] edges = [(5, 2), (5, 0), (4, 0), (4, 1), (2, 3), (3, 1)];
var order = Kahn(6, edges) ?? throw new Exception("expected an order");
var pos = order.Select((v, i) => (v, i)).ToDictionary(p => p.v, p => p.i);
if (!edges.All(e => pos[e.Item1] < pos[e.Item2])) throw new Exception("edge out of order");
if (Kahn(3, [(0, 1), (1, 2), (2, 0)]) is not null) throw new Exception("cycle not detected");
if (string.Join(",", Kahn(2, [])!) != "0,1") throw new Exception("no edges");
Console.WriteLine("ok");

// Order nodes 0..n-1 so every edge (a, b) has a before b. null if there's a cycle.
static List<int>? Kahn(int n, (int, int)[] edges)
{
    var succ = Enumerable.Range(0, n).Select(_ => new List<int>()).ToArray();
    var indeg = new int[n];
    foreach (var (a, b) in edges) { succ[a].Add(b); indeg[b]++; }   // 1. adjacency + in-degrees
    var ready = new Queue<int>(Enumerable.Range(0, n).Where(v => indeg[v] == 0)); // 2. nothing to wait for
    var order = new List<int>();
    while (ready.Count > 0)
    {
        var u = ready.Dequeue();                     // 3. emit u and "delete" its outgoing edges
        order.Add(u);
        foreach (var v in succ[u])
            if (--indeg[v] == 0) ready.Enqueue(v);   // v's last prerequisite just finished
    }
    return order.Count == n ? order : null;          // 4. leftovers mean a cycle
}

DFS: reverse post-order

When DFS finishes a node, everything reachable from it has already finished. So for every edge u → v, v finishes before u. Reverse the finish order and every edge points forward.

1. Run DFS from every unvisited node, colouring nodes gray on entry and black on exit.
2. Seeing a gray neighbour means a back edge: report a cycle.
3. On exit, append the node to a post list.
4. Return post reversed.

Python

dfs_topo.py

def dfs_topo(adj: dict[str, list[str]]) -> list[str] | None:
    """Reverse post-order of a DFS. None if the graph has a cycle."""
    state: dict[str, int] = {}          # missing = white, 1 = gray (on path), 2 = black (done)
    post: list[str] = []

    def visit(u: str) -> bool:
        state[u] = 1
        for v in adj.get(u, []):
            if state.get(v) == 1:       # 1. gray neighbour: back edge, cycle
                return False
            if v not in state and not visit(v):
                return False
        state[u] = 2
        post.append(u)                  # 2. u finishes after everything it points to
        return True

    for u in adj:                       # 3. cover every component
        if u not in state and not visit(u):
            return None
    return post[::-1]                   # 4. reverse finish order = dependencies first


if __name__ == "__main__":
    g = {"socks": ["shoes"], "pants": ["shoes", "belt"], "shirt": ["belt", "tie"],
         "tie": ["jacket"], "belt": ["jacket"], "shoes": [], "jacket": []}
    order = dfs_topo(g)
    assert order is not None
    pos = {v: i for i, v in enumerate(order)}
    assert all(pos[a] < pos[b] for a in g for b in g[a])
    assert dfs_topo({"a": ["b"], "b": ["a"]}) is None
    print("ok")

TypeScript

dfs_topo.ts

import assert from "node:assert/strict";

/** Reverse post-order of a DFS. null if the graph has a cycle. */
export function dfsTopo(adj: Map<string, string[]>): string[] | null {
  const state = new Map<string, 1 | 2>(); // missing = white, 1 = gray (on path), 2 = black (done)
  const post: string[] = [];
  const visit = (u: string): boolean => {
    state.set(u, 1);
    for (const v of adj.get(u) ?? []) {
      if (state.get(v) === 1) return false; // 1. gray neighbour: back edge, cycle
      if (!state.has(v) && !visit(v)) return false;
    }
    state.set(u, 2);
    post.push(u); // 2. u finishes after everything it points to
    return true;
  };
  for (const u of adj.keys()) { // 3. cover every component
    if (!state.has(u) && !visit(u)) return null;
  }
  return post.reverse(); // 4. reverse finish order = dependencies first
}

const g = new Map(Object.entries({
  socks: ["shoes"], pants: ["shoes", "belt"], shirt: ["belt", "tie"],
  tie: ["jacket"], belt: ["jacket"], shoes: [], jacket: [],
}));
const order = dfsTopo(g);
assert.ok(order);
const pos = new Map(order.map((v, i) => [v, i]));
for (const [a, bs] of g) for (const b of bs) assert.ok(pos.get(a)! < pos.get(b)!);
assert.equal(dfsTopo(new Map([["a", ["b"]], ["b", ["a"]]])), null);
console.log("ok");

C#

dfs_topo.cs

var g = new Dictionary<string, List<string>>
{
    ["socks"] = ["shoes"], ["pants"] = ["shoes", "belt"], ["shirt"] = ["belt", "tie"],
    ["tie"] = ["jacket"], ["belt"] = ["jacket"], ["shoes"] = [], ["jacket"] = [],
};
var order = DfsTopo(g) ?? throw new Exception("expected an order");
var pos = order.Select((v, i) => (v, i)).ToDictionary(p => p.v, p => p.i);
if (!g.All(kv => kv.Value.All(b => pos[kv.Key] < pos[b]))) throw new Exception("edge out of order");
if (DfsTopo(new() { ["a"] = ["b"], ["b"] = ["a"] }) is not null) throw new Exception("cycle missed");
Console.WriteLine("ok");

// Reverse post-order of a DFS. null if the graph has a cycle.
static List<string>? DfsTopo(Dictionary<string, List<string>> adj)
{
    var state = new Dictionary<string, int>(); // missing = white, 1 = gray (on path), 2 = black
    var post = new List<string>();
    bool Visit(string u)
    {
        state[u] = 1;
        foreach (var v in adj.GetValueOrDefault(u, []))
        {
            if (state.GetValueOrDefault(v) == 1) return false;        // 1. gray neighbour: cycle
            if (!state.ContainsKey(v) && !Visit(v)) return false;
        }
        state[u] = 2;
        post.Add(u);                                                  // 2. u finishes after its successors
        return true;
    }
    foreach (var u in adj.Keys)                                       // 3. cover every component
        if (!state.ContainsKey(u) && !Visit(u)) return null;
    post.Reverse();                                                   // 4. dependencies first
    return post;
}

Which order is 'the' answer?

There are usually many valid orders. If the problem wants a specific one, such as “smallest first when there’s a choice”, replace Kahn’s FIFO queue with a min-heap. That raises the cost to O(V log V + E). DFS can’t easily give that kind of tie-break.

What it costs

	Time	Extra space
Kahn’s algorithm	O(V + E): each node enqueued once, each edge decremented once	O(V) in-degrees + queue
DFS reverse post-order	O(V + E)	O(V) colours + recursion depth up to V
Kahn with a min-heap tie-break	O(V log V + E)	O(V)
Checking a proposed order	O(V + E): map node → position, check every edge	O(V)

Kahn or DFS?

	Kahn	DFS
Mental model	“do whatever is ready now”	“finish everything after me first”
Cycle signal	output shorter than V	edge into a gray node
Recursion	none	yes (depth up to V), or a careful iterative version
Gives levels / rounds	yes: process the queue layer by layer	no
Custom tie-breaks	easy, swap in a heap	awkward
Finding the actual cycle	needs extra work on leftovers	easy: walk the gray path from the back edge

Kahn’s layers are useful on their own: layer k is the set of nodes whose longest chain of prerequisites has length k. That’s the minimum number of “rounds” if unlimited work can run in parallel.

Variations you’ll meet

• Lexicographically smallest order: min-heap instead of queue.
• Parallel rounds / earliest finish times: process Kahn’s queue level by level, or do DP over the order, finish[v] = max(finish[u]) + duration[v] over incoming u.
• Longest or shortest path in a DAG with weights (even negative ones): relax edges in topological order, O(V + E). No Dijkstra needed.
• Counting paths from a source: ways[v] += ways[u] in topological order.
• Is the order unique? It is exactly when Kahn’s queue never holds more than one node.
• Undirected cycle detection is a different problem: use union-find or DFS with a parent check.

Pitfalls

• Edge direction. “a depends on b” means b → a if edges mean “must come before”. Decide and write it down before coding.
• Isolated nodes with no edges are easy to forget. Seed in-degrees from the full node list, not just from edges.
• Duplicate edges double-count in-degree. That’s fine as long as you also decrement twice (you will, if the adjacency list has both copies). Deduplicating one but not the other is a bug.
• Self-loops (a → a) are cycles. Kahn handles them naturally; make sure your input parsing doesn’t drop them.
• Visited-only DFS reports false cycles on diamonds. You need the gray state.

In the interview

• Ask: are all nodes listed, or only those in edges? Can there be duplicate edges or self-loops? What should happen on a cycle (return empty, throw, report the cycle)? Any tie-break rule?
• Say the invariant for Kahn: “A node enters the queue only once all its prerequisites are output, so the output never violates an edge.”
• Say the cycle argument: “If the queue empties early, every leftover node has an incoming edge from another leftover, so following those edges backwards must loop.”
• Expected follow-ups: smallest order by name, which tasks can run in parallel, total time with durations, report the cycle, support adding edges over time.

Check yourself

Check yourself

pick one

Kahn's algorithm stops with 5 of 8 nodes output. What do you know about the other 3?

AThey are isolated nodesBEach still has an incoming edge from another leftover node, so they lie on or after a cycleCThe algorithm has a bug; Kahn always outputs every nodeDThey have no outgoing edges

Check yourself

pick one

Why does reversing DFS post-order give a valid topological order in a DAG?

ABecause DFS visits nodes in sorted orderBBecause for every edge u→v, v finishes before uCBecause post-order is the same as BFS order

Check yourself

pick one

During Kahn's algorithm the queue holds two nodes at once. What does that tell you?

AThe graph has a cycleBThe topological order is not unique: either node could go nextCOne of the two nodes is isolated

Practice on your own

These are classic textbook exercises, not gym questions:

• The getting-dressed example from CLRS: produce any valid order for the clothing graph.
• Given a list of package dependencies, return an install order or the packages involved in a cycle.
• Longest path in a weighted DAG from a given source.
• Count the number of distinct paths from a source to a sink in a DAG.
• Determine whether a DAG has exactly one topological order.

Go deeper

• CLRS, Introduction to Algorithms, “Topological sort” in the elementary graph algorithms chapter: the DFS method and its proof.
• A. B. Kahn, “Topological sorting of large networks”, Communications of the ACM 5(11), 1962: the original in-degree algorithm.
• cp-algorithms: Topological sorting and finding a cycle.
• Sedgewick and Wayne, Algorithms 4.2: Directed graphs, Topological and DirectedCycle.

Related

Depth-first searchColours, finish times and edge types.

Dependency resolutionTopological order in build systems and schedulers.

Dynamic programming: 1DDP over a topological order: longest paths, path counts.

HeapsTie-break ready nodes by priority.