Topological Sort: DFS Approach

1. The Core Idea: Finishing Times and Post-Order Traversal

The insight behind the DFS-based approach lies in the properties of a post-order traversal. In a standard DFS, a recursive call dfs(u) only finishes after all recursive calls for vertices reachable from u have completed.

Think about what this means in the context of dependencies. If there's an edge $u\to v$, u is a prerequisite for v. In a topological sort, u must appear before v. Now consider the DFS traversal. When we call dfs(u), we will eventually explore v. The call to dfs(v) (and everything reachable from it) must finish before the call to dfs(u) can finish.

This gives us a crucial relationship: If there is an edge $u\to v$, then the finishing time of v in a DFS is always earlier than the finishing time of u.

This suggests a simple algorithm:

1. Run a DFS on the entire graph.
2. Keep a list of vertices in the order they finish their DFS calls.
3. The reverse of this list is a valid topological ordering.

A stack is the perfect data structure for this. When a vertex u finishes its DFS exploration (i.e., after the recursive calls for all its neighbors have returned), we push u onto a stack. After the entire DFS is complete, popping elements from the stack will yield the topological sort.

2. The DFS-Based Algorithm

Let's formalize the step-by-step process. You'll need an adjacency list representation of the graph, a visited array to track explored nodes, and a stack to store the topological order.

1. Initialization: Create an empty stack, say st, and initialize a visited array for all vertices to false.

2. Main Loop: Iterate through each vertex i from 0 to V-1. If visited[i] is false, start a DFS from that vertex by calling a recursive helper function, dfs_topo(i, visited, st, adj). This loop ensures that we cover all components of the graph, even if it's disconnected.

3. Recursive Helper dfs_topo(u):
   a. Mark the current vertex u as visited: visited[u] = true.
   b. Iterate through all neighbors v of u.
   c. If a neighbor v has not been visited (visited[v] == false), make a recursive call: dfs_topo(v, ...).
   d. After the loop over all neighbors is complete, it means we have explored all nodes reachable from u. Now, u has "finished". Push u onto the stack: st.push(u).

4. Final Result: Once the main loop is done, the stack st contains the vertices in a topologically sorted order. You can pop them one by one into a result vector.

The following animated GIF provides a fantastic visualization of this process. The "closed nodes" (orange) are nodes whose DFS has finished, and they are added to the toposort array, which functions like our stack.

For a guided walkthrough with a clear explanation tailored to competitive programming, the following video is an excellent resource.

3. Implementation and Correctness

Now, let's put everything together with a formal C++ implementation and a look at the proof of correctness, which you've indicated is important to you.

C++ Implementation

The implementation is a straightforward translation of the algorithm described above. The cp-algorithms website provides a very clean and standard implementation for competitive programming.

The core C++ code looks like this:

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

void dfs_topo(int u, std::vector<bool>& visited, std::stack<int>& st, const std::vector<std::vector<int>>& adj) {
    visited[u] = true;
    for (int v : adj[u]) {
        if (!visited[v]) {
            dfs_topo(v, visited, st, adj);
        }
    }
    // After visiting all reachable nodes, push current node to stack
    st.push(u);
}

std::vector<int> topologicalSort(int V, const std::vector<std::vector<int>>& adj) {
    std::stack<int> st;
    std::vector<bool> visited(V, false);

    for (int i = 0; i < V; ++i) {
        if (!visited[i]) {
            dfs_topo(i, visited, st, adj);
        }
    }

    std::vector<int> topo_order;
    while (!st.empty()) {
        topo_order.push_back(st.top());
        st.pop();
    }

    return topo_order;
}

Why Does This Work? A Proof of Correctness

Your preference for understanding the "why" is crucial for deep mastery. The correctness of this algorithm hinges on the classification of edges in a DFS traversal of a DAG. As we know, a DAG by definition has no cycles, which means a DFS traversal on it will produce no back edges.

A back edge is an edge (u, v) where v is an ancestor of u in the DFS tree. The absence of back edges is key. Let's consider any arbitrary edge (u, v) in our DAG. When the DFS explores this edge from u, only two scenarios are possible for the state of v:

1. v is unvisited: The DFS will make a recursive call dfs_topo(v). By the nature of recursion, this call must finish (and v be pushed to the stack) before the call for u can finish. Thus, u is pushed onto the stack after v, ensuring u comes before v in the final topological order.

2. v has already been visited: Since there are no back edges, v cannot be an ancestor of u. This means dfs_topo(v) has already completed. Therefore, v is already on the stack (or will be added lower down the stack than u). u will be pushed on top of v later. Again, u comes before v.

In all possible cases, for any edge (u, v), vertex u is placed in the final ordering before vertex v. This satisfies the definition of a topological sort.

For a more formal treatment of this proof, the following university lecture slides are excellent.

4. Complexity Analysis

• Time Complexity: $O(V+E)$. The algorithm is a standard DFS traversal. Each vertex is visited once, and every edge is considered once.
• Space Complexity: $O(V)$. This is required for the visited array, the recursion stack (which can go V deep in the worst case of a path graph), and the stack used to store the topological order.

Conclusion

You now have a second, equally efficient method for generating a topological sort. The DFS-based approach is often considered more concise to implement recursively and provides a different but powerful perspective based on post-order traversal and finishing times.

Key Takeaways:

• The DFS-based topological sort orders vertices by their reverse finishing times.
• The logic relies on the fact that for any edge $u\to v$ in a DAG, the DFS call for v will always finish before the call for u.
• A stack is the natural data structure to collect vertices as they finish, which automatically reverses the finishing order.
• Like Kahn's algorithm, this method runs in linear time, $O(V+E)$, and has linear space complexity, $O(V)$.
• This algorithm implicitly detects cycles. If a back edge is found during DFS (which we covered in Module 2), the graph is not a DAG, and no topological sort exists.

In our next lesson, we will start applying these sorting algorithms. You'll learn how to use a topological sort to solve Dynamic Programming problems on DAGs, a very common and powerful pattern for finding shortest paths, longest paths, and counting paths in directed acyclic graphs.