Log inSign up
mediumGeeksforGeeksNot Started

Kahn's Algorithm

Given a Directed Acyclic Graph (DAG) with V vertices and E edges, compute a topological ordering using Kahn's algorithm (in-degree based BFS). If a cycle exists, detect it.

Graph
Solve on GeeksforGeeks
Lesson

Problem Statement

### Problem Statement

Given a Directed Graph with V vertices numbered 0 to V - 1 and an adjacency list adj.

Compute a Topological Sort of the graph using Kahn's Algorithm (In-Degree based BFS).

A topological sort is a linear ordering of vertices such that for every directed edge u -> v, vertex u comes before vertex v in the ordering.

If the graph contains a directed cycle, no valid topological sort exists; return an empty list []. Otherwise, return a valid topological sort array of length V.

---

### Examples

Example 1: ``text Input: V = 6, adj = [[], [], [3], [1], [0, 1], [0, 2]] Output: [4, 5, 2, 3, 1, 0] (or [5, 4, 2, 3, 1, 0]) Explanation: - In-degrees: deg(0)=2, deg(1)=2, deg(2)=1, deg(3)=1, deg(4)=0, deg(5)=0. - Nodes 4 and 5 have in-degree 0. They are processed first. - As edges from 4 and 5 are removed, in-degrees of downstream nodes decrease to 0. - Every directed edge u -> v points forward in the result.

Example 2 (Cycle Detected): ``text Input: V = 2, adj = [[1], [0]] Output: [] Explanation: Cycle 0 -> 1 -> 0 prevents any node from having in-degree 0 initially. Result length = 0 < V => cycle detected.

---

### Constraints - 1 <= V <= 10^5 - 0 <= adj[i].length <= V - Directed graph without self-loops.

Constraints:

  • 1 <= V <= 105
  • 0 <= E <= 2 * 105
  • 0-indexed directed graph

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Explain the fundamental theorem: every finite DAG has at least one source (in-degree 0) and one sink (out-degree 0).
  • Implement Kahn's in-degree BFS queue pattern.
  • Detect directed cycles using the processed count comparison count < V.
  • Apply Kahn's algorithm across C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Course schedule prerequisite resolution.
  • Build systems and task dependency ordering (Makefile, Webpack).
  • Deadlock detection in operating systems.
  • Alien dictionary character precedence.

Algorithmic Decision Tree:

  • If need topological sort AND cycle detection using BFS -> Kahn's Algorithm in O(V + E).
  • If need topological sort using DFS -> DFS with 3-coloring (White/Gray/Black) or postorder stack in O(V + E).

Connected Patterns:

Course ScheduleCourse Schedule IIAlien DictionaryFind Eventual Safe States

1. Repeated Array Scan for Zero In-Degree

Intuition

Maintain in-degree array. In each of V rounds, scan all vertices linearly to find an unprocessed node with in-degree 0.

Algorithm

  1. Compute in-degree array of size V.
  2. Create visited array of size V initialized to false.
  3. Repeat V times:
  4. Scan for unvisited node u with inDegree[u] == 0.
  5. If no such node exists: cycle detected, return [].
  6. Mark visited[u] = true, append u to result.
  7. For each neighbor v of u: inDegree[v]--.
  8. Return result.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6vector<int> kahnsLinearScan(int V, const vector<vector<int>>& adj) {
7 vector<int> inDegree(V, 0);
8 for (int u = 0; u < V; ++u) {
9 for (int v : adj[u]) inDegree[v]++;
10 }
11
12 vector<bool> visited(V, false);
13 vector<int> result;
14
15 for (int step = 0; step < V; ++step) {
16 int u = -1;
17 for (int i = 0; i < V; ++i) {
18 if (!visited[i] && inDegree[i] == 0) {
19 u = i;
20 break;
21 }
22 }
23
24 if (u == -1) return {}; // Cycle detected
25
26 visited[u] = true;
27 result.push_back(u);
28
29 for (int v : adj[u]) {
30 inDegree[v]--;
31 }
32 }
33 return result;
34}
35
36int main() {
37 int V = 6;
38 vector<vector<int>> adj = {{}, {}, {3}, {1}, {0, 1}, {0, 2}};
39 auto res = kahnsLinearScan(V, adj);
40 cout << "Topological Sort (Linear Scan): ";
41 for (int v : res) cout << v << " ";
42 cout << endl;
43 return 0;
44}

Time & Space Complexity

  • Time complexity: O(V^2 + E)
  • Space complexity: O(V)

2. DFS with Reverse Finishing Times

Intuition

Use Depth-First Search with visited set. Push vertices to a stack after all outgoing edges have been explored. Reversing the stack yields topological order.

Algorithm

  1. Maintain visited array with 3 states (0 = unvisited, 1 = visiting, 2 = visited).
  2. For each vertex i from 0 to V - 1:
  3. If unvisited, call dfs(i).
  4. In dfs(u):
  5. Mark state[u] = 1 (visiting).
  6. For each neighbor v:
  7. If state[v] == 1: cycle detected! return false.
  8. If state[v] == 0: if !dfs(v) return false.
  9. Mark state[u] = 2 (visited).
  10. Push u onto stack.
  11. Reverse stack to produce final order.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <stack>
