Topological Sort

What is Topological Sort?

Topological Sort is a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge $u \rightarrow v$, vertex $u$ comes before $v$ in the ordering.

Typical Use Cases:

• Task scheduling (Project Management/PERT charts).
• Resolving module/dependency builds in compilers (e.g., make).
• Determining course prerequisites.
• Serialization of data structures with references.

Crucial Rule: If a graph contains a cycle, a topological sort is impossible (circular dependency means no task can start first).

Kahn's Algorithm (BFS Method)

Core Logic: Repeatedly find nodes with an in-degree of 0 (no remaining prerequisites), add them to the result, and remove their outgoing edges (decrement neighbors' in-degrees).

List<Integer> topologicalSort(int n, int[][] edges) {
    List<List<Integer>> adjacency = new ArrayList<>();
    int[] inDegree = new int[n];
    for (int i = 0; i < n; i++) adjacency.add(new ArrayList<>());
    
    // 1. Build graph and track in-degrees
    for (int[] edge : edges) {
        adjacency.get(edge[0]).add(edge[1]);
        inDegree[edge[1]]++;
    }
    
    // 2. Queue all nodes with NO prerequisites (in-degree 0)
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) queue.offer(i);
    }
    
    List<Integer> result = new ArrayList<>();
    // 3. Process the queue
    while (!queue.isEmpty()) {
        int node = queue.poll();
        result.add(node);
        
        for (int neighbor : adjacency.get(node)) {
            // Decrement in-degree of neighbors
            if (--inDegree[neighbor] == 0) {
                queue.offer(neighbor);
            }
        }
    }
    
    // Cycle check: If result size < n, a cycle prevented some nodes from ever reaching 0 in-degree.
    return result.size() == n ? result : new ArrayList<>();
}

Complexity: O(V + E) time, O(V + E) space.

DFS-Based Topological Sort

Logic: A node is added to a stack after all its descendants have been fully explored. Reversing this stack (or simply pushing to a linked list's head) gives the topological order.

We must use Three-Color Marking to detect cycles.

int[] color;      // 0=Unvisited, 1=Visiting (In stack), 2=Visited
Deque<Integer> stack;
boolean isCyclic = false;

void dfs(List<List<Integer>> adj, int node) {
    if (isCyclic) return;
    
    color[node] = 1; // Mark as Visiting
    for (int neighbor : adj.get(node)) {
        if (color[neighbor] == 1) { // Node already in current recursion stack -> Cycle!
            isCyclic = true;
            return;
        }
        if (color[neighbor] == 0) {
            dfs(adj, neighbor);
        }
    }
    color[node] = 2; // Finished
    stack.push(node); // All children explored, add to stack
}

List<Integer> topologicalSortDFS(int n, int[][] edges) {
    List<List<Integer>> adj = new ArrayList<>();
    // ... initialize adjacency list ...
    
    color = new int[n];
    stack = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        if (color[i] == 0) dfs(adj, i);
    }
    
    if (isCyclic) return new ArrayList<>();
    return new ArrayList<>(stack);
}

High-Frequency Problem: Course Schedule II (LeetCode 210)

Return a possible order of courses given numCourses and prerequisites[a, b] (where $b$ is a prerequisite of $a$).

int[] findOrder(int numCourses, int[][] prerequisites) {
    List<List<Integer>> adj = new ArrayList<>();
    int[] inDegrees = new int[numCourses];
    for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
    
    for (int[] p : prerequisites) {
        adj.get(p[1]).add(p[0]); // Order: b -> a
        inDegrees[p[0]]++;
    }
    
    Queue<Integer> q = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) if (inDegrees[i] == 0) q.offer(i);
    
    int[] order = new int[numCourses];
    int idx = 0;
    while (!q.isEmpty()) {
        int u = q.poll();
        order[idx++] = u;
        for (int v : adj.get(u)) {
            if (--inDegrees[v] == 0) q.offer(v);
        }
    }
    
    return idx == numCourses ? order : new int[0];
}

Comparison Summary