Topological Sort

1. Introduction: The Prerequisite Chain

Imagine you are enrolling in university classes. You want to take "Machine Learning" (Course 4). But to take it, you first need "Calculus" (Course 1) and "Linear Algebra" (Course 2). And to take "Linear Algebra", you need "Basic Math" (Course 0).

In what order should you take these classes? [0, 1, 2, 4] or [1, 0, 2, 4]? Both are valid! This problem of finding a linear execution order based on prerequisites is solved using Topological Sorting.

A Topological Sort applies exclusively to Directed Acyclic Graphs (DAGs).

• Directed: Edges have a one-way direction (A must come before B).
• Acyclic: There are no loops (If A requires B, and B requires A, you can never graduate!).

2. Core Concept: Kahn's Algorithm (BFS)

The most intuitive way to solve Topological Sort is Kahn's Algorithm, which uses Breadth-First Search (BFS) and tracks the In-Degree of every node.

• In-Degree: The number of edges pointing into a node (i.e., how many prerequisites it has).
• The Logic: If a node has an In-Degree of 0, it has no prerequisites! We can take this class immediately. Once we take the class, we "remove" it from the graph. By doing so, we decrease the In-Degree of all classes that depended on it. If any of those classes drop to an In-Degree of 0, we can take them next!

3. Advanced Code Example: Course Schedule (Kahn's Algorithm)

Problem Statement: (LeetCode 207) There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [a, b] indicates that you must take course b first if you want to take course a. Return true if you can finish all courses. Otherwise, return false.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class CourseSchedule {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 1. Build Adjacency List and In-Degree array
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
        
        int[] inDegree = new int[numCourses];
        
        for (int[] pre : prerequisites) {
            int course = pre[0];
            int prereq = pre[1];
            adj.get(prereq).add(course); // Directed edge: prereq -> course
            inDegree[course]++;
        }
        
        // 2. Find all starting points (In-Degree == 0)
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }
        
        // 3. BFS Traversal
        int coursesTaken = 0;
        
        while (!queue.isEmpty()) {
            int current = queue.poll();
            coursesTaken++; // We successfully took a course
            
            // "Remove" this course by decrementing the dependencies of its neighbors
            for (int neighbor : adj.get(current)) {
                inDegree[neighbor]--;
                
                // If a neighbor now has 0 prerequisites, add it to the queue!
                if (inDegree[neighbor] == 0) {
                    queue.offer(neighbor);
                }
            }
        }
        
        // 4. Cycle Detection
        // If we didn't take all the courses, there MUST be a cycle (a deadlock)!
        return coursesTaken == numCourses;
    }
}

Complexity Analysis:

• Time Complexity: $O(V + E)$ where $V$ is vertices (courses) and $E$ is edges (prerequisites). We visit every node and edge exactly once.
• Space Complexity: $O(V + E)$ for the adjacency list and queue.

4. Advanced Code Example: Course Schedule II (DFS)

What if the interviewer explicitly asks for a DFS solution? The Insight: If we perform a standard DFS down to the deepest node (the one with no outbound edges), that node must be the last course to take. As the recursive call stack unwinds, we add nodes to a list. Reversing that list gives us the valid Topological order! To detect cycles, we need 3 states for visited nodes: UNVISITED (0), VISITING (1) (currently in our recursive stack), and VISITED (2) (fully processed).

import java.util.ArrayList;
import java.util.List;

public class CourseScheduleDFS {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
        for (int[] pre : prerequisites) {
            adj.get(pre[1]).add(pre[0]);
        }
        
        int[] state = new int[numCourses]; // 0 = unvisited, 1 = visiting, 2 = visited
        List<Integer> topologicalOrder = new ArrayList<>();
        
        // We must check every node in case the graph is disconnected
        for (int i = 0; i < numCourses; i++) {
            if (state[i] == 0) {
                // If DFS detects a cycle, return an empty array
                if (hasCycle(i, adj, state, topologicalOrder)) {
                    return new int[0];
                }
            }
        }
        
        // Reverse the post-order result to get the Topological Sort
        int[] result = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            result[i] = topologicalOrder.get(numCourses - 1 - i);
        }
        return result;
    }
    
    private boolean hasCycle(int node, List<List<Integer>> adj, int[] state, List<Integer> order) {
        state[node] = 1; // Mark as CURRENTLY visiting
        
        for (int neighbor : adj.get(node)) {
            if (state[neighbor] == 1) {
                return true; // We hit a node currently in our recursive stack! Cycle detected!
            }
            if (state[neighbor] == 0) {
                if (hasCycle(neighbor, adj, state, order)) return true;
            }
        }
        
        state[node] = 2; // Mark as FULLY visited
        order.add(node); // POST-ORDER: Add to list only after all neighbors are processed
        return false;
    }
}

5. Common Mistakes Beginners Make

1. Getting the Edge Direction Backwards

   • The Mistake: adj.get(course).add(prereq)
   • Why it's wrong: The edge must flow from dependency to dependent. If A must be taken before B, the edge is A -> B. If you flip it, your In-Degrees will be backwards, and your algorithm will return the exact reverse order.

