Definition
- Topological Sort – a linear ordering of all nodes in a directed acyclic graph (DAG) such that for every directed edge from node A to node B, A appears before B.
- Kahn's algorithm – BFS approach that computes in-degrees, queues all zero in-degree nodes, and removes them one by one while decrementing neighbours' in-degrees.
- DFS variant – pushes nodes onto a stack in post-order; the reversed stack is the topological order.
- Cycle detection – if the output contains fewer nodes than exist in the graph, a cycle prevents a complete ordering.
- Complexity – O(V + E) time and O(V + E) space where V is nodes and E is edges.
The National Bank of India has a set of end-of-day batch jobs where some jobs must finish before others can start. Interest posting must complete before statement generation, and statement generation must complete before archival. Topological Sort finds a safe execution order by always running the jobs that currently have no pending prerequisites, just like a project manager who starts tasks whose dependencies are all finished.
Understanding the Concepts
What is Topological Sort?
Topological Sort is a linear ordering of all nodes in a directed acyclic graph (DAG) such that for every directed edge from node U to node V, U appears before V in the ordering. It answers the question: in what order should I process these items so that every prerequisite is handled first?
The ordering is not unique. A graph may have multiple valid topological orders. For example, if A must come before B and A must come before C but B and C have no dependency between them, both A-B-C and A-C-B are valid.
package com.bank.service;
// Banking batch jobs with dependencies:
// InterestPosting -> StatementGeneration -> Archival
// InterestPosting -> TaxCalculation
// Valid order: InterestPosting, TaxCalculation, StatementGeneration, Archival
// Also valid: InterestPosting, StatementGeneration, TaxCalculation, Archival
How does Kahn's algorithm work?
Kahn's algorithm is the BFS-based approach. It models prerequisites as directed edges from a prerequisite to its dependent. The steps are:
- Build the adjacency list and compute the in-degree (number of incoming edges) for every node.
- Add all nodes with in-degree zero to a queue. These have no prerequisites and can go first.
- While the queue is not empty, remove a node, append it to the output order, and for each of its neighbours decrement their in-degree by one. If a neighbour's in-degree reaches zero, add it to the queue.
- If the output contains all nodes, the ordering is valid. Otherwise the graph has a cycle.
package com.bank.service;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class TopologicalSort {
public List<Integer> kahnSort(int numJobs, int[][] dependencies) {
List<List<Integer>> adj = new ArrayList<>();
int[] inDegree = new int[numJobs];
for (int i = 0; i < numJobs; i++) {
adj.add(new ArrayList<>());
}
for (int[] dep : dependencies) {
int prereq = dep[0];
int dependent = dep[1];
adj.get(prereq).add(dependent);
inDegree[dependent]++;
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numJobs; i++) {
if (inDegree[i] == 0) {
queue.add(i);
}
}
List<Integer> order = new ArrayList<>();
while (!queue.isEmpty()) {
int node = queue.poll();
order.add(node);
for (int next : adj.get(node)) {
inDegree[next]--;
if (inDegree[next] == 0) {
queue.add(next);
}
}
}
if (order.size() != numJobs) {
throw new IllegalArgumentException("Cycle detected: no valid order");
}
return order;
}
}
How does the DFS-based topological sort work?
The DFS variant visits each unvisited node, recursively visits all its neighbours first, and then pushes the current node onto a stack after all its dependents are processed. The reversed stack (or reading it from top to bottom) is the topological order.
The key insight is that a node is pushed after all nodes it leads to are already on the stack, so it appears before them in the final order.
package com.bank.service;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;
public class DfsTopologicalSort {
public List<Integer> dfsSort(int numJobs, int[][] dependencies) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < numJobs; i++) adj.add(new ArrayList<>());
for (int[] d : dependencies) adj.get(d[0]).add(d[1]);
boolean[] visited = new boolean[numJobs];
boolean[] inStack = new boolean[numJobs];
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < numJobs; i++) {
if (!visited[i]) {
if (hasCycle(i, adj, visited, inStack, stack)) {
throw new IllegalArgumentException("Cycle detected");
}
}
}
List<Integer> order = new ArrayList<>();
while (!stack.isEmpty()) order.add(stack.pop());
return order;
}
private boolean hasCycle(int node, List<List<Integer>> adj,
boolean[] visited, boolean[] inStack,
Stack<Integer> stack) {
visited[node] = true;
inStack[node] = true;
for (int next : adj.get(node)) {
if (inStack[next]) return true; // cycle
if (!visited[next] && hasCycle(next, adj, visited, inStack, stack)) {
return true;
}
}
inStack[node] = false;
stack.push(node);
return false;
}
}
How is Kahn's BFS different from DFS topological sort?
| Feature | Kahn's (BFS) | DFS-based |
|---|---|---|
| Approach | Queue of zero in-degree nodes | Recursive post-order traversal |
| Cycle detection | Output size < node count | Back edge detected during DFS |
| Output method | Direct order from queue removal | Reversed stack |
| Parallelism | Naturally shows independent tasks | Harder to identify parallel groups |
| Implementation | Iterative with queue | Recursive with stack |
Kahn's algorithm is often preferred in interviews because the BFS queue makes the process easy to trace step by step.
What are the edge cases?
- Empty graph: zero nodes, return an empty list.
- Single node: return a list with that one node.
- Disconnected components: each component is sorted independently, but the algorithm handles it because all zero in-degree nodes from all components enter the queue.
- Multiple valid orderings: both Kahn's and DFS produce one valid order. The specific order depends on which node is dequeued first.
package com.bank.service;
public class TopSortEdgeCases {
public static void main(String[] args) {
TopologicalSort sorter = new TopologicalSort();
// Single node, no dependencies
System.out.println(sorter.kahnSort(1, new int[][]{}));
// Linear chain: 0 -> 1 -> 2
System.out.println(sorter.kahnSort(3, new int[][]{{0,1},{1,2}}));
// Diamond: 0 -> 1, 0 -> 2, 1 -> 3, 2 -> 3
System.out.println(sorter.kahnSort(4, new int[][]{{0,1},{0,2},{1,3},{2,3}}));
}
}
[0]
[0, 1, 2]
[0, 1, 2, 3]
What happens when there is a cycle?
If the graph has a cycle, no topological ordering exists because you can never find a node whose prerequisites are all satisfied within the cycle. In Kahn's algorithm, the output list will have fewer nodes than the graph because the cycle nodes never reach in-degree zero. This shortfall is the standard cycle detection mechanism.
package com.bank.service;
public class CycleDetectionDemo {
public static void main(String[] args) {
TopologicalSort sorter = new TopologicalSort();
try {
// Cycle: 0 -> 1 -> 2 -> 0
sorter.kahnSort(3, new int[][]{{0,1},{1,2},{2,0}});
} catch (IllegalArgumentException e) {
System.out.println(e.getMessage());
}
}
}
Cycle detected: no valid order
What about the banking use case?
At the National Bank of India, the end-of-day batch system has jobs with dependencies. Interest posting must complete before statement generation. Statement generation must complete before archival. Tax calculation depends on interest posting but is independent of statement generation.
package com.bank.service;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class BatchScheduler {
public static void main(String[] args) {
// Jobs: 0=InterestPosting, 1=StatementGeneration,
// 2=Archival, 3=TaxCalculation
int[][] deps = {
{0, 1}, // InterestPosting -> StatementGeneration
{1, 2}, // StatementGeneration -> Archival
{0, 3} // InterestPosting -> TaxCalculation
};
TopologicalSort sorter = new TopologicalSort();
List<Integer> order = sorter.kahnSort(4, deps);
Map<Integer, String> names = new HashMap<>();
names.put(0, "InterestPosting");
names.put(1, "StatementGeneration");
names.put(2, "Archival");
names.put(3, "TaxCalculation");
System.out.println("Batch execution order:");
for (int job : order) {
System.out.println(" " + names.get(job));
}
}
}
Batch execution order:
InterestPosting
StatementGeneration
TaxCalculation
Archival
What should a senior engineer know?
- Build systems like Maven and Gradle use topological sort to resolve dependency order.
- Course schedulers use it to determine which courses can be taken in which semester given prerequisites.
- Longest path in a DAG can be found with a topological sort followed by dynamic programming relaxation.
- Parallel execution: in Kahn's algorithm, all nodes in the queue at the same time have no dependencies on each other and can execute in parallel. This is how build systems determine which tasks can run concurrently.
- Lexicographically smallest order: use a min-heap instead of a plain queue in Kahn's algorithm.
What are common interview follow-up questions?
- How do you detect a cycle? (Output size check in Kahn's, back-edge detection in DFS.)
- Can you find all valid topological orderings? (Yes, using backtracking, but the count can be exponential.)
- What if you want the lexicographically smallest order? (Replace the queue with a priority queue.)
- How does topological sort relate to shortest/longest path in a DAG? (Sort first, then relax edges in topological order.)
Visual Overview
Kahn's Algorithm: BFS-based Topological Sort Step 1: Compute in-degrees ┌───┐ ┌───┐ ┌───┐ ┌───┐ │ A │────▶│ B │────▶│ C │────▶│ D │ │(0)│ │(1)│ │(1)│ │(1)│ └───┘ └───┘ └───┘ └───┘ Step 2: Enqueue zero in-degree: Queue = [A] Step 3: Remove A, output A, decrement B's in-degree Queue = [B] Output = [A] Step 4: Remove B, output B, decrement C's in-degree Queue = [C] Output = [A, B] Step 5: Remove C, output C, decrement D's in-degree Queue = [D] Output = [A, B, C] Step 6: Remove D, output D Queue = [] Output = [A, B, C, D] ← valid order
Banking Batch Job Dependencies:
┌──────────────────┐
│ Interest Posting │
└────────┬─────────┘
│
┌─────┴──────┐
▼ ▼
┌──────────┐ ┌──────────────┐
│ Tax Calc │ │ Statement Gen │
└──────────┘ └──────┬───────┘
▼
┌──────────┐
│ Archival │
└──────────┘
Key Takeaway
Topological Sort produces a linear ordering of nodes in a directed acyclic graph so that every edge points from an earlier node to a later node. Kahn's algorithm does this with a BFS approach: compute in-degrees, queue all zero in-degree nodes, and repeatedly remove a node, output it, and decrement its neighbours' in-degrees. Any neighbour whose in-degree drops to zero enters the queue. The whole process runs in O(V + E) time.
The built-in bonus of Kahn's algorithm is cycle detection. If the output contains fewer nodes than the graph, a cycle prevented some nodes from ever reaching in-degree zero, which means no valid topological ordering exists. The DFS variant detects cycles through back edges during traversal and builds the order by pushing nodes onto a stack in post-order.
The practical value is enormous. At the National Bank of India, the end-of-day batch system has dozens of jobs with complex dependencies: interest posting before statement generation, statement generation before archival, tax calculation depending on interest posting. Running Kahn's algorithm over the dependency graph produces a safe execution order so that no job ever starts before its prerequisites are finished.
A senior engineer also knows that all nodes in the queue at the same time are independent and can execute in parallel, which is how build systems determine which tasks to run concurrently. And for the lexicographically smallest valid order, you simply replace the queue with a min-heap.
Remember one sentence: topological sort linearizes a DAG by always picking nodes with no remaining prerequisites, and a shortfall in the output count means a cycle.
---