Topological Sort with DFS

Hello! Welcome back to our module on Graph Algorithms and Applications.

In the previous lesson, we implemented topological sort using Kahn's algorithm, a BFS-based approach that processes nodes by tracking their in-degrees. You saw how it systematically identifies nodes with no remaining prerequisites and adds them to a queue.

Today, we'll tackle the same problem from a different angle. Our goal is to implement topological sort on a DAG using a DFS-based approach. This method leverages the natural recursive structure of Depth-First Search to produce a valid ordering. By understanding both BFS and DFS-based solutions, you'll gain a more complete perspective on how different algorithmic strategies can solve the same problem, a key skill for evaluating trade-offs in system design.

1. The Core Idea: Post-Order Traversal

The intuition behind DFS-based topological sort is elegant. Think about what it means for a task (a node) to be "finished" in a dependency graph. A task can only be considered complete after all tasks that depend on it have been finished. In the context of a graph, a node is ready to be added to our sorted list only after we have fully explored all of its descendants.

This maps perfectly to a post-order traversal in DFS. In a recursive DFS, we visit a node, then recursively visit all its neighbors. The "post-order" step happens after all the recursive calls for its neighbors have returned.

The algorithm is as follows:

1. Start a DFS from an arbitrary unvisited node.
2. For the current node, recursively call DFS for all its unvisited neighbors.
3. Once all neighbors have been visited (i.e., the recursive calls have returned), add the current node to the front of our result list.
4. Repeat this process until all nodes in the graph have been visited.

Let's see this in action. The following video provides a clear, conceptual introduction and an animated walkthrough.

As the video illustrates, by adding each node to the result after its recursive calls complete, we ensure that for any edge $u\to v$, $v$ will be fully explored and added to the result before $u$ is. Since we add nodes to the front of the list (or append and then reverse), $u$ will ultimately appear before $v$ in the final ordering.

2. Implementing with Cycle Detection

The simple algorithm above assumes the graph is a DAG. In a real-world system, you can't make that assumption; you must handle invalid inputs gracefully. If the graph contains a cycle, a recursive DFS will loop forever, causing a stack overflow.

To make our implementation robust, we need to detect cycles. We can achieve this by tracking the state of each node during the DFS traversal. A node can be in one of three states:

1. Unvisited: We haven't seen this node yet.
2. Visiting: We are currently exploring this node's branch of the graph. It's on the current recursion call stack.
3. Visited: We have finished exploring this node and all of its descendants.

A cycle is detected if, during our DFS, we encounter a node that is currently in the "visiting" state. This means we've found a back edge—an edge that leads from a node back to one of its own ancestors in the DFS tree.

The following video, which solves the "Course Schedule II" LeetCode problem, gives a fantastic walkthrough of implementing this three-state logic in Python.

3. Production-Quality Python Implementation

Now, let's synthesize these concepts into a complete, robust Python function. We'll use two sets to manage the node states, just as shown in the NeetCode video.

from collections import defaultdict

def dfs_topological_sort(n, edges):
    """
    Performs a topological sort on a DAG using a DFS-based approach.

    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.
    """



    # Build adjacency list
    adj_list = defaultdict(list)
    for u, v in edges:
        adj_list[u].append(v)
        
    topological_order = []
    



    # States:
    # `path` (or 'visiting'): nodes in the current recursion stack (detects cycles).
    # `visited`: nodes that have been fully explored.
    path = set()
    visited = set()
    
    def dfs(node):



        # Base case for cycle detection
        if node in path:
            return False # Cycle detected
        



        # If already fully visited, no need to explore again
        if node in visited:
            return True # Successfully visited before




        # Mark as on the current path and start exploring
        path.add(node)
        
        for neighbor in adj_list.get(node, []):
            if not dfs(neighbor):
                return False # Propagate cycle detection signal
        



        # All neighbors explored, remove from current path
        path.remove(node)



        # Mark as fully visited
        visited.add(node)
        



        # This is the post-order step: add to the result
        topological_order.append(node)
        return True




    # Iterate through all nodes to handle disconnected components
    for i in range(n):
        if i not in visited:
            if not dfs(i):
                return [] # Cycle detected, return empty list




    # The list is built in reverse order, so we reverse it at the end
    return topological_order[::-1]




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

sorted_tasks = dfs_topological_sort(num_nodes, dependencies)

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



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




# Example with a cycle:
cyclic_deps = [[0, 1], [1, 2], [2, 0]]
sorted_tasks_cyclic = dfs_topological_sort(3, cyclic_deps)

if not sorted_tasks_cyclic:
    print("Correctly detected a cycle.")

Code Analysis

• path set: This corresponds to the cycle set in the video. It tracks nodes on the current recursion path. A node is added upon entering its dfs call and removed just before returning.
• visited set: This tracks nodes that have been completely processed. This prevents redundant work in graphs with multiple paths to the same node or in disconnected graphs.
• Return values: The dfs helper returns False to signal a cycle, which is propagated up the call stack to the main loop. This is a clean way to halt execution immediately.
• Final Reverse: Because we append nodes in post-order, the resulting list is a valid topological sort, but in reverse. We reverse it once at the very end to get the final order.

4. Connection to Your Background: Rust & Iterative DFS

Given your strong background in Rust, it's helpful to see how this recursive logic translates. The core principles of state management (visiting, visited) and post-order processing remain identical.

A final point on "production quality": deep recursion can cause stack overflow errors in any language. For extremely deep graphs (e.g., a dependency chain of millions of tasks), an iterative DFS using an explicit stack is a more robust alternative. While we won't implement it here, being aware of this trade-off between recursive elegance and iterative robustness is important.

Conclusion

Today, you've added a powerful, recursive alternative for topological sorting to your toolkit.

Key Takeaways:

• DFS-based topological sort relies on a post-order traversal. A node is added to the result only after all its descendants have been fully explored.
• Robust implementation requires cycle detection. This is typically done by maintaining three node states: unvisited, visiting (on the current recursion path), and visited.
• Encountering a node in the "visiting" state indicates a back edge and thus a cycle.
• The time and space complexity are both $O(V+E)$, identical to a standard DFS traversal. The space complexity includes the recursion stack depth, which can be up to $O(V)$ in the worst case.

Next Lesson Preview

You've now implemented topological sort using both a BFS-based (Kahn's) and a DFS-based algorithm. Which one is better? The answer, as is often the case in engineering, is "it depends." In the next lesson, we will compare the trade-offs between Kahn's algorithm and the DFS approach, discussing scenarios where one might be preferred over the other.