Topological Sort: DFS & Kahn's Algorithm

1. What is a Topological Sort?

A topological sort of a Directed Acyclic Graph (DAG) is a linear ordering of its vertices such that for every directed edge from vertex u to vertex v (u -> v), vertex u comes before vertex v in the ordering.

Think of it as flattening a graph's dependencies into a single valid sequence.

A key property of topological sorting is that the resulting order is not always unique. A graph can have multiple valid topological sorts.

This is only possible on a DAG. Why? As we saw in the last lesson, a cycle like A -> B -> C -> A creates a paradox: A must come before B, B before C, and C before A. No linear ordering can satisfy this, so a topological sort is impossible.

For a deeper dive into the intuition behind topological sorting and its real-world applications, the following article provides an excellent overview.

2. Approach 1: DFS-Based Topological Sort

This method is a clever modification of the standard DFS traversal you are already familiar with. The core idea is based on the finish times of the DFS calls.

Intuition: In a DAG, the last node to "finish" its DFS exploration (meaning all its descendants have been fully explored) must be one of the starting points in the dependency chain. Conversely, a node that finishes its DFS call first must be at the end of a dependency chain.

Therefore, if we track the order in which nodes finish their DFS calls and then reverse that order, we get a valid topological sort. A stack is the perfect data structure for this.

Algorithm:

1. Initialize a visited set and an empty stack.
2. Iterate through all vertices of the graph. If a vertex hasn't been visited, call a recursive DFS helper function on it.
3. In the DFS function for a node u:
   a. Mark u as visited.
   b. For each neighbor v of u, if v is not visited, recursively call DFS on v.
   c. After exploring all of u's neighbors (i.e., just before the function for u returns), push u onto the stack.
4. After the main loop finishes, the stack contains the vertices in a reverse topological order. Popping elements one by one from the stack gives the final topological sort.

To see this in action, the following video provides a clear, step-by-step walkthrough.

Python Implementation

Here is a Python implementation of the DFS-based topological sort. You can also find this code, along with versions in other languages, in the GeeksForGeeks article "Kahn's Algorithm vs DFS Approach".

def topological_sort_dfs(V, adj):
    visited = [False] * V
    stack = []

    def dfs(node):
        visited[node] = True
        for neighbor in adj[node]:
            if not visited[neighbor]:
                dfs(neighbor)
        # After visiting all neighbors, push current node to stack
        stack.append(node)

    # Call the recursive helper function to store Topological Sort
    # starting from all vertices one by one
    for i in range(V):
        if not visited[i]:
            dfs(i)
    
    # The stack now contains the reverse topological sort.
    # We can pop from it or simply reverse it.
    return stack[::-1] 

# Example Usage:
# V = 6
# adj = [[], [], [3], [1], [0, 1], [0, 2]]
# sort_order = topological_sort_dfs(V, adj)
# print(sort_order) # Output could be [5, 4, 2, 3, 1, 0]

• Time Complexity: $O(V+E)$. We visit each vertex and edge once.
• Space Complexity: $O(V)$. For the visited array, the recursion stack depth, and the output stack.

3. Approach 2: Kahn's Algorithm (BFS-Based)

This is an iterative approach that uses Breadth-First Search (BFS). It has a very intuitive logic based on dependencies.

Intuition: A topological sort can only start with a node that has no incoming dependencies. In graph terms, this is a node with an in-degree of 0. The algorithm processes these nodes, "removes" them and their outgoing edges from the graph, and then finds the next set of nodes that now have an in-degree of 0.

Algorithm:

1. Compute In-Degrees: Create an array to store the in-degree of every vertex. Iterate through all edges (u, v) in the graph and increment the in-degree of each v.
2. Initialize Queue: Find all vertices with an in-degree of 0 and add them to a queue.
3. Process Queue:
   a. Initialize an empty list for the topological order.
   b. While the queue is not empty:
   i. Dequeue a vertex u and append it to the topological order list.
   ii. For each neighbor v of u:
   - Decrement the in-degree of v (as the dependency from u is now satisfied).
   - If the in-degree of v becomes 0, enqueue v.
4. The list now contains a valid topological sort.

The video below explains this process beautifully.

Python Implementation

Here is a Python implementation of Kahn's Algorithm.

from collections import deque

def topological_sort_kahn(V, adj):
    in_degree = [0] * V
    for i in range(V):
        for neighbor in adj[i]:
            in_degree[neighbor] += 1
            
    # Create a queue and enqueue all vertices with in-degree 0
    queue = deque([i for i in range(V) if in_degree[i] == 0])
    
    topo_order = []
    
    while queue:
        u = queue.popleft()
        topo_order.append(u)
        
        # Iterate through all neighboring nodes of dequeued node u
        # and decrease their in-degree by 1
        for neighbor in adj[u]:
            in_degree[neighbor] -= 1
            # If in-degree becomes 0, add it to the queue
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
                
    return topo_order

# Example Usage:
# V = 6
# adj = [[], [], [3], [1], [0, 1], [0, 2]]
# sort_order = topological_sort_kahn(V, adj)
# print(sort_order) # Output could be [4, 5, 0, 2, 3, 1]

• Time Complexity: $O(V+E)$. $O(V+E)$ to build the in-degree map and $O(V+E)$ for the BFS traversal.
• Space Complexity: $O(V)$. For the in_degree array and the queue.

4. Cycle Detection using Kahn's Algorithm

A neat feature of Kahn's algorithm is its built-in ability to detect cycles.

If the graph has a cycle, the nodes within the cycle (and any nodes that depend on them) will never have their in-degrees reduced to 0. The queue will become empty before all vertices have been processed.

Therefore, a cycle exists if and only if the number of nodes in the final topo_order list is less than the total number of vertices V. This is an important check to include in an interview setting.

Conclusion

You have now added two powerful and versatile algorithms to your interview toolkit. Topological sorting is fundamental for any problem involving ordered dependencies.

Key Takeaways:

• Topological Sort creates a linear ordering of vertices in a Directed Acyclic Graph (DAG).
• The DFS-based approach uses a stack to store vertices in the reverse order of their DFS finish times. Its complexity is $O(V+E)$.
• Kahn's Algorithm (BFS-based) is an iterative approach that uses a queue and the concept of in-degrees. It processes nodes with no incoming dependencies first. Its complexity is also $O(V+E)$.
• Both methods can be adapted to detect cycles. In Kahn's algorithm, a cycle is present if the final sorted list doesn't contain all vertices.

Preview of the Next Lesson:

We have now extensively covered graph traversal algorithms like DFS and BFS and their applications in cycle detection and topological sorting. Next, we will shift gears to a different but equally important graph-related topic: connectivity. We will learn to implement the Union-Find data structure, a specialized tool designed to efficiently track and merge disjoint sets, which is the key to solving problems like finding the number of connected components in a graph or detecting cycles in an undirected graph with incredible speed.