Topological Sort

What is Topological Sort?

Topological sort produces a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge u→v, vertex u comes before v in the ordering.

DAG Example:                 Valid Topological Orders:
  0 → 1 → 3                  [0, 1, 2, 3, 4]
  0 → 2 → 3                  [0, 2, 1, 3, 4]
      ↓                       [2, 0, 1, 3, 4]
      4                       (Multiple valid orderings possible)

Key Concepts

• Prerequisite: Edge u→v means u must come before v
• DAG: Directed Acyclic Graph (no cycles allowed)
• In-degree: Number of incoming edges to a vertex
• Source: Vertex with in-degree 0 (no prerequisites)

When to Use Topological Sort

Two Main Approaches

1. DFS-based: Use DFS to produce reverse post-order
2. Kahn's Algorithm (BFS-based): Use in-degree and queue

Both run in O(V + E) time.

Kahn's Algorithm (BFS-based)

import java.util.*;

public class TopologicalSort {
    
    // Kahn's Algorithm
    public int[] kahnTopoSort(int n, int[][] edges) {
        // Build graph and compute in-degrees
        Map<Integer, List<Integer>> graph = new HashMap<>();
        int[] inDegree = new int[n];
        
        for (int i = 0; i < n; i++) {
            graph.put(i, new ArrayList<>());
        }
        
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            inDegree[edge[1]]++;
        }
        
        // Add all sources (in-degree 0) to queue
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }
        
        int[] result = new int[n];
        int index = 0;
        
        while (!queue.isEmpty()) {
            int node = queue.poll();
            result[index++] = node;
            
            for (int neighbor : graph.get(node)) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) {
                    queue.offer(neighbor);
                }
            }
        }
        
        // Check for cycle
        if (index != n) {
            return new int[]{}; // Cycle exists
        }
        
        return result;
    }
    
    // Returns empty array if cycle exists
    // Returns topological order otherwise
}

DFS-based Topological Sort

public int[] dfsTopoSort(int n, int[][] edges) {
    Map<Integer, List<Integer>> graph = new HashMap<>();
    for (int i = 0; i < n; i++) {
        graph.put(i, new ArrayList<>());
    }
    for (int[] edge : edges) {
        graph.get(edge[0]).add(edge[1]);
    }
    
    int[] color = new int[n]; // 0: unvisited, 1: visiting, 2: visited
    Stack<Integer> stack = new Stack<>();
    
    for (int i = 0; i < n; i++) {
        if (color[i] == 0) {
            if (dfsHelper(graph, i, color, stack)) {
                return new int[]{}; // Cycle detected
            }
        }
    }
    
    int[] result = new int[n];
    for (int i = 0; i < n; i++) {
        result[i] = stack.pop();
    }
    return result;
}

private boolean dfsHelper(Map<Integer, List<Integer>> graph, int node, 
                         int[] color, Stack<Integer> stack) {
    color[node] = 1; // Mark as visiting
    
    for (int neighbor : graph.get(node)) {
        if (color[neighbor] == 1) {
            return true; // Cycle detected
        }
        if (color[neighbor] == 0) {
            if (dfsHelper(graph, neighbor, color, stack)) {
                return true;
            }
        }
    }
    
    color[node] = 2; // Mark as visited
    stack.push(node);
    return false;
}

Course Schedule Problem

// Can finish all courses?
public boolean canFinish(int numCourses, int[][] prerequisites) {
    return kahnTopoSort(numCourses, prerequisites).length > 0;
}

// Return course ordering
public int[] findOrder(int numCourses, int[][] prerequisites) {
    return kahnTopoSort(numCourses, prerequisites);
}

Complexity Comparison

Interview Tips

1. Always check for cycles - if cycle exists, no valid ordering
2. Kahn's is easier to implement and naturally detects cycles
3. DFS gives reverse post-order - remember to reverse the result
4. Multiple valid orderings - any valid order is acceptable
5. Edge cases: single node, no edges, all edges in one direction