Topological Sort
Problem link: https://www.geeksforgeeks.org/problems/topological-sort/1
Problem Statement
Given a Directed Acyclic Graph (DAG), find a linear ordering of vertices such that for every directed edge u -> v, u appears before v.
Input
Adjacency list adj and vertex count V.
Output
Valid linear ordering array.
[ 5, 4, 2, 3, 1, 0 ]| | | | | |Order of Execution
Example
Input: V = 6, adj = [[], [], [3], [1], [0,1], [0,2]] Output: [5, 4, 2, 3, 1, 0]
Explanation
Nodes with no incoming edges (5, 4) must come first. Node 0 depends on 4 and 5, so it appears later.
Brute Force
Intuition
Kahn's Algorithm (BFS)
Think of it as 'removing dependencies'. We find nodes that don't depend on anything (Indegree 0), process them, and then 'break' their outgoing edges to see which nodes become independent next.
Approach
- Fill an array
indegree[]by counting incoming edges for each node. - Add all nodes with
indegree == 0to a Queue. - While Queue is not empty:
- Poll node
u, add to result. - For each neighbor
v, decrementindegree[v]. - If
indegree[v]hits 0, add to Queue.
- Poll node
Dry Run
Initial Indegrees: {0:2, 1:2, 2:1, 3:1, 4:0, 5:0}
- Queue: [5, 4]
- Pop 5: Result [5], Decr 2 and 0. (2's Indegree becomes 0)
- Queue: [4, 2]
- Pop 4: Result [5, 4], Decr 0 and 1.
- Pop 2: Result [5, 4, 2], Decr 3. (3's Indegree becomes 0)...
Code (Java)
static int[] topoSortBFS(int V, ArrayList<ArrayList<Integer>> adj) {
int[] indegree = new int[V];
for (int i = 0; i < V; i++) {
for (int it : adj.get(i)) indegree[it]++;
}
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < V; i++) {
if (indegree[i] == 0) q.add(i);
}
int[] topo = new int[V];
int i = 0;
while (!q.isEmpty()) {
int node = q.poll();
topo[i++] = node;
for (int it : adj.get(node)) {
indegree[it]--;
if (indegree[it] == 0) q.add(it);
}
}
return topo;
}
Complexity Analysis
Each vertex and edge is processed once. Space is used for the indegree array and queue.
Optimal Solution
Intuition
DFS with Stack
This is 'backwards logic'. We dive as deep as possible into a dependency chain. When we hit a node with no outgoing edges (or all neighbors visited), we know it can safely go last. We push it to a stack, and the stack naturally reverses this 'last-to-first' order into 'first-to-last'.
Approach
- Use a
visitedarray and aStack. - Start DFS from an unvisited node.
- In DFS: Visit all unvisited neighbors recursively.
- Key Step: After all neighbors are visited, push the current node to the Stack.
- Result is the Stack popped from top to bottom.
Dry Run
Start DFS(5):
- Visit 2 -> Visit 3 -> Visit 1 (No neighbors)
- Push 1 to Stack. Backtrack to 3.
- Push 3 to Stack. Backtrack to 2.
- Push 2 to Stack. Backtrack to 5.
- 5 has neighbor 0 -> Visit 0 (No neighbors left)
- Push 0, then Push 5. Stack Top-Down: [5, 4, 2, 3, 1, 0]
Code (Java)
private static void dfs(int node, int[] vis, Stack<Integer> st, ArrayList<ArrayList<Integer>> adj) {
vis[node] = 1;
for (int it : adj.get(node)) {
if (vis[it] == 0) dfs(it, vis, st, adj);
}
st.push(node);
}
static int[] topoSortDFS(int V, ArrayList<ArrayList<Integer>> adj) {
int[] vis = new int[V];
Stack<Integer> st = new Stack<>();
for (int i = 0; i < V; i++) {
if (vis[i] == 0) dfs(i, vis, st, adj);
}
int[] topo = new int[V];
int i = 0;
while (!st.isEmpty()) topo[i++] = st.pop();
return topo;
}
Complexity Analysis
Time is linear as each node and edge is visited once. Space is V for the stack and recursion depth.
Quick Revision (Brute Force)
- BFS / Kahn's
- Uses Indegree
- Result size check detects cycles
Quick Revision (Optimal)
- DFS + Stack
- Push to stack AFTER recursion
- Reverse stack for result