Topological Sort Using DFS in DSA C++

Mental Model

We visit each task and all the tasks that depend on it first, then add the task to the order. This way, tasks come after their prerequisites.

Analogy: Imagine you have to build a toy set where some parts must be assembled before others. You first build all parts that depend on this part, then add that part to the final set.

Graph:
0 -> 1 -> 3
↓    ↓
2    4

Order stack (empty at start): []
Visited nodes marked with ↑

Dry Run Walkthrough

Input: Graph edges: 5 nodes (0 to 4), edges: 0->1, 0->2, 1->3, 2->3, 1->4

Goal: Find an order to complete tasks so that each task comes after all its dependencies

Step 1: Start DFS at node 0, mark 0 visited

Visited: 0↑
Stack: []

Why: We begin from node 0 to explore its successors

Step 2: From 0, DFS to 1, mark 1 visited

Visited: 0↑ -> 1↑
Stack: []

Why: We must finish all tasks that depend on 1 before adding 1

Step 3: From 1, DFS to 3, mark 3 visited

Visited: 0↑ -> 1↑ -> 3↑
Stack: []

Why: 3 depends on 1, so explore it first

Step 4: 3 has no dependencies, add 3 to stack

Stack: [3]

Why: 3 is done, so add it to the order

Step 5: Back to 1, DFS to 4, mark 4 visited

Visited: 0↑ -> 1↑ -> 4↑
Stack: [3]

Why: Explore other tasks that depend on 1

Step 6: 4 has no dependencies, add 4 to stack

Stack: [3, 4]

Why: 4 is done, add to order

Step 7: All successors of 1 processed, add 1 to stack

Stack: [3, 4, 1]

Why: 1 can be added after its successors

Step 8: Back to 0, DFS to 2, mark 2 visited

Visited: 0↑ -> 2↑
Stack: [3, 4, 1]

Why: Explore other tasks that depend on 0

Step 9: From 2, DFS to 3 but 3 already visited

Visited: 0↑ -> 2↑
Stack: [3, 4, 1]

Why: 3 already processed, no need to revisit

Step 10: All successors of 2 processed, add 2 to stack

Stack: [3, 4, 1, 2]

Why: 2 can be added after its successors

Step 11: All successors of 0 processed, add 0 to stack

Stack: [3, 4, 1, 2, 0]

Why: 0 can be added after all its successors

Result:

Topological order (reverse stack): 0 -> 2 -> 1 -> 4 -> 3

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

class Graph {
public:
    int V;
    vector<vector<int>> adj;

    Graph(int V) {
        this->V = V;
        adj.resize(V);
    }

    void addEdge(int u, int v) {
        adj[u].push_back(v);
    }

    void dfs(int node, vector<bool>& visited, stack<int>& stk) {
        visited[node] = true; // mark node visited
        for (int neighbor : adj[node]) {
            if (!visited[neighbor]) {
                dfs(neighbor, visited, stk); // visit dependencies first
            }
        }
        stk.push(node); // add node after dependencies
    }

    void topologicalSort() {
        vector<bool> visited(V, false);
        stack<int> stk;

        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                dfs(i, visited, stk); // start DFS if not visited
            }
        }

        while (!stk.empty()) {
            cout << stk.top() << " ";
            stk.pop();
        }
        cout << endl;
    }
};

int main() {
    Graph g(5);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 3);
    g.addEdge(1, 4);

    g.topologicalSort();
    return 0;
}

visited[node] = true; // mark node visited

mark current node as visited to avoid revisiting

for (int neighbor : adj[node]) { if (!visited[neighbor]) { dfs(neighbor, visited, stk); } }

visit all successors of current node first

stk.push(node); // add node after dependencies

add node to stack after all successors are processed

for (int i = 0; i < V; i++) { if (!visited[i]) { dfs(i, visited, stk); } }

start DFS from all unvisited nodes to cover disconnected graph

while (!stk.empty()) { cout << stk.top() << " "; stk.pop(); }

print nodes in topological order by popping stack

Output

0 2 1 4 3 

Complexity Analysis

Time: O(V + E) because we visit each node and edge once during DFS

Space: O(V) for visited array and recursion stack in worst case

vs Alternative: Compared to Kahn's BFS approach, DFS uses recursion and stack but both have similar time complexity

Edge Cases

Empty graph (0 nodes)

No output, function handles gracefully

DSA C++

for (int i = 0; i < V; i++) { if (!visited[i]) { dfs(i, visited, stk); } }

Graph with no edges

All nodes printed in any order since no dependencies

DSA C++

for (int i = 0; i < V; i++) { if (!visited[i]) { dfs(i, visited, stk); } }

Graph with disconnected components

All components processed independently and combined in order

DSA C++

for (int i = 0; i < V; i++) { if (!visited[i]) { dfs(i, visited, stk); } }

When to Use This Pattern

When you need to order tasks with dependencies and detect a sequence where each task comes after its prerequisites, use topological sort with DFS to explore dependencies first.

Common Mistakes

Mistake: Adding the node to the order before visiting its successors
Fix: Add the node to the stack only after all its successors have been visited

Mistake: Not marking nodes as visited, causing infinite recursion
Fix: Mark nodes as visited at the start of DFS to avoid revisiting

Summary

It finds an order of tasks so that each task comes after all tasks it depends on.

Use it when you have tasks with dependencies and need a valid sequence to complete them.

