Topological Sort for DAGs

The Five Concepts for Today

We will build our understanding of topological sort through these five concepts:

1. The Core Idea of Topological Sort: What it is and why it's useful.
2. The Prerequisite: Directed Acyclic Graphs (DAGs): Why cycles make ordering impossible.
3. Kahn's Algorithm: An intuitive, BFS-based approach using in-degrees.
4. DFS-based Algorithm: An elegant approach that leverages the "finishing time" of nodes in a DFS traversal.
5. Advanced Topics & Interview Context: Cycle detection, non-uniqueness, and applying these algorithms to classic interview problems.

Concept 1: The Core Idea of Topological Sort

Technical Explanation

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

Think of it as "flattening" a graph of dependencies into a single valid sequence. If a node represents a task and an edge A -> B means "task A must be completed before task B," a topological sort gives you a valid order to execute all tasks.

This has wide-ranging applications in real-world systems:

• Build Systems (e.g., Make, Bazel): Compiling source files in the correct order based on dependencies.
• Package Managers (e.g., pip, npm): Installing library dependencies before installing the library that needs them.
• Task Scheduling: Executing jobs in a data processing pipeline (e.g., Apache Airflow, Dagster).
• University Course Prerequisites: Determining a valid sequence of courses to take.

Metaphor: Getting Dressed

Imagine you're getting dressed. You have a set of dependencies:

• You must put on socks before shoes.
• You must put on your shirt before your jacket.
• You can put on your pants at any time relative to your shirt.

A topological sort gives you a valid sequence, like [socks, pants, shirt, shoes, jacket]. Another valid sequence is [pants, socks, shirt, jacket, shoes]. The key is that socks always appears before shoes, and shirt always before jacket.

Concept 2: The Prerequisite: Directed Acyclic Graphs (DAGs)

Technical Explanation

Topological sorting is only defined for Directed Acyclic Graphs (DAGs). This is a critical constraint. If a graph contains a cycle, a linear ordering is impossible.

Consider a simple cycle: A -> B -> C -> A.

• The edge A -> B means A must come before B.
• The edge B -> C means B must come before C.
• The edge C -> A means C must come before A.

If we try to create an ordering, we get a logical contradiction: A must come before B, which must come before C, which must come before A. There's no starting point and no valid sequence.

This is why your knowledge from the previous lesson is so important. Before attempting a topological sort, you must be sure the graph is a DAG. The 3-color DFS cycle detection algorithm is the perfect tool for this verification.

Metaphor: The Chicken and Egg Problem

A cycle is the classic "chicken and egg" paradox. If a chicken must come from an egg, and an egg must come from a chicken, which came first? There is no linear starting point. A topological sort requires at least one "first" item—a node with no prerequisites. A cycle ensures no such node exists among the cycle's members.

Python Code: The Prerequisite Check

We won't write new code here. The has_cycle_directed function from our last lesson is the tool you would use. If it returns True, you cannot perform a topological sort.

# From previous lesson:
# if has_cycle_directed(my_graph):
#     print("Cannot perform topological sort: graph contains a cycle.")
# else:
#     # Proceed with one of the algorithms below...

Concept 3: Kahn's Algorithm (BFS-based)

Technical Explanation

Kahn's algorithm is an intuitive, BFS-based approach to topological sorting. It works by iteratively identifying nodes that have no more pending dependencies and adding them to the sorted list.

The core concept is the in-degree of a node: the number of incoming edges. A node with an in-degree of 0 has no prerequisites and can be executed.

The algorithm proceeds as follows:

1. Compute In-degrees: Calculate the in-degree for every vertex in the graph. This takes $O(V+E)$ time.
2. Initialize Queue: Create a queue and add all vertices with an in-degree of 0.
3. Process Queue:
   a. While the queue is not empty, dequeue a vertex u.
   b. Add u to your topologically sorted list.
   c. For each neighbor v of u:
   i. Decrement the in-degree of v.
   ii. If the in-degree of v becomes 0, enqueue v.

This process mimics a real-world workflow: complete a task, and then check which subsequent tasks are now "unlocked."

Python Code: Kahn's Algorithm

from collections import deque, defaultdict

def topological_sort_kahns(num_nodes: int, edges: list[list[int]]):
    """
    Performs topological sort using Kahn's algorithm (BFS-based).

    Args:
        num_nodes: The total number of nodes in the graph, labeled 0 to n-1.
        edges: A list of edges, where each edge is [u, v] for u -> v.

    Returns:
        A list of nodes in topological order, or an empty list if a cycle exists.
    """
    adj = defaultdict(list)
    in_degree = {i: 0 for i in range(num_nodes)}

    for u, v in edges:
        adj[u].append(v)
        in_degree[v] += 1

    queue = deque([node for node in range(num_nodes) if in_degree[node] == 0])
    topo_order = []

    while queue:
        u = queue.popleft()
        topo_order.append(u)

        for v in adj[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)

    # This is a crucial check we will formalize in Concept 5
    if len(topo_order) == num_nodes:
        return topo_order
    else:
        # Graph has a cycle
        return []

