L19. Topological Sort | Kahn's Algorithm (BFS) & DFS-Based Approach

Topological sorting is a fundamental graph algorithm used to establish a linear ordering of vertices in a Directed Acyclic Graph (DAG). For every directed edge $u \to v$, vertex $u$ must appear before $v$ in the ordering. This technique is crucial for solving scheduling problems, resolving build dependencies, and ordering tasks with prerequisite constraints.

1. Introduction to Topological Sort & Core Definitions

To understand Topological Sort, we must first break down the mathematical properties of the graphs it operates on. Topological sorting is only possible on Directed Acyclic Graphs (DAGs).

Key Definitions

• Directed Graph: A graph where edges have a direction, pointing from a source node to a destination node ($u \to v$).
• Acyclic Graph: A graph that contains no cycles. If you start at any node $u$ and follow the directed edges, you can never loop back to $u$.
• Topological Sort: A linear ordering of the vertices such that for every directed edge $u \to v$, node $u$ comes before node $v$ in the ordering.

Why Cycles Prevent Topological Sorting

If a graph contains a cycle (e.g., $A \to B \to C \to A$), a topological sort is mathematically impossible.

• To place $A$, we must first place $C$.
• To place $C$, we must first place $B$.
• To place $B$, we must first place $A$.

This circular dependency cannot be resolved, which is why cycle detection is intimately tied to topological sorting algorithms.

2. Real-World Analogies & Mental Hooks

Topological sorting is highly intuitive when mapped to real-world dependency resolution.

Analogy 1: College Course Prerequisites

To graduate with a Computer Science degree, you must take several courses, many of which have prerequisites:

You cannot take Algorithms (CS301) or Web Dev (CS302) without first completing Data Structures (CS201), which itself requires Intro to Programming (CS101). A topological sort provides a valid semester-by-semester schedule to complete all courses without violating any prerequisites.

Analogy 2: Getting Dressed

When getting dressed in the morning, certain items of clothing must be put on before others:

• Socks must be put on before Shoes.
• Underwear must be put on before Pants.
• Pants must be put on before Shoes.

A valid topological sort of this process is: [Underwear, Socks, Pants, Shoes].

3. DFS-Based Topological Sort (Using Stack)

The Depth-First Search (DFS) approach to topological sorting relies on backtracking. The core idea is to explore as deep as possible along a path. Once we reach a node that has no outgoing edges (or whose outgoing paths have all been fully explored), we can safely place this node at the end of our topological order.

Why Use a Stack?

In DFS, we visit nodes recursively. When a node's DFS execution is about to finish (i.e., we are backtracking from it), it means all of its dependency chains have been fully processed.

By pushing the node onto a Stack at the very end of its recursive call, we ensure that nodes with no outgoing dependencies are pushed first (sitting at the bottom of the stack). Nodes that must be executed first are pushed last (sitting at the top of the stack). Popping from the stack at the end naturally reverses this order, yielding the correct topological sequence.

Step-by-Step Dry Run

Consider the following DAG:

• Edges: 5 -> 0, 5 -> 2, 4 -> 0, 4 -> 1, 2 -> 3, 3 -> 1
• Visited Array: [false, false, false, false, false, false]
• Stack: []

Execution Trace:

1. Start DFS from unvisited node 0.
   • Node 0 has no outgoing edges.
   • Mark 0 as visited.
   • Push 0 to Stack. Stack: [0]
2. Next unvisited node is 1.
   • Node 1 has no outgoing edges.
   • Mark 1 as visited.
   • Push 1 to Stack. Stack: [0, 1]
3. Next unvisited node is 2.
   • Mark 2 as visited.
   • Traverse neighbor 3.
     • Mark 3 as visited.
     • Traverse neighbor 1 (already visited, skip).
     • No more neighbors for 3. Push 3 to Stack. Stack: [0, 1, 3]
   • No more neighbors for 2. Push 2 to Stack. Stack: [0, 1, 3, 2]
4. Next unvisited node is 3 (already visited, skip).
5. Next unvisited node is 4.
   • Mark 4 as visited.
   • Traverse neighbor 0 (already visited, skip).
   • Traverse neighbor 1 (already visited, skip).
   • No more neighbors for 4. Push 4 to Stack. Stack: [0, 1, 3, 2, 4]
