Topological Sort on a DAG

1. What is Topological Sorting?

Imagine you have a list of university courses to take, but some have prerequisites. For example, you must take "Intro to Programming" before "Data Structures." A topological sort would give you a valid sequence in which you can take all the courses.

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

The two key requirements are:

1. Directed Graph: The relationships have a one-way dependency (e.g., A is required for B, not the other way around).
2. Acyclic Graph (No Cycles): There are no circular dependencies. If "Course A" requires "Course B", and "Course B" requires "Course A", it's impossible to create a valid schedule.

A topological sort visually "unravels" the graph into a straight line, where all arrows point from left to right.

To understand these prerequisites more deeply, let's watch a short, clear explanation.

There are two primary algorithms to perform a topological sort. We will cover both:

1. Kahn's Algorithm, which uses Breadth-First Search (BFS).
2. A modified Depth-First Search (DFS) approach.

2. Kahn's Algorithm (BFS-based Approach)

Kahn's algorithm is intuitive because it mimics how you might naturally schedule tasks. You start with the tasks that have no prerequisites. Once you complete them, you can then move on to the tasks that only depended on the ones you just finished.

The key concept here is in-degree: the number of incoming edges a node has.

• A node with an in-degree of 0 has no prerequisites and can be performed first.

The algorithm works as follows:

1. Compute In-degrees: Calculate the in-degree for every vertex in the graph.
2. Initialize Queue: Add all vertices with an in-degree of 0 to a queue. These are our starting points.
3. Process Nodes: While the queue is not empty:
   a. Dequeue a vertex u. Add it to your result list (this is the next task in our sorted order).
   b. For each neighbor v of u, decrement its in-degree by 1 (since we've just "completed" u).
   c. If a neighbor v's in-degree becomes 0, it means all its prerequisites are met. Add v to the queue.
4. Check for Cycles: After the loop, if the number of vertices in your result list is less than the total number of vertices in the graph, it means there was a cycle. A cycle prevents the in-degrees of some nodes from ever reaching 0.

Let's see this process in action.

Python Implementation of Kahn's Algorithm

Now, let's look at a clean Python implementation. This is a common pattern you'll use in competitive programming.

Here is the code from the article, with added comments to highlight the steps:

from collections import deque, defaultdict

def topological_sort_kahns(vertices, edges):
    # Step 1: Build adjacency list and calculate in-degrees
    graph = defaultdict(list)
    in_degree = {i: 0 for i in range(vertices)}
    
    for src, dest in edges:
        graph[src].append(dest)
        in_degree[dest] += 1
    
    # Step 2: Find all vertices with no incoming edges (in-degree == 0)
    queue = deque()
    for vertex in range(vertices):
        if in_degree[vertex] == 0:
            queue.append(vertex)
    
    result = []
    
    # Step 3: Process vertices from the queue
    while queue:
        current = queue.popleft()
        result.append(current)
        
        # For each neighbor, reduce its in-degree
        for neighbor in graph[current]:
            in_degree[neighbor] -= 1
            # If in-degree becomes 0, add to queue
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    # Step 4: Check if topological sorting is possible (no cycle)
    if len(result) != vertices:
        return []  # Graph has a cycle
    
    return result

# Example usage
vertices = 6
edges = [(5, 2), (5, 0), (4, 0), (4, 1), (2, 3), (3, 1)]
print("Topological Sort (Kahn's):", topological_sort_kahns(vertices, edges))
# Possible output: [4, 5, 0, 2, 3, 1] or [5, 4, 2, 0, 3, 1] etc.

3. DFS-based Approach

An alternative method uses Depth-First Search. This approach can feel a bit less direct, but it's very powerful and a natural extension of your DFS skills.

The core idea is based on post-order traversal. A node is only considered "finished" after all of its descendants in the DFS tree have been visited. In a topological sort, a node must appear before its descendants. This means if we add a node to our result list as soon as it's finished, we are building the topological sort in reverse order.

The algorithm works as follows:

1. Initialize a visited set and a list/stack to store the result.
2. Iterate through all vertices. If a vertex hasn't been visited, start a DFS from it.
3. In the dfs(vertex) function:
   a. Mark the vertex as visited.
   b. For each neighbor of the vertex, if it hasn't been visited, recursively call dfs on it.
   c. After the loop over neighbors finishes (this is the post-order step), add the current vertex to the front of the result list (or append to a list and reverse it at the end).
4. Cycle Detection: To detect a cycle, we need an extra recursion_stack set. Before visiting a node's neighbors, add it to the recursion_stack. After the visit, remove it. If you ever try to visit a node that is already in the recursion_stack, you've found a back edge, which indicates a cycle.

This DFS approach is often used in more complex problems. Let's watch an explanation of this logic in the context of a challenging competitive programming problem.

Python Implementation of DFS-based Topological Sort

Now, let's examine the Python code for this approach.

Here's the code, again with comments to guide you:

def topological_sort_dfs(vertices, edges):
    # Step 1: Build the adjacency list
    graph = {i: [] for i in range(vertices)}
    for src, dest in edges:
        graph[src].append(dest)
    
    visited = [False] * vertices
    rec_stack = [False] * vertices  # For cycle detection
    result_stack = []

    def dfs(vertex):
        # Mark current vertex as visited and add to recursion stack
        visited[vertex] = True
        rec_stack[vertex] = True
        
        # Visit all neighbors
        for neighbor in graph[vertex]:
            # If neighbor is in recursion stack, we have a cycle
            if rec_stack[neighbor]:
                return False  # Cycle detected
            # If neighbor is not visited, recursively visit it
            if not visited[neighbor]:
                if not dfs(neighbor):
                    return False # Propagate cycle detection
        
        # After visiting all descendants, remove from recursion stack
        rec_stack[vertex] = False
        # Post-order step: add vertex to the result
        result_stack.append(vertex)
        return True
    
    # Perform DFS for all unvisited vertices (handles disconnected graphs)
    for vertex in range(vertices):
        if not visited[vertex]:
            if not dfs(vertex):
                return []  # Cycle detected, no topological sort possible
    
    # The stack was built in post-order, so reverse it for the final result
    return result_stack[::-1]

# Example usage
vertices = 6
edges = [(5, 2), (5, 0), (4, 0), (4, 1), (2, 3), (3, 1)]
print("Topological Sort (DFS):", topological_sort_dfs(vertices, edges))
# Possible output: [5, 4, 2, 3, 1, 0] or [4, 5, 2, 3, 1, 0] etc.

Conclusion

You have now mastered topological sorting, a key algorithm for directed graphs. You've learned not just what it is, but two distinct and equally valid ways to implement it.

Key Takeaways:

• A topological sort is a linear ordering of vertices in a DAG where for every edge u -> v, u appears before v.
• It's essential for problems involving dependencies, such as task scheduling or build systems.
• Kahn's Algorithm uses a BFS-like approach, processing nodes with an in-degree of 0.
• The DFS-based algorithm uses a post-order traversal to build the sorted list in reverse.
• Both algorithms have a time complexity of $O(V+E)$ and can be adapted to detect cycles. If a cycle is present, a topological sort is not possible.

Up Next:
This lesson concludes our module on graph traversals. You've built a strong foundation. In our next module, "Shortest Paths and Minimum Spanning Trees," we will start by exploring Dijkstra's algorithm. This will show you how to find the shortest path from a single source to all other nodes in a weighted graph, and it will be a great opportunity to apply your knowledge of heaps and priority queues