Topological Sort: Kahn's Algorithm & DFS Explained

Topological Sort orders vertices in a DAG so that for every edge u→v, u comes before v.

Its core advantage:

Kahn’s algorithm uses in-degree tracking for O(V+E) topological ordering without recursion.

Watch in-degrees fall to zero as tasks are output — the queue only ever contains “ready now” tasks:

Topological Sort (Kahn's)

Linear order of tasks respecting all dependencies in a DAG.

Queue every node with in-degree 0; repeatedly output one, delete its outgoing edges, and enqueue any neighbour whose in-degree hits 0. If not all nodes are output, the graph has a cycle and no valid order exists.

GRAPH VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        compute inDegree[] for all nodes
                      
                        2
                        queue = all nodes with inDegree 0
                      
                        3
                        while queue not empty:
                      
                        4
                          n = queue.poll(); output n
                      
                        5
                          for each neighbour m:
                      
                        6
                            if --inDegree[m] == 0: queue.add(m)

Focus on recognizing:

“Dependency order” + “Course schedule” + “Task ordering” = Topological Sort

Pattern Table

Pattern	Typical Questions	Trigger
Kahn’s Algorithm (BFS)	Course schedule, build order	In-degree array + queue
DFS Postorder	Topological order	DFS + add to result post-visit

Mental Trigger

DAG + ordering → In-degree array + Queue of nodes with in-degree 0.

1. Generic Java Topological Sort Template (Base)

public int[] topologicalSort(int n, int[][] edges) {
    List<Integer>[] graph = new ArrayList[n];
    int[] indegree = new int[n];

    for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
    for (int[] e : edges) {
        graph[e[0]].add(e[1]);
        indegree[e[1]]++;
    }

    Queue<Integer> q = new LinkedList<>();
    for (int i = 0; i < n; i++)
        if (indegree[i] == 0) q.offer(i);

    int[] order = new int[n];
    int idx = 0;

    while (!q.isEmpty()) {
        int u = q.poll();
        order[idx++] = u;

        for (int v : graph[u])
            if (--indegree[v] == 0) q.offer(v);
    }

    return idx == n ? order : new int[0];
}

from collections import deque

def topological_sort(n, edges):
    graph = [[] for _ in range(n)]
    indegree = [0] * n

    for u, v in edges:
        graph[u].append(v)
        indegree[v] += 1

    q = deque(
        i for i in range(n) if indegree[i] == 0
    )

    order = []
    idx = 0

    while q:
        u = q.popleft()
        order.append(u)

        for v in graph[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                q.append(v)

    return order if len(order) == n else []

vector<int> topologicalSort(int n, vector<vector<int>>& edges) {
    vector<vector<int>> graph(n);
    vector<int> indegree(n);

    for (auto& e : edges) {
        graph[e[0]].push_back(e[1]);
        indegree[e[1]]++;
    }

    queue<int> q;
    for (int i = 0; i < n; i++)
        if (indegree[i] == 0) q.push(i);

    vector<int> order;
    order.reserve(n);

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        order.push_back(u);

        for (int v : graph[u])
            if (--indegree[v] == 0) q.push(v);
    }

    return (int)order.size() == n ? order : vector<int>();
}

function topologicalSort(n, edges) {
  const graph = Array.from({ length: n }, () => []);
  const indegree = new Array(n).fill(0);

  for (const [u, v] of edges) {
    graph[u].push(v);
    indegree[v]++;
  }

  // ponytail: shift() is O(n), fine at this scale; use head-index deque if profiling matters
  const q = [];
  for (let i = 0; i < n; i++)
    if (indegree[i] === 0) q.push(i);

  const order = [];
  let idx = 0;

  while (q.length > 0) {
    const u = q.shift();
    order[idx++] = u;

    for (const v of graph[u])
      if (--indegree[v] === 0) q.push(v);
  }

  return idx === n ? order : [];
}

Common Mistakes

Not detecting cycles.

If result length < n, there’s a cycle — return empty array.

Wrong edge direction.

For “A depends on B”, edge is B→A, not A→B.

Recognition Cheat Sheet

If you see…	Think…
Course schedule / prerequisites	Kahn’s algorithm
Build/dependency order	Topological sort
Cycle detection in DAG	Check result length

⚠️ Animation & Content Notice

Topological Sort

⚠️ Animation & Content Notice

Topological Sort (Kahn's)

Pattern Table

Mental Trigger

1. Generic Java Topological Sort Template (Base)

Common Mistakes

Recognition Cheat Sheet

Premium Content

My Private Notes

Earn Premium with Referrals

Topological Sort (Kahn's)

Pattern Table

Mental Trigger

1. Generic Java Topological Sort Template (Base)

Common Mistakes

Recognition Cheat Sheet

Premium Content

My Private Notes