6. Next unvisited node is 5.
   • Mark 5 as visited.
   • Traverse neighbor 0 (already visited, skip).
   • Traverse neighbor 2 (already visited, skip).
   • No more neighbors for 5. Push 5 to Stack. Stack: [0, 1, 3, 2, 4, 5]

Final Order:

Pop all elements from the Stack: 5 -> 4 -> 2 -> 3 -> 1 -> 0

4. DFS Implementation (Code Walkthrough)

Here is the complete, production-grade implementation of the DFS-based Topological Sort.

Java Implementation

import java.util.*;

public class TopologicalSortDFS {
    
    // Helper DFS function
    private static void dfs(int node, ArrayList<ArrayList<Integer>> adj, 
                            boolean[] visited, Stack<Integer> stack) {
        visited[node] = true;
        
        // Traverse all adjacent vertices
        for (int neighbor : adj.get(node)) {
            if (!visited[neighbor]) {
                dfs(neighbor, adj, visited, stack);
            }
        }
        
        // Push current node to stack after all its neighbors are processed
        stack.push(node);
    }
    
    // Function to return list containing vertices in Topological order
    public static int[] topoSort(int V, ArrayList<ArrayList<Integer>> adj) {
        boolean[] visited = new boolean[V];
        Stack<Integer> stack = new Stack<>();
        
        // Call DFS for all unvisited components to handle disconnected graphs
        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                dfs(i, adj, visited, stack);
            }
        }
        
        // Pop elements from stack and store in result array
        int[] result = new int[V];
        int index = 0;
        while (!stack.isEmpty()) {
            result[index++] = stack.pop();
        }
        
        return result;
    }

    public static void main(String[] args) {
        int V = 6;
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<>());
        }
        
        // Add edges
        adj.get(5).add(2);
        adj.get(5).add(0);
        adj.get(4).add(0);
        adj.get(4).add(1);
        adj.get(2).add(3);
        adj.get(3).add(1);
        
        int[] topoOrder = topoSort(V, adj);
        System.out.println("Topological Sort (DFS): " + Arrays.toString(topoOrder));
    }
}

Python Implementation

def topo_sort_dfs(v: int, adj: list[list[int]]) -> list[int]:
    visited = [False] * v
    stack = []

    def dfs(node: int):
        visited[node] = True
        for neighbor in adj[node]:
            if not visited[neighbor]:
                dfs(neighbor)
        # Push to stack on backtracking
        stack.append(node)

    # Loop through all nodes to handle disconnected components
    for i in range(v):
        if not visited[i]:
            dfs(i)

    # Reverse the stack to get the correct topological order
    return stack[::-1]

# Example Usage
if __name__ == "__main__":
    V = 6
    adj = [[] for _ in range(V)]
    adj[5].append(2)
    adj[5].append(0)
    adj[4].append(0)
    adj[4].append(1)
    adj[2].append(3)
    adj[3].append(1)

    print("Topological Sort (DFS):", topo_sort_dfs(V, adj))

Complexity Analysis

• Time Complexity: $\mathcal{O}(V + E)$ where $V$ is the number of vertices and $E$ is the number of edges. We visit every vertex exactly once and traverse all its outgoing edges.
• Space Complexity: $\mathcal{O}(V)$ auxiliary space for the recursion stack, the visited array, and the output stack.