# Example: Course prerequisites
# 0: CS101, 1: CS102, 2: CS201, 3: CS210, 4: CS301
# CS101 -> CS102, CS102 -> CS201, CS102 -> CS210, CS201 -> CS301
edges_example = [[0, 1], [1, 2], [1, 3], [2, 4]]
num_nodes_example = 5

print(f"Kahn's Algorithm Order: {topological_sort_kahns(num_nodes_example, edges_example)}")
# Possible output: [0, 1, 2, 3, 4] or [0, 1, 3, 2, 4]

Concept 4: DFS-based Algorithm

Technical Explanation

The second major approach uses DFS. The logic is slightly less direct than Kahn's but is incredibly elegant once understood. It builds on the idea of a node's "finishing time" in a DFS traversal.

Recall from our last lesson that in a recursive DFS, a function call for a node u only "finishes" (returns) after all of its descendants have been fully explored.

• This means if there's a path u -> v, the DFS call for v will finish before the DFS call for u.
• Therefore, the reverse of the finishing order of the nodes gives a valid topological sort.

The algorithm:

1. Initialize a visited set and a stack (or a list to be used as a stack).
2. Iterate through all nodes in the graph. If a node hasn't been visited, start a DFS from it.
3. In the dfs function for a node u:
   a. Mark u as visited.
   b. For each neighbor v of u, if v is not visited, recursively call dfs(v).
   c. After the loop over neighbors finishes, push u onto the stack. This is the crucial step. It's a post-order traversal.
4. Once the main loop is done, the stack contains the topologically sorted nodes. Popping them one by one (or simply reversing the list) gives the final order.

Python Code: DFS-based Algorithm

This implementation assumes the graph is a DAG. For a production setting, you'd combine this with the 3-color cycle detection logic.

def topological_sort_dfs(num_nodes: int, edges: list[list[int]]):
    """
    Performs topological sort using a DFS-based algorithm.
    """
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
    
    visited = set()
    # In Python, a list is an easy way to implement a stack.
    # We will append to it and then reverse at the end.
    topo_order_stack = []

    def dfs(u):
        visited.add(u)
        for v in adj[u]:
            if v not in visited:
                dfs(v)
        # This is the post-order step. u is added only after all its
        # descendants are processed and added to the stack.
        topo_order_stack.append(u)

    for i in range(num_nodes):
        if i not in visited:
            dfs(i)
    
    # The stack contains the reverse topological order.
    return topo_order_stack[::-1]

print(f"DFS-based Algorithm Order: {topological_sort_dfs(num_nodes_example, edges_example)}")
# Possible output: [0, 1, 3, 2, 4] or [0, 1, 2, 3, 4]

Concept 5: Advanced Topics & Interview Context

Technical Explanation

Mastering topological sort for interviews means going beyond just the implementation. You need to understand the nuances and common pitfalls.

1. Cycle Detection with Kahn's Algorithm:
Kahn's algorithm has a built-in, elegant way to detect cycles. After the while loop finishes, if the number of nodes in your topo_order list is less than the total number of nodes in the graph, it means the graph has a cycle. Why? The nodes within a cycle (and any nodes that depend on them) will never have their in-degrees reduced to 0, so they will never be added to the queue and processed.

2. Non-Uniqueness of Solutions:
As seen in our examples, a topological sort is often not unique. Any time the queue in Kahn's algorithm contains more than one node, you have a choice. For example, if both taskA and taskB have an in-degree of 0, you can start with either. This is a great clarifying question to ask an interviewer: "Does the problem require any specific topological order, or is any valid order acceptable?"

3. DFS vs. Kahn's - The Trade-offs:

For your goals of working on large-scale systems, the parallelism aspect of Kahn's is a noteworthy advantage.

4. Classic Interview Problems:
Topological sort is rarely asked directly. It's usually the core of a word problem.

• Course Schedule (LeetCode 207 & 210): The quintessential topological sort problem. Given prerequisites, can you finish all courses? (Cycle detection). If so, what is one valid order? (Topological sort).
• Alien Dictionary (LeetCode 269): A harder problem where you must first derive the dependency graph from a list of lexicographically sorted words in an alien language, and then perform a topological sort. For ["wrt", "wrf"], you can infer that t must come before f.

Conclusion

You have now added a powerful and practical algorithm to your graph toolkit. Topological sort is the definitive way to handle problems involving order and dependencies.

Key Takeaways:

• Topological Sort creates a linear ordering of nodes in a Directed Acyclic Graph (DAG).
• The presence of a cycle makes a topological sort impossible.
• Kahn's Algorithm (BFS-based) is an intuitive method that uses in-degrees and a queue to process nodes with no pending dependencies. It can also detect cycles if the final sorted list is incomplete.
• The DFS-based Algorithm is an elegant method that relies on the post-order traversal of nodes; the reverse of the node "finishing times" yields a valid sort.
• Both algorithms have a time complexity of $O(V+E)$ and a space complexity of $O(V+E)$ (for the adjacency list) or $O(V)$ for auxiliary structures.

Preview of the Next Lesson:
We've explored unweighted graphs with BFS and DAGs with topological sort. Now, we'll introduce weights to our edges. In the next lesson, we will tackle Dijkstra's Algorithm, the classic method for finding the single-source shortest path in a weighted graph with non-negative edge weights. This is a fundamental algorithm for everything from network routing to mapping applications.