Kahn's Algorithm for Topological Sort

1. The Core Idea: An Algorithmic Translation of the Proof

Recall the key property we proved: every non-empty DAG has at least one vertex with an in-degree of 0. These vertices are "sources" with no prerequisites, so they can safely come first in a topological ordering.

Kahn's algorithm systematizes this. Imagine we have a set of all tasks we can currently perform (those with no pending prerequisites). We pick one, "complete" it, and then update the prerequisite status of all tasks that depended on it. As we complete tasks, new ones may become available. This is the essence of the algorithm.

To implement this, we need a few components:

1. An adjacency list to represent the graph.
2. An array or map to store the current in-degree of each vertex.
3. A queue to maintain the set of vertices with an in-degree of 0 that are ready to be processed. This is why the algorithm is considered BFS-based.
4. A result list to build the topological order.

2. The Algorithm Step-by-Step

The algorithm proceeds in three main phases: initialization, processing, and finalization.

Phase 1: Initialization

1. Compute In-degrees: Iterate through all the edges in the graph. For each edge $u\to v$, increment the in-degree count for vertex $v$. This pass gives us the initial in-degree for every vertex.
2. Populate the Queue: Iterate through all the vertices. Any vertex with an initial in-degree of 0 is a source. Add all such vertices to the queue.

This initial state is shown in the image below. The nodes with an in-degree of 0 (4, 5, and 6) are placed in the queue, ready to be processed.

Phase 2: Processing Loop
This is the main loop, which runs as long as the queue is not empty. It's very similar to a standard BFS traversal.

1. Dequeue a Vertex: Remove a vertex, let's call it u, from the front of the queue.
2. Add to Order: Append u to your result list. This vertex is now officially placed in the topological ordering.
3. Update Neighbors: For each neighbor v of u (i.e., for each edge $u\to v$):
   • Decrement the in-degree of v. Conceptually, this is like removing the edge from u to v because the prerequisite u is now satisfied.
   • If the in-degree of v becomes 0, it means all its prerequisites are met. Add v to the queue.

Phase 3: Finalization & Cycle Detection

1. After the loop terminates (i.e., the queue is empty), check if the number of vertices in your result list is equal to the total number of vertices in the graph.
2. If it is: You have successfully found a valid topological ordering.
3. If it is not: The graph contains a cycle. The loop terminated because the queue became empty, but there were still vertices left in the graph with in-degrees greater than 0. These vertices are part of a cycle and could never have their in-degrees reduced to 0.

The following video provides an excellent, animated walkthrough of this process, clearly showing how the in-degree counts and the queue change over time.

3. Implementation in C++

Now, let's translate this logic into C++. Given your competitive programming background, the structure should feel familiar. We will use a std::vector<int> in_degree, a std::queue<int>, and std::vector<int> adj[] for the adjacency list.

The following resource provides a concise walkthrough and a clear C++ implementation tailored for competitive programming.

Here is the core logic in C++, reflecting the structure discussed in the video.

#include <iostream>
#include <vector>
#include <queue>
#include <list>

// V: number of vertices, adj: adjacency list
std::vector<int> topologicalSort(int V, std::vector<int> adj[]) {
    // 1. Initialization
    std::vector<int> in_degree(V, 0);
    for (int i = 0; i < V; i++) {
        for (int neighbor : adj[i]) {
            in_degree[neighbor]++;
        }
    }

    std::queue<int> q;
    for (int i = 0; i < V; i++) {
        if (in_degree[i] == 0) {
            q.push(i);
        }
    }

    std::vector<int> topo_order;

    // 2. Processing Loop
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        topo_order.push_back(u);

        for (int v : adj[u]) {
            in_degree[v]--;
            if (in_degree[v] == 0) {
                q.push(v);
            }
        }
    }

    // 3. Finalization / Cycle Check
    if (topo_order.size() == V) {
        return topo_order;
    } else {
        // Graph has a cycle, return an empty list to indicate failure.
        return {};
    }
}

A Note on Correctness and Complexity

As you prefer to understand the theory, let's briefly touch upon why this works and its efficiency.

The key takeaways on correctness and complexity are:

• Correctness:
  • If the graph is a DAG, we proved it must have a source. Our algorithm finds it. By removing it, the remaining subgraph is also a DAG, which must also have a source. The algorithm correctly continues this process until all nodes are visited.
  • If the graph has a cycle, no node within the cycle can ever have its in-degree become 0 by removing other nodes in the cycle. Therefore, the queue will eventually become empty while these cyclic nodes remain, and topo_order.size() will be less than V.
• Time Complexity: $O(V+E)$, where $V$ is the number of vertices and $E$ is the number of edges.
  • Calculating initial in-degrees takes $O(E)$ time as we iterate through each adjacency list once.
  • Initializing the queue takes $O(V)$ time.
  • The main loop processes each vertex and each edge exactly once. Each vertex is enqueued and dequeued once. When a vertex u is dequeued, we iterate through its outgoing edges. Over the entire algorithm, this means we visit each edge once.
• Space Complexity: $O(V)$ to store the in_degree array, the queue, and the result.

Conclusion

In this lesson, you've transformed the theoretical foundation from our previous session into a practical and efficient algorithm. Kahn's algorithm is a powerful tool that not only generates a topological sort but also doubles as a cycle detector for directed graphs.

Key Takeaways:

• Kahn's algorithm is a direct implementation of the constructive proof that every DAG has a topological order.
• It operates by iteratively processing nodes with an in-degree of 0, using a queue in a manner similar to BFS.
• The core steps are: calculate all in-degrees, initialize a queue with source nodes, and then process the queue by decrementing neighbors' in-degrees and adding new source nodes as they appear.
• If the final sorted list contains fewer vertices than the graph, a cycle has been detected.
• The algorithm runs in linear time, $O(V+E)$, making it highly efficient for competitive programming problems.

In our next lesson, we will explore an alternative method for topological sorting that is based on Depth-First Search (DFS). This will provide you with another powerful perspective and a different set of trade-offs for solving problems on DAGs.