G-21: Topological Sort Algorithm | DFS

Topological sorting is a fundamental graph algorithm used to linearize dependent tasks, heavily utilized in build systems, course prerequisite trackers, and package managers. This chapter covers the theoretical foundations of topological sort, why it is restricted to Directed Acyclic Graphs (DAGs), and how to implement it efficiently using Depth-First Search (DFS) alongside a stack.

1. Why Do We Need Topological Sort? (Problem Statement)

In many real-world scenarios, tasks have dependencies. For instance, in a university curriculum, you cannot take Advanced Algorithms without first passing Data Structures.

• Definition: Topological sorting is a linear ordering of vertices in a directed graph such that for every directed edge from vertex $u$ to vertex $v$ ($u \to v$), vertex $u$ comes before vertex $v$ in the ordering.
• Key Constraint: Topological sorting only exists on Directed Acyclic Graphs (DAGs). If a graph contains cycles or undirected edges, a valid topological sort is impossible.

2. Core Mental Model & Real-Life Analogy

Real-Life Analogy: Getting Dressed

Imagine getting dressed in the morning. Certain items depend on others:

• You must put on your socks before your shoes.
• You must put on your undershirt before your jacket.

If you try to map these dependencies out, you create a directed graph where an edge points from a prerequisite to the dependent item. A topological sort gives you a valid, sequential list of instructions on what order to put your clothes on without violating any dependencies.

3. Why Only Directed Acyclic Graphs (DAGs)?

The algorithm strictly requires two graph properties: Directed and Acyclic.

1. Why Directed? If a graph is undirected, an edge between node $1$ and node $2$ implies bidirectional dependencies ($1 \to 2$ and $2 \to 1$). This creates an impossible paradox where $1$ must appear before $2$, and $2$ must appear before $1$.

2. Why Acyclic (No Cycles)? If a graph contains a cycle (e.g., $1 \to 2$, $2 \to 3$, and $3 \to 1$), it creates a circular dependency:

   • $1$ must come before $2$
   • $2$ must come before $3$
   • $3$ must come before $1$

   It is mathematically impossible to arrange these in a linear sequence. Thus, cycles break topological sorting entirely.

4. Visualizing the Graph & Adjacency List

Consider a directed acyclic graph (DAG) with nodes from $0$ to $5$ and the following directed edges:

• $5 \to 0$
• $4 \to 0$
• $5 \to 2$
• $2 \to 3$
• $3 \to 1$
• $4 \to 1$

Valid Linear Orderings

Depending on how you traverse the graph, multiple valid topological orderings can exist. Two valid examples for the above graph include:

• [5, 4, 2, 3, 1, 0]
• [4, 5, 2, 3, 1, 0]

Let's verify the first ordering [5, 4, 2, 3, 1, 0] against our edge constraints:

5 appears before 0  (Valid)
4 appears before 0  (Valid)
5 appears before 2  (Valid)
2 appears before 3  (Valid)
3 appears before 1  (Valid)
4 appears before 1  (Valid)

5. Step-by-Step DFS Algorithm Walkthrough

To find the topological sort using DFS, we use a Visited Array to keep track of visited nodes and a Stack to store nodes in the order their DFS completions finish.

Algorithm Steps:

1. Initialize a visited array of size $V$ with all zeros (unvisited).
2. Initialize an empty Stack.
3. Iterate through all nodes from $0$ to $V-1$. If a node is not visited, trigger a DFS call on it.
4. Inside the DFS function:
   • Mark the current node as visited ($1$).
   • Recursively visit all unvisited adjacent neighbors.
   • Once all neighbors are explored, push the current node onto the Stack before returning.
5. After all nodes are processed, pop elements from the stack one by one to get the final topological ordering.

Trace Execution on Sample Graph:

• Start at Node 0: Mark visited. No unvisited neighbors. Push 0 to Stack. Stack: [0]
• Start at Node 1: Mark visited. No unvisited neighbors. Push 1 to Stack. Stack: [0, 1]
• Start at Node 2: Mark visited. Go to neighbor 3.
  • Node 3: Mark visited. Go to neighbor 1 (already visited, skip). Push 3 to Stack. Stack: [0, 1, 3]
  • Return to 2. Push 2 to Stack. Stack: [0, 1, 3, 2]
• Start at Node 4: Mark visited. Neighbors 0 and 1 are already visited. Push 4 to Stack. Stack: [0, 1, 3, 2, 4]
• Start at Node 5: Mark visited. Neighbors 0 and 2 are already visited. Push 5 to Stack. Stack: [0, 1, 3, 2, 4, 5]

Pop elements from the stack:

6. Implementation Code (C++ & Java)

C++ Implementation

class Solution {
private:
    void dfs(int node, int vis[], stack<int>& st, vector<int> adj[]) {
        vis[node] = 1;
        for (auto it : adj[node]) {
            if (!vis[it]) {
                dfs(it, vis, st, adj);
            }
        }
        st.push(node); // Push to stack after all descendants are visited
    }

public:
    vector<int> topologicalSort(int V, vector<int> adj[]) {
        int vis[V] = {0};
        stack<int> st;
        
        for (int i = 0; i < V; i++) {
            if (!vis[i]) {
                dfs(i, vis, st, adj);
            }
        }
        
        vector<int> ans;
        while (!st.empty()) {
            ans.push_back(st.top());
            st.pop();
        }
        return ans;
    }
};

Java Implementation

class Solution {
    private static void dfs(int node, int vis[], Stack<int> st, ArrayList<ArrayList<Integer>> adj) {
        vis[node] = 1;
        for (int it : adj.get(node)) {
            if (vis[it] == 0) {
                dfs(it, vis, st, adj);
            }
        }
        st.push(node);
    }

    public static int[] topologicalSort(ArrayList<ArrayList<Integer>> adj, int V) {
        int vis[] = new int[V];
        Stack<Integer> st = new Stack<>();
        
        for (int i = 0; i < V; i++) {
            if (vis[i] == 0) {
                dfs(i, vis, st, adj);
            }
        }
        
        int ans[] = new int[V];
        int i = 0;
        while (!st.isEmpty()) {
            ans[i++] = st.peek();
            st.pop();
        }
        return ans;
    }
}

7. Complexity Analysis

8. Summary and Key Takeaways

• Definition Check: Topological sort provides a linear ordering of vertices in a DAG such that for every edge $u \to v$, $u$ precedes $v$.
• Graph Restrictions: Valid only on Directed Acyclic Graphs (DAGs). Cycles or undirected edges make topological sorting impossible.
• The Stack Mechanism: By pushing a node to a stack only after its entire DFS branch is fully explored, we ensure that deeper dependent nodes settle at the bottom of the stack, while prerequisites settle at the top.
• Component Coverage: Always loop through all nodes from $0$ to $V-1$ to handle disconnected components in the graph.
• Optimal Efficiency: Achieves an optimal linear time complexity of $O(V + E)$, matching standard DFS performance.