Topological Sorting for DAGs

Hello! Let's dive into your next lesson on graph algorithms.

In the previous lesson, you learned how to detect cycles in directed graphs. This is the perfect foundation for today's topic, because we'll be working with graphs that are guaranteed not to have cycles.

Today's learning outcome is to implement topological sorting for a Directed Acyclic Graph (DAG). A topological sort is a linear ordering of vertices such that for every directed edge from vertex u to vertex v, u comes before v in the ordering. This is a common and powerful algorithm used to model dependencies—think of build systems where libraries must be compiled in a certain order, or task scheduling where some tasks are prerequisites for others. Mastering this is another step toward the architectural mindset you're building.

We will explore the two primary algorithms for this task: one based on DFS, and another based on BFS.

What is Topological Sorting?

Imagine you have a set of tasks, and some tasks must be completed before others can begin. A topological sort gives you a valid sequence in which to perform these tasks. A graph is a natural way to represent this: each task is a node, and a directed edge A -> B means "task A must be completed before task B."

Because it's impossible to have a circular dependency (e.g., A needs B, B needs C, and C needs A), this algorithm only works on Directed Acyclic Graphs (DAGs).

Unsorted vs. Topologically Sorted Graph — This image shows the goal of topological sorting. On the left is a standard DAG. On the right, the same nodes are rearranged into a straight line, where all dependency arrows point from left to right. This linear arrangement is one of several possible topological sorts for the graph.

There are two main ways to achieve this sort. Let's start with the one that builds directly on your DFS knowledge.

1. The DFS-Based Approach

The intuition here is connected to the "finishing time" of a node in a DFS traversal. A vertex's recursive DFS call only "finishes" after all of its descendants have been fully explored. Therefore, the last node to finish must be a node with no outgoing edges (or whose outgoing edges all point to already-visited nodes). This node can be placed at the end of our topological sort.

Extending this logic, if we take the nodes in the reverse order of their finishing times, we get a valid topological sort.

How can we implement this? By using a stack.

Perform a DFS traversal on the graph.
Once a node's recursive DFS call has visited all its neighbors and is about to return (i.e., it has "finished"), push that node onto a stack.
After the entire DFS traversal is complete (covering all components of the graph), the stack will contain all the nodes. Popping them one by one will give a valid topological order.

The following video provides an excellent walkthrough of this entire process.

G-21. Topological Sort Algorithm | DFS

The 'take U forward' channel has a great video that explains the definition, the DFS-based algorithm, and the intuition behind why it works.

Watch from the beginning to 07:49, and then from 10:46 to 12:57. Focus on the key moment: a node is pushed onto the stack after its recursive DFS calls for all neighbors have completed. The final segment explains the simple, yet powerful, intuition behind this ordering.

Algorithm Summary (DFS-based)

Topological Sort Algorithms: DFS based algorithm — This image provides a concise summary of the DFS-based approach. It lists the steps, notes the O(V+E) running time, and shows a worked example with discovery and finish times, culminating in a final topological order.

Complexity Analysis

Time Complexity: $O (V + E)$ . This is because the algorithm is fundamentally a DFS traversal where we visit every vertex and every edge once.
Space Complexity: $O (V)$ . This space is used for the visited array, the recursion stack (which in the worst case can be of depth V), and the stack used to store the topological sort.

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

There is an alternative, iterative approach that uses Breadth-First Search. It's known as Kahn's algorithm, and its intuition is equally elegant but comes from a different angle.

Instead of finding nodes that should go last, Kahn's algorithm finds nodes that can go first. A node can be the first in a topological sort if it has no prerequisites—that is, it has no incoming edges.

The central concept here is a node's in-degree: the count of incoming edges.

Kahn's Algorithm:

Compute the in-degree for every vertex in the graph.
Initialize a queue and add all vertices with an in-degree of 0.
Initialize a list to store the final topological order.
While the queue is not empty:
a. Dequeue a vertex, let's call it u. Add u to your topological order list.
b. For each neighbor v of u:
i. Decrement the in-degree of v.
ii. If the in-degree of v becomes 0, enqueue v.
If the final list of sorted vertices contains all vertices from the graph, you have a valid topological sort. If not, the graph must contain a cycle.

Let's watch a demonstration of this in action.

G-22. Kahn's Algorithm | Topological Sort Algorithm | BFS

This video, also from 'take U forward', explains Kahn's algorithm. It clearly introduces the concept of 'in-degree' and walks through how the queue and in-degree array work together.

Watch from 03:58 to 10:31. Focus on how nodes are only added to the queue when their in-degree drops to zero, signifying that all their prerequisite tasks are complete.

Complexity Analysis

