Topological Sort: DFS & Kahn's Algorithm

1. What is Topological Sorting?

Imagine you have a list of tasks, where some tasks must be completed before others. A topological sort gives you a valid sequence in which to perform these tasks.

A key thing to remember is that a graph can have multiple valid topological sorts. Our goal is to find any one of them.

To get a clear definition and see why this only works on DAGs, the first few minutes of this video are a great starting point.

2. Topological Sort using Depth-First Search (DFS)

The intuition behind the DFS approach is based on a simple observation: a vertex can only be "finished" (i.e., added to our sorted list) after all the vertices it points to are finished. This sounds a lot like a post-order traversal.

The algorithm uses a stack to achieve this:

1. Initialize an empty stack and a visited array.
2. Iterate through all the vertices of the graph. For each unvisited vertex, call a recursive DFS helper function.
3. In the DFS function for a vertex u:
   a. Mark u as visited.
   b. Recursively call the DFS function for all of u's unvisited neighbors.
   c. After the recursive calls for all neighbors are complete, push u onto the stack.
4. Once the main loop is done, the stack contains the vertices in reverse topological order. Popping elements one by one from the stack gives the final topological sort.

This process ensures that a node is pushed to the stack only after all its dependencies have been pushed. Therefore, the node with no outgoing edges (or whose dependent nodes are all processed) gets pushed first, and the source nodes get pushed last.

Let's watch a detailed walkthrough of this algorithm.

Java Implementation (DFS)

Here's a clean Java implementation of the DFS-based topological sort. Since you're comfortable with DFS, this structure should look familiar.

import java.util.*;

public class TopologicalSortDFS {

    // Main function to perform topological sort
    public static int[] topoSort(int V, ArrayList<ArrayList<Integer>> adj) {
        boolean[] visited = new boolean[V];
        Stack<Integer> stack = new Stack<>();

        // Call DFS for every unvisited node to handle disconnected components
        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                dfs(i, adj, visited, stack);
            }
        }

        // Pop elements from the stack to get the topological order
        int[] result = new int[V];
        int i = 0;
        while (!stack.isEmpty()) {
            result[i++] = stack.pop();
        }
        return result;
    }

    // Recursive DFS helper function
    private static void dfs(int node, ArrayList<ArrayList<Integer>> adj, boolean[] visited, Stack<Integer> stack) {
        visited[node] = true;

        for (int neighbor : adj.get(node)) {
            if (!visited[neighbor]) {
                dfs(neighbor, adj, visited, stack);
            }
        }

        // After visiting all neighbors, push the current node onto the stack
        stack.push(node);
    }

    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<>());
        }
        // Example from the video: 5->0, 5->2, 4->0, 4->1, 2->3, 3->1
        adj.get(5).add(0);
        adj.get(5).add(2);
        adj.get(4).add(0);
        adj.get(4).add(1);
        adj.get(2).add(3);
        adj.get(3).add(1);

        int[] sortedOrder = topoSort(V, adj);
        System.out.println("Topological Sort (DFS): " + Arrays.toString(sortedOrder));
        // Possible output: [5, 4, 2, 3, 1, 0] or [4, 5, 2, 3, 1, 0]
    }
}

Complexity Analysis

• Time Complexity: O(V + E). This is the standard time complexity for a DFS traversal, as we visit each vertex and each edge once.
• Space Complexity: O(V). This is for the visited array, the recursion stack (which can go up to V in the worst case), and the stack used to store the result.

3. Topological Sort using BFS (Kahn's Algorithm)

The second approach uses Breadth-First Search and has a very different, but equally intuitive, logic. It's known as Kahn's Algorithm.

The intuition is to start with the tasks that have no prerequisites. In graph terms, we start with vertices that have an in-degree of 0.

The algorithm works as follows:

1. Compute In-degrees: Calculate the in-degree for every vertex in the graph. This can be done by iterating through the adjacency list.
2. Initialize Queue: Create a queue and add all vertices with an in-degree of 0.
3. Process Queue:
   a. While the queue is not empty, dequeue a vertex u.
   b. Add u to the result list (our topological sort).
   c. For each neighbor v of u:
   i. Decrement the in-degree of v.
   ii. If the in-degree of v becomes 0, it means all its prerequisites are met. Add v to the queue.
4. The final result list is the topological sort.

A fascinating side-effect of Kahn's algorithm is that it can also detect cycles. If, after the algorithm finishes, the number of nodes in our result list is less than the total number of vertices V, the graph must contain a cycle. Why? Because a cycle creates a circular dependency where the in-degrees of the nodes in the cycle will never drop to 0.

Let's watch a detailed walkthrough of this algorithm.

Java Implementation (Kahn's Algorithm)

This approach is highly valued in interviews for its iterative nature and its cycle-detection property. Here is a guide that provides a good Java implementation.

Here's the code, adapted for clarity:

import java.util.*;

public class TopologicalSortBFS {

    public static int[] topoSort(int V, ArrayList<ArrayList<Integer>> adj) {
        // 1. Compute in-degrees
        int[] inDegree = new int[V];
        for (int i = 0; i < V; i++) {
            for (int neighbor : adj.get(i)) {
                inDegree[neighbor]++;
            }
        }

        // 2. Initialize queue with all nodes having in-degree 0
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < V; i++) {
            if (inDegree[i] == 0) {
                queue.add(i);
            }
        }

        int[] result = new int[V];
        int index = 0;

        // 3. Process the queue
        while (!queue.isEmpty()) {
            int node = queue.poll();
            result[index++] = node;

            // For each neighbor, reduce its in-degree
            for (int neighbor : adj.get(node)) {
                inDegree[neighbor]--;
                // If in-degree becomes 0, add it to the queue
                if (inDegree[neighbor] == 0) {
                    queue.add(neighbor);
                }
            }
        }

        // Check for cycle: if not all vertices were visited, a cycle exists.
        if (index != V) {
            System.out.println("Cycle detected! Topological sort not possible.");
            return new int[0]; // Return empty array or handle error
        }

        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<>());
        }
        adj.get(5).add(0);
        adj.get(5).add(2);
        adj.get(4).add(0);
        adj.get(4).add(1);
        adj.get(2).add(3);
        adj.get(3).add(1);

        int[] sortedOrder = topoSort(V, adj);
        System.out.println("Topological Sort (Kahn's): " + Arrays.toString(sortedOrder));
        // Possible output: [4, 5, 0, 2, 3, 1]
    }
}

Complexity Analysis

• Time Complexity: O(V + E).
  • Calculating in-degrees takes O(V + E).
  • Initializing the queue takes O(V).
  • The main while loop processes each vertex and each edge exactly once, totaling O(V + E).
• Space Complexity: O(V). This is for the inDegree array and the queue, both of which can store up to V elements.

Conclusion

You've now mastered two fundamental algorithms for topological sorting, a problem that appears frequently in both technical interviews and real-world applications.

Key Takeaways:

• Topological sorting produces a linear ordering of nodes in a Directed Acyclic Graph (DAG) that respects all dependencies.
• The DFS-based method uses a stack to store nodes in a post-order traversal fashion. The final order is obtained by popping from the stack.
• Kahn's Algorithm (BFS-based) uses a queue and the concept of in-degrees. It processes nodes with no incoming edges first and can also detect cycles.
• Both algorithms have an optimal time complexity of O(V + E) and a space complexity of O(V).

Preview of the Next Lesson:
We will continue our exploration of graph traversal algorithms by looking at how to identify distinct subgraphs. Our next lesson will be on finding connected components and the number of "islands" in a graph. This is a classic problem that uses simple BFS or DFS traversals to count and categorize separate parts of a graph or grid.