The key is to visit all dependencies first, then add the task to the order.

Practice

1. What is the main purpose of using DFS in Topological Sort on a Directed Acyclic Graph (DAG)?

easy

A. To count the total number of nodes in the graph

B. To find the shortest path between two nodes

C. To detect cycles in an undirected graph

D. To visit nodes in a way that all dependencies come before the node

Solution

1. Step 1: Understand DFS role in Topological Sort

   DFS visits nodes deeply, ensuring all nodes reachable from a node are processed first.

2. Step 2: Relation to dependencies in DAG

   In Topological Sort, DFS ensures nodes are ordered so that all dependencies (edges) come before the node itself.

3. Final Answer:

   To visit nodes in a way that all dependencies come before the node -> Option D

4. Quick Check:

   DFS orders nodes respecting dependencies [OK]

Hint: DFS orders nodes so dependencies appear before dependents [OK]

Common Mistakes:

• Confusing DFS with BFS for topological order
• Thinking DFS finds shortest paths
• Assuming DFS detects cycles in undirected graphs here

2. Which of the following is the correct way to mark a node as visited in a DFS-based topological sort in C++?

easy

A. visited(node) = true;

B. visited[node] = true;

C. visited[node] == true;

D. visited[node] != false;

Solution

1. Step 1: Understand C++ syntax for arrays or vectors

   To mark a node visited, we assign true to visited[node] using = operator.

2. Step 2: Analyze options for correctness

   visited[node] = true; uses correct syntax: visited[node] = true; Options A, C, D use wrong syntax or comparison operators.

3. Final Answer:

   visited[node] = true; -> Option B

4. Quick Check:

   Assignment uses =, not == or function call [OK]

Hint: Use = to assign true to visited[node] in C++ [OK]

Common Mistakes:

• Using == instead of = for assignment
• Using parentheses instead of brackets for indexing
• Using != false which is confusing and incorrect here

3. What will be the output topological order of the following graph using DFS?

Edges:
0 -> 1
0 -> 2
1 -> 3
2 -> 3

medium

A. [0, 1, 2, 3]

B. [3, 1, 2, 0]

C. [0, 2, 1, 3]

D. [1, 0, 2, 3]

Solution

1. Step 1: Perform DFS starting from node 0

   Visit 0, then 1 and 3, then backtrack and visit 2 and 3 (already visited). The order of finishing nodes is 3,1,2,0 reversed gives topological order.

2. Step 2: Determine topological order

   Reversing finishing times gives [0, 2, 1, 3].

3. Final Answer:

   [0, 2, 1, 3] -> Option C

4. Quick Check:

   DFS finishing order reversed = [0,2,1,3] [OK]

Hint: Reverse DFS finishing order for topological sort output [OK]

Common Mistakes:

• Not reversing the DFS finishing order
• Visiting nodes in wrong order
• Confusing edges direction

4. Identify the error in this DFS-based topological sort code snippet:

void dfs(int node, vector<bool> &visited, stack<int> &st, vector<int> adj[]) {
  visited[node] = true;
  for (auto x : adj[node]) {
    if (!visited[x])
      dfs(x, visited, st, adj);
  }
  st.push(node);
}

// Called for all nodes
for (int i = 0; i < n; i++) {
  if (!visited[i])
    dfs(i, visited, st, adj);
}

medium

A. No error; code correctly implements DFS topological sort

B. Visited array should be reset inside dfs

C. Stack should be replaced with queue

D. Nodes should be pushed to stack before recursive calls

Solution

1. Step 1: Analyze DFS function logic

   DFS marks node visited, recursively visits neighbors, then pushes node to stack after all neighbors processed.

2. Step 2: Check correctness of stack usage and visited array

   Stack is used to store nodes in finishing order, visited array is correctly used and not reset inside DFS.

3. Final Answer:

   No error; code correctly implements DFS topological sort -> Option A

4. Quick Check:

   DFS post-order push to stack is correct [OK]

Hint: Push node after recursion to stack for correct order [OK]

Common Mistakes:

• Pushing node before recursion causing wrong order
• Resetting visited inside DFS causing infinite loops
• Using queue instead of stack for topological order

5. Given a graph with edges:

5 -> 2
5 -> 0
4 -> 0
4 -> 1
2 -> 3
3 -> 1

Which of the following is a valid topological sort using DFS?

hard

A. [5, 4, 2, 3, 1, 0]

B. [4, 5, 0, 2, 1, 3]

C. [0, 1, 2, 3, 4, 5]

D. [1, 3, 2, 0, 4, 5]

Solution

1. Step 1: Analyze dependencies from edges

   5 -> 2, 5 -> 0 mean 5 before 2 and 0; 4 -> 0, 4 -> 1 mean 4 before 0 and 1; 2 -> 3 mean 2 before 3; 3 -> 1 mean 3 before 1. So 5 and 4 come before their successors.

2. Step 2: Validate options respecting dependencies

   [5, 4, 2, 3, 1, 0] respects all edges: 5 before 2 and 0, 4 before 0 and 1, 2 before 3, 3 before 1. Others violate these orders.

3. Final Answer:

   [5, 4, 2, 3, 1, 0] -> Option A

4. Quick Check:

   All edges respected in order [OK]

Hint: Check all edges point forward in topological order [OK]

Common Mistakes:

• Ignoring edge directions
• Placing dependent nodes before dependencies
• Assuming any order is valid