Definition
- Topological sort – a linear ordering of a directed acyclic graph (DAG) where every edge points from earlier to later.
- Kahn's algorithm – BFS approach using in-degree counts: seed with zero-in-degree nodes, emit, decrement, enqueue new zeros.
- Cycle detection – if fewer than all nodes are emitted, the remaining nodes form a cycle.
- O(V + E) time – each node enqueued once, each edge relaxed once.
- DFS alternative – post-order stack with recursion-stack marker for cycle detection.
Imagine the National Bank of India onboards a new product through a series of steps where some steps cannot start until others finish. A planner writes each step on a card with arrows to dependent steps. She first does all the steps that depend on nothing, then crosses off their arrows, which may free new steps. She keeps going until every step is done. If steps remain but none are free, they are stuck waiting on each other in a circle.
Understanding the Concepts
What is topological sort?
A topological sort of a directed acyclic graph (DAG) is a linear ordering of its nodes such that for every directed edge from A to B, A appears before B. It only exists if the graph has no cycle. The classic use case is ordering tasks with prerequisite dependencies.
package com.bank.graph;
import java.util.*;
public class TopologicalSort {
public static List<Integer> kahnSort(int numNodes, int[][] edges) {
List<List<Integer>> adj = new ArrayList<>();
int[] inDegree = new int[numNodes];
for (int i = 0; i < numNodes; i++) adj.add(new ArrayList<>());
for (int[] e : edges) {
adj.get(e[0]).add(e[1]);
inDegree[e[1]]++;
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numNodes; i++) {
if (inDegree[i] == 0) queue.offer(i);
}
List<Integer> order = new ArrayList<>();
while (!queue.isEmpty()) {
int node = queue.poll();
order.add(node);
for (int next : adj.get(node)) {
if (--inDegree[next] == 0) {
queue.offer(next);
}
}
}
if (order.size() != numNodes) {
System.out.println("Cycle detected! No valid order.");
return Collections.emptyList();
}
return order;
}
public static void main(String[] args) {
// Banking product onboarding steps:
// 0: Open Ledger, 1: Create Account, 2: Post Opening Balance,
// 3: Issue Debit Card, 4: Send Welcome Email
// Dependencies: 0->1, 0->2, 1->2, 1->3, 2->4, 3->4
int[][] edges = {{0,1}, {0,2}, {1,2}, {1,3}, {2,4}, {3,4}};
List<Integer> order = kahnSort(5, edges);
String[] names = {"Open Ledger", "Create Account",
"Post Balance", "Issue Card", "Send Email"};
System.out.print("Order: ");
for (int i : order) System.out.print(names[i] + " -> ");
System.out.println("DONE");
}
}
Order: Open Ledger -> Create Account -> Post Balance -> Issue Card -> Send Email -> DONE
How does Kahn's algorithm work step by step?
- Kahn's algorithm:
- Compute in-degree for every node.
- Seed a queue with all zero-in-degree nodes (no prerequisites).
- Poll a node, add it to the order, decrement in-degree of its dependents.
- When a dependent's in-degree drops to zero, enqueue it.
- Repeat until the queue is empty.
- If the order has fewer than all nodes, a cycle exists.
package com.bank.graph;
import java.util.*;
public class KahnTrace {
public static void main(String[] args) {
int n = 4;
int[][] edges = {{0,1}, {0,2}, {1,3}, {2,3}};
int[] inDeg = new int[n];
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] e : edges) { adj.get(e[0]).add(e[1]); inDeg[e[1]]++; }
System.out.println("Initial in-degrees: " + Arrays.toString(inDeg));
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < n; i++) if (inDeg[i] == 0) q.offer(i);
List<Integer> order = new ArrayList<>();
while (!q.isEmpty()) {
int node = q.poll();
order.add(node);
System.out.println("Emit " + node + ", decrement neighbors");
for (int next : adj.get(node)) {
inDeg[next]--;
if (inDeg[next] == 0) q.offer(next);
}
}
System.out.println("Order: " + order);
}
}
Initial in-degrees: [0, 1, 1, 2]
Emit 0, decrement neighbors
Emit 1, decrement neighbors
Emit 2, decrement neighbors
Emit 3, decrement neighbors
Order: [0, 1, 2, 3]
How does cycle detection work?
If the graph has a cycle, the nodes in the cycle permanently wait on each other, never reaching zero in-degree, and are never emitted. Comparing the emitted count to the total node count detects the cycle.
package com.bank.graph;
import java.util.*;
public class CycleDetection {
public static void main(String[] args) {
int n = 3;
int[][] edges = {{0,1}, {1,2}, {2,0}}; // cycle: 0->1->2->0
int[] inDeg = new int[n];
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] e : edges) { adj.get(e[0]).add(e[1]); inDeg[e[1]]++; }
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < n; i++) if (inDeg[i] == 0) q.offer(i);
int emitted = 0;
while (!q.isEmpty()) { q.poll(); emitted++; }
System.out.println("Emitted: " + emitted + " of " + n);
System.out.println(emitted < n ? "CYCLE DETECTED" : "No cycle");
}
}
Emitted: 0 of 3
CYCLE DETECTED
What is the DFS alternative?
The depth-first approach explores each node recursively, pushing it onto a stack after all its descendants are visited (post-order). Cycles are detected by marking nodes as "in-progress"; revisiting an in-progress node means there is a cycle.
package com.bank.graph;
import java.util.*;
public class DFSTopSort {
static boolean dfs(int node, List<List<Integer>> adj,
int[] state, Deque<Integer> stack) {
state[node] = 1; // in-progress
for (int next : adj.get(node)) {
if (state[next] == 1) return false; // cycle
if (state[next] == 0 && !dfs(next, adj, state, stack)) return false;
}
state[node] = 2; // done
stack.push(node);
return true;
}
public static void main(String[] args) {
int n = 4;
int[][] edges = {{0,1}, {0,2}, {1,3}, {2,3}};
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] e : edges) adj.get(e[0]).add(e[1]);
int[] state = new int[n]; // 0=unvisited, 1=in-progress, 2=done
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
if (state[i] == 0 && !dfs(i, adj, state, stack)) {
System.out.println("Cycle!"); return;
}
}
System.out.println("DFS order: " + stack);
}
}
DFS order: [0, 2, 1, 3]
How do Kahn's and DFS compare?
| Feature | Kahn's (BFS) | DFS post-order |
|---|---|---|
| Approach | In-degree queue | Recursion + stack |
| Cycle detection | Emitted count < n | Revisit in-progress node |
| Output | Nodes in topological order | Reverse post-order |
| Space | O(V) queue + in-degree | O(V) recursion stack |
| Preference | Explicit, easy to reason about | Natural for recursive problems |
What is the time and space complexity?
| Metric | Value |
|---|---|
| Time | O(V + E) |
| Space | O(V + E) for adjacency list |
Where is topological sort used in production?
- Topological sort appears in many production systems:
- Build systems ordering compilation tasks.
- Task schedulers resolving dependencies.
- Spring resolving bean creation order.
- Database migration tools ordering scripts.
- Package managers resolving install order.
package com.bank.graph;
public class RealWorldUses {
public static void main(String[] args) {
System.out.println("Topological sort in production:");
System.out.println(" - Maven/Gradle: compile dependencies before dependents");
System.out.println(" - Spring: create beans in dependency order");
System.out.println(" - Flyway: run migrations in version order");
System.out.println(" - Banking: onboard product steps in prerequisite order");
}
}
Topological sort in production:
- Maven/Gradle: compile dependencies before dependents
- Spring: create beans in dependency order
- Flyway: run migrations in version order
- Banking: onboard product steps in prerequisite order
How is this applied at the National Bank of India?
The product-onboarding workflow engine runs dependent steps like opening the ledger before posting the opening balance. The planner computes a valid execution order using Kahn's algorithm, and crucially detects a misconfigured dependency cycle before execution begins, preventing deadlocks at runtime.
package com.bank.graph;
import java.util.*;
public class OnboardingWorkflow {
public static void main(String[] args) {
String[] steps = {
"Open Ledger", // 0
"KYC Verification", // 1
"Create Account", // 2
"Post Opening Balance",// 3
"Issue Debit Card", // 4
"Send Welcome Kit" // 5
};
int[][] deps = {{0,2}, {1,2}, {2,3}, {2,4}, {3,5}, {4,5}};
// Kahn's sort
int n = steps.length;
int[] inDeg = new int[n];
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] d : deps) { adj.get(d[0]).add(d[1]); inDeg[d[1]]++; }
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < n; i++) if (inDeg[i] == 0) q.offer(i);
System.out.println("Execution order:");
int count = 0;
while (!q.isEmpty()) {
int s = q.poll(); count++;
System.out.println(" " + count + ". " + steps[s]);
for (int next : adj.get(s)) if (--inDeg[next] == 0) q.offer(next);
}
System.out.println(count < n ? "CYCLE: cannot onboard!" : "All steps scheduled.");
}
}
Execution order:
1. Open Ledger
2. KYC Verification
3. Create Account
4. Post Opening Balance
5. Issue Debit Card
6. Send Welcome Kit
All steps scheduled.
What are common interview follow-up questions?
- Interviewers often extend this problem:
- Can you find all valid topological orderings? (Backtracking with in-degree.)
- What if you need the shortest path in a DAG? (Topological sort + DP.)
- How do you detect which nodes are in the cycle? (Nodes with non-zero in-degree after Kahn's.)
Visual Overview
Kahn's Algorithm Flow:
Step Dependencies (DAG):
Open Ledger ──► Create Account ──► Post Balance ──► Send Email
│ ▲
└──► Issue Card ───────────────────┘
In-degrees: Open=0 Create=1 Post=1 Card=1 Email=2
Round 1: Emit Open (in-deg 0), decrement Create
Round 2: Emit Create (now 0), decrement Post, Card
Round 3: Emit Post (now 0), decrement Email
Round 4: Emit Card (now 0), decrement Email
Round 5: Emit Email (now 0)
Order: Open -> Create -> Post -> Card -> Email
All 5 emitted -> no cycle.
Key Takeaway
A topological sort of a directed acyclic graph produces a linear ordering where every edge points from an earlier node to a later one. It only exists if the graph has no cycle. Kahn's algorithm computes it by tracking in-degrees, seeding a queue with zero-in-degree nodes, and repeatedly emitting and decrementing. If fewer than all nodes are emitted, a cycle exists.
The DFS alternative explores descendants first and pushes nodes onto a stack in post-order, detecting cycles via an in-progress marker. Both run in O(V + E) time. Kahn's is preferred for its explicit in-degree model and natural cycle count.
In a banking system at the National Bank of India, the product-onboarding workflow engine uses topological sort to schedule dependent steps like opening the ledger before posting the opening balance. Crucially, it detects misconfigured dependency cycles before execution, preventing deadlocks.
This same algorithm underpins build systems, task schedulers, Spring bean creation order, and migration tools, making it one of the most practically used graph algorithms in production software.
Remember one sentence: Kahn's algorithm emits zero-in-degree nodes and decrements neighbors, producing a valid task order or detecting a cycle if some nodes can never be emitted.
---