Kahn's Algorithm for Topological Sort

Hello! Welcome to the third lesson in our module on Graph Algorithms and Applications.

In our last session, we established the foundations of graph traversal by implementing Breadth-First Search (BFS) and Depth-First Search (DFS). You learned that BFS explores level-by-level and is ideal for finding the shortest path in unweighted graphs, while DFS explores deeply and excels at tasks like cycle detection and path finding.

Today, we'll apply this knowledge to solve a classic problem with immense practical relevance in software engineering: ordering dependent tasks. Imagine a complex build system, a CI/CD pipeline, or the task scheduler you worked on for Bedrock's inference service, Rudi. In all these systems, you must execute tasks in an order that respects their prerequisites. This is precisely what topological sorting accomplishes.

Our learning outcome is to implement topological sort on a Directed Acyclic Graph (DAG) using Kahn's algorithm (BFS-based). We will build on your understanding of BFS to develop an algorithm that is not only correct but also robust enough for production-like scenarios.

---

1. What is Topological Sort?

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

In simpler terms, if task A must be completed before task B, a topological sort will always place A before B in the resulting sequence.

It's important to note two things:

1. It only works on DAGs. If a graph contains a cycle (e.g., A depends on B, and B depends on A), no valid ordering is possible.
2. The ordering is not always unique. There can be multiple valid sequences, depending on which "ready" task you choose to process next.

To get a solid grasp of the concept and its applications, the following video provides an excellent introduction.

---

2. Kahn's Algorithm: A BFS-based Approach

Kahn's algorithm provides an intuitive, iterative way to generate a topological sort. Since you're already comfortable with BFS, you'll find the logic very familiar.

The core idea is to repeatedly identify and process nodes that have no remaining dependencies.

Here’s the high-level intuition:

1. Find all nodes that have no incoming edges (an in-degree of 0). These are the tasks with no prerequisites.
2. Add these nodes to a queue of "ready" tasks.
3. While the queue is not empty, dequeue a node and add it to our final sorted list.
4. When we "process" this node, we effectively remove it and its outgoing edges from the graph. For each neighbor of the processed node, we decrement its in-degree count.
5. If decrementing an in-degree causes it to become 0, that neighbor now has no remaining prerequisites, so we add it to the queue.
6. Repeat until the queue is empty.

Let's watch a detailed walkthrough of this process.

---

3. Implementation in Python

Now let's translate this logic into production-quality Python code. We'll need three key components:

• An adjacency list to represent the graph.
• A dictionary or list to track the in-degree of each node.
• A deque to serve as our queue for nodes with an in-degree of 0.

A critical part of a robust implementation is cycle detection. How do we know if the graph had a cycle? If a cycle exists, some nodes will never have their in-degrees reduced to zero. They will be "stuck" waiting for each other. Consequently, the main loop will finish, but the number of nodes in our resulting topological order will be less than the total number of nodes in the graph.

from collections import defaultdict, deque

def kahn_topological_sort(n, edges):
    """
    Performs a topological sort on a DAG using Kahn's algorithm.

    Args:
        n (int): The total number of nodes, labeled 0 to n-1.
        edges (list of lists): A list of directed edges, e.g., [[u1, v1], [u2, v2]].

    Returns:
        list: A list containing the topologically sorted nodes.
              Returns an empty list if the graph has a cycle.
    """



    # 1. Build adjacency list and in-degree map
    adj_list = defaultdict(list)
    in_degree = {i: 0 for i in range(n)}
    
    for u, v in edges:
        adj_list[u].append(v)
        in_degree[v] += 1
        



    # 2. Initialize the queue with all nodes having an in-degree of 0
    queue = deque([node for node in range(n) if in_degree[node] == 0])
    
    topological_order = []
    



    # 3. Process the queue
    while queue:
        node = queue.popleft()
        topological_order.append(node)
        



        # For each neighbor, decrement its in-degree
        for neighbor in adj_list.get(node, []):
            in_degree[neighbor] -= 1



            # If in-degree becomes 0, add it to the queue
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
                



    # 4. Check for cycles
    if len(topological_order) == n:
        return topological_order
    else:



        # A cycle was detected
        return []




# Example Usage:
num_nodes = 6
dependencies = [[5, 2], [5, 0], [4, 0], [4, 1], [2, 3], [3, 1]]



# Task 5 must be done before 2 and 0
# Task 4 must be done before 0 and 1
# etc.

sorted_tasks = kahn_topological_sort(num_nodes, dependencies)

if sorted_tasks:
    print(f"Valid topological order: {sorted_tasks}")



    # Possible output: [4, 5, 0, 2, 3, 1]
else:
    print("A cycle was detected in the task dependencies.")

This implementation clearly follows the steps we outlined and includes the crucial check for cycles, making it suitable for handling potentially invalid inputs.

---

4. Connection to Your Background: Rust Implementation

The logic of Kahn's algorithm is language-agnostic. Given your expertise in Rust, it's valuable to see how the same principles apply. The core data structures—adjacency list, in-degree counts, and a queue—map directly.

The following resource provides a Rust implementation for a problem that uses Kahn's algorithm.

Notice the parallels:

• Python's defaultdict(list) becomes vec![vec![]; n + 1] in Rust.
• The in_degree dictionary is a vec![0i32; n + 1].
• The deque is implemented with a Vec, where new items are collected into a next_queue.

This parallel highlights that mastering the algorithm's logic is the key skill that transfers across languages and environments. In a production system like Rudi, where performance and memory safety are paramount, a Rust implementation would be a natural choice, but the underlying scheduling logic remains the same.

---

5. Complexity and Trade-offs

Understanding the performance characteristics of an algorithm is critical for an SDE.

• Time Complexity: $O(V+E)$

  • Initialization: Building the adjacency list and in-degree map requires iterating through all edges, which is $O(E)$. Initializing the queue requires iterating through all vertices, which is $O(V)$.
  • Processing Loop: Each vertex is enqueued and dequeued exactly once. When a vertex is dequeued, we visit each of its outgoing edges. Over the entire execution, this means every vertex and every edge is processed once.
  • Total time is therefore proportional to $V+E$.

• Space Complexity: $O(V+E)$

  • The adjacency list requires $O(V+E)$ space.
  • The in_degree map requires $O(V)$ space.
  • The queue can, in the worst case, hold up to $V$ vertices (e.g., a graph with no edges).
  • The dominant factor is the adjacency list, making the space complexity $O(V+E)$.

Kahn's algorithm is highly efficient and scales linearly with the size of the graph, making it practical for large-scale dependency analysis.

---

Conclusion

In this lesson, we moved from general graph traversal to a specific, powerful application. You learned how to order a set of dependencies, a fundamental problem in computer science.

Key Takeaways:

• Topological Sort produces a linear ordering of nodes in a DAG, respecting all prerequisites.
• Kahn's Algorithm is an iterative, BFS-based method that uses in-degrees and a queue to build this ordering.
• It is efficient, with a time and space complexity of $O(V+E)$.
• A key feature is its ability to detect cycles by checking if all nodes were successfully added to the final ordering.
• The algorithm's logic is universal, and you've seen how it translates from Python to Rust, reinforcing your cross-language skills.

Next Lesson Preview

You've now mastered the BFS-based approach to topological sorting. But is it the only way? In our next lesson, we will explore its counterpart: "Implement topological sort on a DAG using a DFS-based approach." This will allow you to compare and contrast two different algorithmic paradigms for solving the same problem, deepening your understanding of their trade-offs.