4#include <algorithm>
5
6using namespace std;
7
8bool dfs(int u, const vector<vector<int>>& adj, vector<int>& state, vector<int>& order) {
9 state[u] = 1; // Visiting
10
11 for (int v : adj[u]) {
12 if (state[v] == 1) return false; // Cycle detected
13 if (state[v] == 0) {
14 if (!dfs(v, adj, state, order)) return false;
15 }
16 }
17
18 state[u] = 2; // Visited
19 order.push_back(u);
20 return true;
21}
22
23vector<int> topoSortDFS(int V, const vector<vector<int>>& adj) {
24 vector<int> state(V, 0);
25 vector<int> order;
26
27 for (int i = 0; i < V; ++i) {
28 if (state[i] == 0) {
29 if (!dfs(i, adj, state, order)) return {};
30 }
31 }
32
33 reverse(order.begin(), order.end());
34 return order;
35}
36
37int main() {
38 int V = 6;
39 vector<vector<int>> adj = {{}, {}, {3}, {1}, {0, 1}, {0, 2}};
40 auto res = topoSortDFS(V, adj);
41 cout << "DFS Topo Sort: ";
42 for (int v : res) cout << v << " ";
43 cout << endl;
44 return 0;
45}

Time & Space Complexity

  • Time complexity: O(V + E)
  • Space complexity: O(V)

3. Kahn's Algorithm (In-Degree BFS Queue)

Intuition

Compute in-degrees for all vertices. Enqueue all vertices with in-degree 0. Dequeue, append to result, and decrement neighbor in-degrees, enqueuing when 0.

Algorithm

  1. Initialize inDegree array of size V with 0s.
  2. For each vertex u and neighbor v in adj[u]: inDegree[v]++.
  3. Initialize FIFO queue q. For each vertex i from 0 to V - 1: if inDegree[i] == 0, push i to q.
  4. Initialize result array topoOrder.
  5. While q is not empty:
  6. Dequeue front vertex u, append u to topoOrder.
  7. For each outgoing neighbor v of u:
  8. inDegree[v]--.
  9. If inDegree[v] == 0: push v to q.
  10. If topoOrder.length == V: return topoOrder.
  11. Otherwise: return [] (directed cycle detected).

Kahn's In-Degree BFS Trace

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
inDegree = [2, 2, 1, 1, 0, 0]
Visual state
Values and pointers at this exact step
table
This state table trace has no visual items for the current step yet. Add step.items (and connections where needed) to render its structure accurately.
Decision / next transition
Dequeue 4
Why this step matters

inDegree = [2, 2, 1, 1, 0, 0]. Nodes 4 and 5 have inDegree 0. Queue: [4, 5].

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4
5using namespace std;
6
7vector<int> kahnsAlgorithm(int V, const vector<vector<int>>& adj) {
8 vector<int> inDegree(V, 0);
9 for (int u = 0; u < V; ++u) {
10 for (int v : adj[u]) {
11 inDegree[v]++;
12 }
13 }
14
15 queue<int> q;
16 for (int i = 0; i < V; ++i) {
17 if (inDegree[i] == 0) {
18 q.push(i);
19 }
20 }
21
22 vector<int> topoOrder;
23 while (!q.empty()) {
24 int u = q.front();
25 q.pop();
26 topoOrder.push_back(u);
27
28 for (int v : adj[u]) {
29 inDegree[v]--;
30 if (inDegree[v] == 0) {
31 q.push(v);
32 }
33 }
34 }
35
36 // Cycle check: If not all vertices are processed, cycle exists!
37 if (topoOrder.size() != V) {
38 return {};
39 }
40
41 return topoOrder;
42}
43
44int main() {
45 int V = 6;
46 vector<vector<int>> adj = {{}, {}, {3}, {1}, {0, 1}, {0, 2}};
47 auto order = kahnsAlgorithm(V, adj);
48
49 cout << "Optimal Kahn's Topological Order: ";
50 for (int v : order) cout << v << " ";
51 cout << endl;
52 return 0;
53}

Time & Space Complexity

  • Time complexity: O(V + E)
  • Space complexity: O(V)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Unoptimized Repeated Array Scan (Naive)O(V^2 + E)O(V)In each of V rounds, scan the inDegree array linearly to find an unprocessed node with in-degree 0.Linear scan for in-degree 0 vertices.
2.DFS with Reverse Finishing TimesO(V + E)O(V)Run DFS traversal, push nodes to stack upon completion. Reverse stack gives topological order.Recursion call stack overhead.
3.Kahn's In-Degree BFS Queue Algorithm (Optimal)OptimalO(V + E)O(V)Maintain in-degree array and FIFO queue of 0-in-degree nodes. Incrementally dequeue, decrement neighbors, and enqueue new 0-degree nodes.Standard BFS edge traversal.

Common Pitfalls & Crucial Edge Cases

Assuming topological sort is unique

Multiple valid orders exist whenever queue has > 1 elements.

Applying Kahn's to undirected graphs

Topological sorting is only defined on Directed Acyclic Graphs (DAGs).

Missing cycle check

Forgetting to check if order.length == V before returning.

Crucial Edge Cases to Validate:

  • Graph with 0 edges — In-degree of all vertices is 0; any permutation [0, 1, ..., V - 1] is valid.
  • Self-loop (u -> u) — in-degree of u is at least 1 and never drops to 0; detected as a cycle.
  • Linear DAG (0 -> 1 -> 2 -> ... -> V-1) — Exactly one unique topological sort.
  • Disconnected DAG components — All components sorted concurrently without issues.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Kahn's is BFS-based; compare with Tarjan's DFS-based topological sort.
  2. Highlight how Kahn's algorithm is used in Course Schedule I and II (LeetCode 207 and 210).
  3. Explain that Kahn's can produce lexicographically smallest topological sort by replacing the FIFO queue with a min-heap priority queue.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does Kahn's algorithm fail to produce a topological sort of length V if the graph contains a directed cycle?

2.Can a graph have multiple valid topological sort orderings?

Back to DSA Sheet