Topological Sort: Course Scheduling Problems

Topological Sort Basics (Kahn's Algorithm / BFS)

Add all nodes with an in-degree of 0 to a queue. For each node extracted, remove its outgoing edges; if any neighbor's in-degree drops to 0, add it to the queue.

// Generic Topological Sort Template
public int[] topoSort(int n, int[][] edges) {
    int[] inDegrees = new int[n];
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
    
    for (int[] e : edges) {
        graph.get(e[0]).add(e[1]);
        inDegrees[e[1]]++;
    }
    
    Queue<Integer> queue = new ArrayDeque<>();
    for (int i = 0; i < n; i++) if (inDegrees[i] == 0) queue.offer(i);
    
    int[] order = new int[n];
    int index = 0;
    while (!queue.isEmpty()) {
        int u = queue.poll();
        order[index++] = u;
        for (int v : graph.get(u)) {
            if (--inDegrees[v] == 0) queue.offer(v);
        }
    }
    
    // If we didn't visit all nodes, the graph must contain a cycle
    return index == n ? order : new int[0];
}

Course Schedule (LeetCode 207)

Detecting a cycle in a directed graph is equivalent to checking if a complete topological sort can be performed.

public boolean canFinish(int numCourses, int[][] prerequisites) {
    int[] inDegrees = new int[numCourses];
    List<List<Integer>> adj = new ArrayList<>();
    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 ArrayDeque<>();
    for (int i = 0; i < numCourses; i++) if (inDegrees[i] == 0) q.offer(i);
    
    int processedCount = 0;
    while (!q.isEmpty()) {
        int u = q.poll();
        processedCount++;
        for (int v : adj.get(u)) {
            if (--inDegrees[v] == 0) q.offer(v);
        }
    }
    return processedCount == numCourses;
}

Course Schedule II (LeetCode 210)

Extract the specific topological sequence (return an empty array if a cycle exists).

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

DFS Method (Three-Color Marking)

States: 0=Unvisited, 1=Visiting (In current stack), 2=Finished.

public boolean canFinishDFS(int numCourses, int[][] prerequisites) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
    for (int[] p : prerequisites) adj.get(p[1]).add(p[0]);
    
    int[] colors = new int[numCourses]; // 0: White, 1: Gray, 2: Black
    for (int i = 0; i < numCourses; i++) {
        if (colors[i] == 0 && findCycle(adj, colors, i)) return false;
    }
    return true;
}

private boolean findCycle(List<List<Integer>> adj, int[] colors, int u) {
    colors[u] = 1; // Mark as Gray
    for (int v : adj.get(u)) {
        if (colors[v] == 1) return true; // Found a Gray node -> Cycle detected
        if (colors[v] == 0 && findCycle(adj, colors, v)) return true;
    }
    colors[u] = 2; // Mark as Black
    return false;
}

Summary Comparison