2. Using a boolean[] visited array for DFS Cycle Detection

   • The Mistake: if (visited[neighbor]) return true;
   • Why it's wrong: In a Directed Graph, crossing paths does NOT mean a cycle! A -> B -> D and A -> C -> D is a perfectly valid DAG. If B marks D as visited, when C reaches D, it will incorrectly flag a cycle. You MUST use the 3-state array (Visiting vs Visited) to only flag back-edges that form loops.

3. Forgetting Disconnected Graphs

   • The Mistake: Starting the DFS at node 0 and assuming it reaches everything.
   • Why it's wrong: You could have Course 0 -> Course 1 and a completely unrelated Course 2 -> Course 3. A single DFS from 0 will never check 2. You must wrap the DFS inside a for loop that iterates over all nodes.

6. Interview Q&A

Q1: Which is better: Kahn's Algorithm (BFS) or DFS? Answer: Both are $O(V + E)$. Kahn's (BFS) is much easier to write and inherently tracks cycles perfectly just by checking coursesTaken == numCourses. DFS is trickier due to the 3-state cycle detection and manual list reversal. In an interview, default to Kahn's unless forced.

Q2: Can there be multiple valid Topological Sorts for a single graph? Answer: Yes! If two courses have an In-Degree of 0 simultaneously, the Queue can pop them in any order. If a problem asks for the "Lexicographically smallest" order (e.g. Alien Dictionary), you simply replace the Queue in Kahn's algorithm with a PriorityQueue (Min-Heap)!

7. Practice Problems

1. Course Schedule (LeetCode 207)
   • Goal: Kahn's cycle detection.
2. Course Schedule II (LeetCode 210)
   • Goal: Kahn's / DFS full order generation.
3. Alien Dictionary (LeetCode 269 - Hard)
   • Hint: Build the graph yourself by comparing adjacent words to find letter dependencies, then run Kahn's. This is arguably the most famous Topological Sort problem in the world.

8. Summary

• Prerequisites = Topological Sort.
• DAG: Only works on Directed Acyclic Graphs. Cycles break it.
• Kahn's (BFS): Uses an inDegree array. Push nodes with inDegree == 0. Decrement neighbors. Count nodesVisited to detect cycles.
• DFS: Post-order traversal. Reverse the output list. Requires a 3-state visited array (0=Unvisited, 1=Visiting, 2=Visited) to detect cycles.

Advanced Code Implementations

// Example: Topological Sort using Kahn's Algorithm (BFS)
import java.util.*;

public class CourseSchedule {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adj = new ArrayList<>();
        for(int i=0; i<numCourses; i++) adj.add(new ArrayList<>());
        int[] indegree = new int[numCourses];
        
        for (int[] pre : prerequisites) {
            adj.get(pre[1]).add(pre[0]);
            indegree[pre[0]]++;
        }
        
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) q.offer(i);
        }
        
        int count = 0;
        while (!q.isEmpty()) {
            int node = q.poll();
            count++;
            for (int neighbor : adj.get(node)) {
                indegree[neighbor]--;
                if (indegree[neighbor] == 0) {
                    q.offer(neighbor);
                }
            }
        }
        return count == numCourses;
    }
}

// Example: Topological Sort using DFS
import java.util.*;

public class TopoSortDFS {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adj = new ArrayList<>();
        for(int i=0; i<numCourses; i++) adj.add(new ArrayList<>());
        for (int[] pre : prerequisites) adj.get(pre[1]).add(pre[0]);
        
        int[] visited = new int[numCourses]; // 0: unvisited, 1: visiting, 2: visited
        Stack<Integer> stack = new Stack<>();
        
        for (int i = 0; i < numCourses; i++) {
            if (visited[i] == 0 && hasCycle(adj, visited, i, stack)) {
                return new int[0];
            }
        }
        
        int[] res = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            res[i] = stack.pop();
        }
        return res;
    }
    
    private boolean hasCycle(List<List<Integer>> adj, int[] visited, int node, Stack<Integer> stack) {
        visited[node] = 1;
        for (int neighbor : adj.get(node)) {
            if (visited[neighbor] == 1) return true;
            if (visited[neighbor] == 0 && hasCycle(adj, visited, neighbor, stack)) return true;
        }
        visited[node] = 2;
        stack.push(node);
        return false;
    }
}

Expanded Interview Q&A

Q1: What kind of graphs can be topologically sorted?

Answer: Only Directed Acyclic Graphs (DAGs). If there is a cycle, a valid topological ordering does not exist.

Q2: What is the concept of "in-degree" in Kahn's algorithm?

Answer: In-degree is the number of incoming edges to a node. Nodes with an in-degree of 0 have no dependencies and can be processed immediately.

Q3: How does DFS find the topological order?

Answer: By pushing a node to a stack after all its descendants have been visited. Popping the stack gives the topological order.

Q4: How is topological sorting used in the real world?

Answer: For dependency resolution (like npm packages), build systems (make, gradle), and task scheduling.

Q5: Can there be more than one valid topological sort for a DAG?

Answer: Yes. If at any point the queue in Kahn's algorithm has more than one node, there are multiple valid topological sortings.