5. BFS-Based Topological Sort (Kahn's Algorithm)

Kahn's Algorithm is an elegant, queue-based BFS approach to topological sorting. It is built around the concept of In-degrees.

What is In-degree?

• In-degree: The number of incoming directed edges pointing to a node.
• If a node has an in-degree of 0, it means there are no prerequisites or dependencies for this node. We can process it immediately.

Core Algorithm Steps

1. Calculate In-degrees: Compute the in-degree of every vertex in the graph.
2. Initialize Queue: Insert all vertices with an in-degree of 0 into a queue.
3. Process Queue:
   • De-queue a vertex $u$ and add it to our topological order list.
   • For each outgoing edge $u \to v$, decrement the in-degree of neighbor $v$ by 1 (simulating the "removal" of node $u$ and its outgoing dependencies from the graph).
   • If the in-degree of $v$ drops to 0, push $v$ into the queue.
4. Check for Cycles: If the number of nodes in the topological order is less than $V$, the graph contains a cycle (and thus no valid topological sort exists).

6. Kahn's Algorithm Dry Run & Visual Workflow

Let's trace Kahn's Algorithm using the same graph:

Step 1: Calculate In-degrees

• 0: 2 (from 5, 4)
• 1: 2 (from 3, 4)
• 2: 1 (from 5)
• 3: 1 (from 2)
• 4: 0
• 5: 0

Step 2: Initialize Queue

Queue contains all nodes with in-degree = 0: Queue = [4, 5]

Step 3: Process Queue

Final Topological Order:

[4, 5, 0, 2, 3, 1] (Note: This is also a valid topological sort! Multiple valid orderings can exist for a single DAG).

7. Kahn's Algorithm Implementation (Code Walkthrough)

Java Implementation

import java.util.*;

public class KahnsAlgorithm {
    
    public static int[] topoSort(int V, ArrayList<ArrayList<Integer>> adj) {
        int[] inDegree = new int[V];
        
        // Step 1: Calculate In-degrees
        for (int i = 0; i < V; i++) {
            for (int neighbor : adj.get(i)) {
                inDegree[neighbor]++;
            }
        }
        
        // Step 2: Queue all nodes with in-degree 0
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < V; i++) {
            if (inDegree[i] == 0) {
                queue.add(i);
            }
        }
        
        int[] topoOrder = new int[V];
        int index = 0;
        
        // Step 3: Process Queue
        while (!queue.isEmpty()) {
            int curr = queue.poll();
            topoOrder[index++] = curr;
            
            for (int neighbor : adj.get(curr)) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) {
                    queue.add(neighbor);
                }
            }
        }
        
        // Step 4: Check for cycle
        if (index != V) {
            System.out.println("Cycle detected! No valid topological sort exists.");
            return new int[0];
        }
        
        return topoOrder;
    }

    public static void main(String[] args) {
        int V = 6;
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<>());
        }
        
        adj.get(5).add(2);
        adj.get(5).add(0);
        adj.get(4).add(0);
        adj.get(4).add(1);
        adj.get(2).add(3);
        adj.get(3).add(1);
        
        int[] result = topoSort(V, adj);
        System.out.println("Topological Sort (Kahn's): " + Arrays.toString(result));
    }
}

Python Implementation

from collections import deque

def topo_sort_kahns(v: int, adj: list[list[int]]) -> list[int]:
    in_degree = [0] * v
    
    # Step 1: Calculate In-degrees
    for i in range(v):
        for neighbor in adj[i]:
            in_degree[neighbor] += 1
            
    # Step 2: Queue all nodes with in-degree 0
    queue = deque([i for i in range(v) if in_degree[i] == 0])
    
    topo_order = []
    
    # Step 3: Process Queue
    while queue:
        curr = queue.popleft()
        topo_order.append(curr)
        
        for neighbor in adj[curr]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
                
    # Step 4: Check for cycle
    if len(topo_order) != v:
        print("Cycle detected! No valid topological sort exists.")
        return []
        
    return topo_order

# Example Usage
if __name__ == "__main__":
    V = 6
    adj = [[] for _ in range(V)]
    adj[5].append(2)
    adj[5].append(0)
    adj[4].append(0)
    adj[4].append(1)
    adj[2].append(3)
    adj[3].append(1)

    print("Topological Sort (Kahn's):", topo_sort_kahns(V, adj))

Complexity Analysis

• Time Complexity: $\mathcal{O}(V + E)$ where $V$ is the number of vertices and $E$ is the number of edges.
• Space Complexity: $\mathcal{O}(V)$ to store the in-degree array and the queue.

8. Cycle Detection using Topological Sort

One of the most powerful applications of topological sorting is cycle detection in directed graphs.

Cycle Detection via Kahn's Algorithm (BFS)

In a directed graph with a cycle, the nodes involved in the cycle will never have their in-degrees reduced to 0. This is because there is always at least one incoming edge from another node in the cycle.

• None of these nodes can ever enter the queue because their in-degrees will never reach 0.
• Consequently, the final topoOrder list will have a size strictly less than $V$.
• Condition: if (topoOrder.size() != V) -> Cycle Detected!

Cycle Detection via DFS

To detect cycles using DFS, we must track not only whether a node has been visited, but also whether it is currently in the active recursion stack (i.e., we are still exploring its descendants). We do this using a pathVisited array.

If we encounter a node that is already marked as pathVisited during our DFS traversal, we have found a back-edge, which indicates a cycle.

