Implement Topological Sort
Problem Statement
Given a Directed Acyclic Graph (DAG) with V vertices and E edges, find a topological ordering of the vertices. A topological ordering is a linear ordering where for every directed edge (u, v), vertex u comes before vertex v.
Example:
- Input:
V = 6, Edges = [[5,2],[5,0],[4,0],[4,1],[2,3],[3,1]] - Output:
[5, 4, 2, 3, 1, 0](one valid ordering)
Noob-Friendly Explanation
Imagine you're getting dressed. You can't put on shoes before socks, and you can't put on a shirt before an undershirt. Some items depend on others. Topological sort arranges tasks so that every task comes after the tasks it depends on.
For example: Undershirt → Shirt → Jacket, Underwear → Pants → Shoes. A valid topological order is: Undershirt, Underwear, Shirt, Pants, Jacket, Shoes.
This only works on DAGs (no cycles). If there's a cycle (A depends on B, B depends on A), it's impossible!
Approach 1: Brute Force (DFS-Based)
Intuition
Use DFS. The idea: after visiting all descendants of a node (all nodes that depend on it), push the node onto a stack. When we're done, popping from the stack gives the topological order.
Algorithm
- Build adjacency list.
- For each unvisited vertex, run DFS.
- In DFS, recursively visit all neighbors first.
- After all neighbors are processed, push the current vertex to a stack.
- Pop all elements from the stack — that's the topological order.
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class TopologicalSortDFS {
static void dfs(List<List<Integer>> adj, boolean[] visited, int node, Stack<Integer> stack) {
visited[node] = true;
for (int neighbor : adj.get(node)) {
if (!visited[neighbor]) {
dfs(adj, visited, neighbor, stack);
}
}
stack.push(node); // push after all descendants are processed
}
public static List<Integer> topologicalSort(int V, int[][] edges) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < V; i++) {
adj.add(new ArrayList<>());
}
for (int[] edge : edges) {
adj.get(edge[0]).add(edge[1]);
}
boolean[] visited = new boolean[V];
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < V; i++) {
if (!visited[i]) {
dfs(adj, visited, i, stack);
}
}
List<Integer> result = new ArrayList<>();
while (!stack.isEmpty()) {
result.add(stack.pop());
}
return result;
}
public static void main(String[] args) {
int V = 6;
int[][] edges = {{5,2},{5,0},{4,0},{4,1},{2,3},{3,1}};
System.out.println(topologicalSort(V, edges)); // [5, 4, 2, 3, 1, 0] or similar
}
}Complexity Analysis
- Time Complexity: O(V + E) — each vertex and edge is visited once.
- Space Complexity: O(V) — for visited array, stack, and recursion stack.
Approach 2: Optimal (BFS — Kahn's Algorithm)
Intuition
Use Kahn's Algorithm. Start with all vertices that have in-degree 0 (no dependencies). Process them, reduce in-degrees of their neighbors, and add newly zero-in-degree vertices. This naturally produces a topological order.
Algorithm
- Compute in-degree for each vertex.
- Add all vertices with in-degree 0 to a queue.
- While the queue is not empty: a. Dequeue a vertex, add to result. b. Reduce in-degree of all its neighbors. c. If any neighbor's in-degree becomes 0, enqueue it.
import java.util.*;
public class TopologicalSortBFS {
public static List<Integer> topologicalSort(int V, int[][] edges) {
List<List<Integer>> adj = new ArrayList<>();
int[] inDegree = new int[V];
for (int i = 0; i < V; i++) {
adj.add(new ArrayList<>());
}
for (int[] edge : edges) {
adj.get(edge[0]).add(edge[1]);
inDegree[edge[1]]++;
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < V; i++) {
if (inDegree[i] == 0) {
queue.add(i);
}
}
List<Integer> result = new ArrayList<>();
while (!queue.isEmpty()) {
int node = queue.poll();
result.add(node);
for (int neighbor : adj.get(node)) {
inDegree[neighbor]--;
if (inDegree[neighbor] == 0) {
queue.add(neighbor);
}
}
}
return result; // if result.size() != V, graph has a cycle
}
public static void main(String[] args) {
int V = 6;
int[][] edges = {{5,2},{5,0},{4,0},{4,1},{2,3},{3,1}};
System.out.println(topologicalSort(V, edges)); // [4, 5, 2, 0, 3, 1] or similar
}
}Complexity Analysis
- Time Complexity: O(V + E) — each vertex and edge is processed once.
- Space Complexity: O(V) — for the in-degree array and queue.