Topological Sort: Kahn's Algorithm & DFS

1. What is Topological Sorting?

A topological sort of a directed graph is a linear ordering of its vertices such that for every directed edge from vertex u to vertex v, vertex u comes before vertex v in the ordering.

Think of it as arranging all the graph's nodes in a straight line so that all the directed edges point from left to right. This ordering is crucial in many real-world scenarios:

• Software Build Dependencies: As mentioned, ensuring libraries are built before the programs that depend on them.
• Course Prerequisites: Finding a valid sequence of courses to take at a university.
• Task Scheduling: Ordering jobs in a pipeline where some jobs depend on the output of others.

To build our intuition, the following video provides a great introduction with clear examples.

The Directed Acyclic Graph (DAG) Requirement

An important constraint is that topological sorting is only possible on a Directed Acyclic Graph (DAG). A DAG is a directed graph that contains no cycles.

Why is this? If a graph has a cycle (e.g., A → B → C → A), it's impossible to create a linear ordering. To process A, you must first process C. To process C, you need B. And to process B, you need A. You're stuck in a loop with no valid starting point.

The next segment of the video illustrates this critical point.

2. Algorithm 1: Kahn's Algorithm (BFS-based)

Kahn's algorithm is an intuitive and popular method for topological sorting. It works by iteratively identifying nodes that have no prerequisites.

The core idea is:

1. Find a node with no incoming edges (its in-degree is 0).
2. Add this node to our topological ordering.
3. Remove this node and all its outgoing edges from the graph.
4. This removal might reduce the in-degree of other nodes. If any neighbor's in-degree becomes 0, it is now a candidate for the next step.
5. Repeat until all nodes are processed.

To implement this efficiently, we use a queue to keep track of all nodes with an in-degree of 0.

Detailed Steps:

1. Compute In-degrees: Create an array or map to store the in-degree of every vertex in the graph. This requires iterating through all edges.
2. Initialize Queue: Add all vertices with an in-degree of 0 to a queue.
3. Process Nodes:
   • While the queue is not empty:
     • Dequeue a vertex, u.
     • Add u to your list representing the topological order.
     • For each neighbor v of u:
       • Decrement the in-degree of v.
       • If the in-degree of v becomes 0, enqueue v.

The following video provides an excellent, animated walkthrough of this process.

Cycle Detection and Complexity

• Cycle Detection: If, at the end of the algorithm, the number of nodes in our topological order is less than the total number of vertices in the graph, it means the graph has a cycle. The algorithm got "stuck" because the nodes within the cycle never reached an in-degree of 0.
• Time Complexity: $O(V+E)$. We traverse each vertex and each edge a constant number of times.
  • $O(E)$ to build the adjacency list and compute in-degrees.
  • $O(V)$ to initialize the queue in the worst case.
  • The main while loop runs once for each vertex, and the inner loop runs once for each edge.
• Space Complexity: $O(V+E)$. Required for the adjacency list, the in-degree array, and the queue.

For a textual summary and another example, you can refer to the following resource. It applies Kahn's algorithm to the "Course Schedule" problem, a classic topological sort application.

3. Algorithm 2: DFS-based Approach

An alternative way to generate a topological sort is by using Depth-First Search (DFS). Since you're already familiar with DFS from our earlier modules, this approach is a natural extension of that knowledge.

The key insight is related to the finish times of the DFS traversal. In a DAG, the vertex that finishes last (i.e., its recursive DFS call returns) must be a "source" node (or a source in a subgraph that was just traversed).

Therefore, if we perform a DFS and add each vertex to the front of a list as it finishes, we will produce a valid topological ordering. A common way to implement this is to push each finished vertex onto a stack. At the end, popping all items from the stack gives the sorted order.

Detailed Steps:

1. Initialize an empty list or stack for the result, and a set/array to track visited nodes.
2. Iterate through all vertices in the graph. If a vertex has not been visited, start a recursive DFS from it.
3. In the recursive DFS function for a node u:
   • Mark u as visited.
   • For each unvisited neighbor v of u, recursively call DFS on v.
   • After the recursion for all of u's neighbors has completed, add u to the front of the result list (or push it onto the stack).

Let's watch a visualization of this approach.

Cycle Detection and Complexity

• Cycle Detection: A standard DFS can detect a cycle by keeping track of the nodes currently in the recursion stack. If the DFS traversal encounters a node that is already in the current recursion path (a "back edge"), a cycle exists. This is often implemented using three states (colors): WHITE (unvisited), GRAY (visiting/in recursion stack), and BLACK (finished).
• Time Complexity: $O(V+E)$, same as a standard DFS.
• Space Complexity: $O(V+E)$, for the adjacency list, visited set, and the recursion call stack (which can be up to $O(V)$ deep).

The article you looked at earlier also contains an excellent explanation of the DFS approach, including Python code that uses the three-color method for cycle detection.

4. Comparison: Kahn's vs. DFS

Both algorithms correctly find a topological sort and have the same time and space complexity, but they have different characteristics.

The choice between them often comes down to implementation preference or the specific problem context.

Conclusion

In this lesson, we introduced topological sorting, a key algorithm for ordering items with dependencies. You now understand its importance and the fundamental requirement that it operates on Directed Acyclic Graphs (DAGs).

Key Takeaways:

• A topological sort is a linear ordering of a DAG's vertices where for every edge u -> v, u comes before v.
• It is used in task scheduling, dependency resolution, and build systems.
• Kahn's algorithm is an iterative, BFS-based approach that uses a queue and vertex in-degrees to find the ordering.
• The DFS-based algorithm is a recursive approach that orders vertices by pushing them onto a stack in post-order (after their descendants are visited).
• Both algorithms have a time and space complexity of $O(V+E)$ and can be adapted to detect cycles.

Preview of the Next Lesson:
We will continue exploring advanced graph algorithms by tackling the All-Pairs Shortest Paths problem. While Dijkstra's and Bellman-Ford find the shortest paths from a single source, we'll learn the Floyd-Warshall algorithm, a dynamic programming approach to find the shortest path between every pair of vertices in a graph.