9. Comparative Synthesis: DFS vs. BFS (Kahn's)

10. Practical Application: Course Schedule (LeetCode 207 & 210)

The Course Schedule problem is the classic application of topological sorting.

Problem Statement (LeetCode 210)

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 the ordering of courses you should take to finish all courses.
• If it is impossible to finish all courses, return an empty array.

Modeling the Graph

• Vertices: The courses (0 to numCourses - 1).
• Edges: If [a, b] is a prerequisite, it means we must take b before a. This translates to a directed edge: b -> a.

11. Course Schedule Code Walkthrough (LeetCode 210)

Below is the complete, optimized solution using Kahn's Algorithm, which handles both cycle detection and ordering.

Java Implementation

import java.util.*;

class CourseSchedule {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // Create adjacency list
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            adj.add(new ArrayList<>());
        }
        
        int[] inDegree = new int[numCourses];
        
        // Build graph: prerequisite -> course
        for (int[] pair : prerequisites) {
            int course = pair[0];
            int prereq = pair[1];
            adj.get(prereq).add(course);
            inDegree[course]++;
        }
        
        // Queue for BFS
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.add(i);
            }
        }
        
        int[] order = new int[numCourses];
        int index = 0;
        
        // Process courses
        while (!queue.isEmpty()) {
            int curr = queue.poll();
            order[index++] = curr;
            
            for (int neighbor : adj.get(curr)) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) {
                    queue.add(neighbor);
                }
            }
        }
        
        // If we couldn't process all courses, a cycle exists
        if (index != numCourses) {
            return new int[0];
        }
        
        return order;
    }
}

Python Implementation

from collections import deque

class CourseSchedule:
    def findOrder(self, numCourses: int, prerequisites: list[list[int]]) -> list[int]:
        # Build adjacency list and in-degree array
        adj = [[] for _ in range(numCourses)]
        in_degree = [0] * numCourses
        
        for course, prereq in prerequisites:
            adj[prereq].append(course)
            in_degree[course] += 1
            
        # Queue all courses with no prerequisites
        queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
        
        order = []
        
        while queue:
            curr = queue.popleft()
            order.append(curr)
            
            for neighbor in adj[curr]:
                in_degree[neighbor] -= 1
                if in_degree[neighbor] == 0:
                    queue.append(neighbor)
                    
        # If order contains all courses, return it; otherwise, return empty list (cycle detected)
        return order if len(order) == numCourses else []

12. Common Pitfalls, Debugging, and Edge Cases

When implementing topological sorting in interviews, watch out for these common traps:

1. Disconnected Components

If a graph has multiple disconnected components, a simple DFS starting from node 0 will fail to visit all nodes.

• Fix: Always loop through all vertices from 0 to V - 1 and trigger DFS/BFS on any unvisited nodes.

2. Self-Loops

A node pointing to itself (A -> A) is a cycle.

• Kahn's Algorithm handles this naturally because the in-degree of A will never drop to 0.
• DFS requires explicit cycle detection (using a pathVisited array) to avoid infinite recursion.

3. Non-Unique Orderings

Remember that a graph can have multiple valid topological sorts. For example, if there are no edges in a graph of 3 nodes, [0, 1, 2], [2, 1, 0], and [1, 0, 2] are all perfectly valid topological sorts. Do not write tests that assert a single hardcoded output array.

Summary and Key Takeaways

• Topological Sort is a linear ordering of vertices in a Directed Acyclic Graph (DAG) where for every edge $u \to v$, $u$ comes before $v$.
• DAG Only: Topological sorting is strictly impossible if the graph contains any cycles or is undirected.
• DFS Approach: Uses a visited array and a stack. Nodes are pushed onto the stack during backtracking (when their DFS calls finish).
• Kahn's Algorithm (BFS): Uses an in-degree array and a queue. It processes nodes with an in-degree of 0 and dynamically decrements neighbor in-degrees.
• Cycle Detection: Kahn's algorithm detects cycles if the final sorted list size is less than $V$. DFS detects cycles using a recursion stack tracking array (pathVisited).
• Course Schedule: The classic real-world application of topological sort, where courses are vertices and prerequisites are directed edges.
• Complexity: Both DFS and BFS approaches run in optimal $\mathcal{O}(V + E)$ time and require $\mathcal{O}(V)$ auxiliary space.