Time Complexity: $O (V + E)$ . Calculating initial in-degrees takes $O (E)$ . Then, every vertex is enqueued and dequeued exactly once, and for each vertex, we iterate through its outgoing edges. This totals $O (V + E)$ .
Space Complexity: $O (V)$ . This space is for the in_degree array, the queue (which holds at most V vertices), and the result list.

Test your understanding!

Consider this DAG: 5 -> 0, 4 -> 0, 5 -> 2, 4 -> 1, 2 -> 3, 3 -> 1.

Trace Kahn's algorithm. What is the initial state of the queue? What is one possible final topological order?

Show answer

Calculate In-degrees:
- in-degree[0] = 2 (from 5 and 4)
- in-degree[1] = 2 (from 4 and 3)
- in-degree[2] = 1 (from 5)
- in-degree[3] = 1 (from 2)
- in-degree[4] = 0
- in-degree[5] = 0
Initialize Queue: The queue starts with all nodes having an in-degree of 0.
- Queue: [4, 5]
Process Queue:
- Dequeue 4. Add to result. Result: [4].
  - Neighbors of 4 are 0 and 1.
  - in-degree[0] becomes 1.
  - in-degree[1] becomes 1.
- Dequeue 5. Add to result. Result: [4, 5].
  - Neighbors of 5 are 0 and 2.
  - in-degree[0] becomes 0. Enqueue 0. Queue: [0].
  - in-degree[2] becomes 0. Enqueue 2. Queue: [0, 2].
- Dequeue 0. Add to result. Result: [4, 5, 0]. No neighbors to update.
- Dequeue 2. Add to result. Result: [4, 5, 0, 2].
  - Neighbor of 2 is 3.
  - in-degree[3] becomes 0. Enqueue 3. Queue: [3].
- Dequeue 3. Add to result. Result: [4, 5, 0, 2, 3].
  - Neighbor of 3 is 1.
  - in-degree[1] becomes 0. Enqueue 1. Queue: [1].
- Dequeue 1. Add to result. Result: [4, 5, 0, 2, 3, 1]. No neighbors to update.

The queue is now empty. A possible topological sort is [4, 5, 0, 2, 3, 1]. Note that if we had dequeued 5 before 4 initially, we would have gotten a different valid sort: [5, 4, 2, 0, 3, 1].

Implementation and Comparison

You now understand the theory behind both major topological sort algorithms. As a software engineer, it's valuable to see how these translate into code. This resource provides implementations in several common languages.

Topological Sort Algorithm | DFS & BFS - Tutorial

To see the code for both algorithms in C++, Java, Python, or JavaScript, this tutorial from 'takeUforward' is an excellent reference. It consolidates everything we've discussed into a practical format.

Scan through this resource. You don't need to read it word-for-word, but locate the code snippets for both the DFS-based and BFS-based (Kahn's Algorithm) approaches. Choose your preferred language and review the implementation to connect the theory to practice.

A crucial part of developing an architectural mindset is not just knowing how to implement something, but knowing the trade-offs between different approaches. When should you use the DFS method versus Kahn's algorithm?

Kahn's Algorithm vs DFS Approach: A Comparative Analysis

This GeeksforGeeks article provides a concise comparative analysis, which is perfect for understanding the trade-offs between the two algorithms.

Read just the 'Comparative Analysis' section. Pay attention to the advantages and disadvantages listed for each algorithm, as this helps you decide which one is better suited for a given situation.

In summary:

DFS-based approach is often simple to implement, especially if you already have a DFS framework. It's naturally recursive.
Kahn's algorithm (BFS-based) is iterative, which can be an advantage in some environments to avoid deep recursion stacks. It also has the useful property of being able to detect cycles as part of its main logic (if the sort doesn't include all vertices).

Conclusion

Congratulations! You've just added another essential graph algorithm to your toolkit. You now understand how to order the vertices of a DAG based on their dependencies, a problem that appears frequently in software engineering.

Key Takeaways:

Topological Sorting creates a linear ordering of vertices in a DAG to respect all prerequisite constraints.
The DFS-based method uses a post-order traversal logic, pushing nodes to a stack as they "finish" to reverse their finishing order.
Kahn's Algorithm (BFS-based) is an iterative method that uses a queue and tracks in-degrees to process nodes that have no remaining dependencies.
Both algorithms run in $O (V + E)$ time.

Preview of the Next Lesson:
We will now move into the next module, "Core Graph Algorithms." Our first lesson will be on Dijkstra's algorithm, which is used to find the shortest path between nodes in a weighted graph. This moves us from ordering and structure to finding optimal paths, a cornerstone of network routing, mapping services, and much more.