Topological Sort Using DFS in DSA C++ - Execution Trace

Concept Flow - Topological Sort Using DFS

Start DFS at unvisited node

↓

Mark node as visited

↓

For each neighbor

↓

If neighbor unvisited

↓

Recursive DFS on neighbor

↓

After all neighbors visited

↓

Push node to stack

↓

Repeat for all nodes

↓

Pop all nodes from stack for topological order

Start DFS from each unvisited node, visit all neighbors recursively, then push the node to a stack. Finally, pop nodes from the stack to get topological order.

Execution Sample

DSA C++

void dfs(int node) {
  visited[node] = true;
  for (int nbr : graph[node]) {
    if (!visited[nbr]) dfs(nbr);
  }
  stack.push(node);
}

This code visits nodes recursively and pushes them onto a stack after visiting all neighbors.

Execution Table

Step	Operation	Current Node	Visited Set	Stack State	Visual State
1	Start DFS at node 5	5	{}	[]	Graph nodes: 5->2, 5->0, 4->0, 4->1, 2->3, 3->1
2	Mark 5 visited	5	{5}	[]	5 visited
3	Visit neighbor 2	2	{5}	[]	Moving to 2
4	Mark 2 visited	2	{5,2}	[]	2 visited
5	Visit neighbor 3	3	{5,2}	[]	Moving to 3
6	Mark 3 visited	3	{5,2,3}	[]	3 visited
7	Visit neighbor 1	1	{5,2,3}	[]	Moving to 1
8	Mark 1 visited	1	{5,2,3,1}	[]	1 visited
9	No neighbors for 1	1	{5,2,3,1}	[]	Push 1 to stack
10	Push 1	1	{5,2,3,1}	[1]	Stack: [1]
11	Back to 3, all neighbors visited	3	{5,2,3,1}	[1]	Push 3 to stack
12	Push 3	3	{5,2,3,1}	[1,3]	Stack: [1,3]
13	Back to 2, all neighbors visited	2	{5,2,3,1}	[1,3]	Push 2 to stack
14	Push 2	2	{5,2,3,1}	[1,3,2]	Stack: [1,3,2]
15	Back to 5, visit neighbor 0	0	{5,2,3,1}	[1,3,2]	Moving to 0
16	Mark 0 visited	0	{5,2,3,1,0}	[1,3,2]	0 visited
17	No neighbors for 0	0	{5,2,3,1,0}	[1,3,2]	Push 0 to stack
18	Push 0	0	{5,2,3,1,0}	[1,3,2,0]	Stack: [1,3,2,0]
19	Back to 5, all neighbors visited	5	{5,2,3,1,0}	[1,3,2,0]	Push 5 to stack
20	Push 5	5	{5,2,3,1,0}	[1,3,2,0,5]	Stack: [1,3,2,0,5]
21	Start DFS at node 4	4	{5,2,3,1,0}	[1,3,2,0,5]	Moving to 4
22	Mark 4 visited	4	{5,2,3,1,0,4}	[1,3,2,0,5]	4 visited
23	Visit neighbor 0 (already visited)	0	{5,2,3,1,0,4}	[1,3,2,0,5]	Skip 0
24	Visit neighbor 1 (already visited)	1	{5,2,3,1,0,4}	[1,3,2,0,5]	Skip 1
25	All neighbors visited for 4	4	{5,2,3,1,0,4}	[1,3,2,0,5]	Push 4 to stack
26	Push 4	4	{5,2,3,1,0,4}	[1,3,2,0,5,4]	Stack: [1,3,2,0,5,4]
27	All nodes visited	-	{5,2,3,1,0,4}	[1,3,2,0,5,4]	DFS complete
28	Pop all from stack for order	-	-	-	Topological order: 4,5,0,2,3,1

💡 All nodes visited and stack contains nodes in reverse topological order

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 8	After Step 10	After Step 14	After Step 18	After Step 20	After Step 26	Final
visited	{}	{5}	{5,2}	{5,2,3}	{5,2,3,1}	{5,2,3,1}	{5,2,3,1}	{5,2,3,1,0}	{5,2,3,1,0}	{5,2,3,1,0,4}	{5,2,3,1,0,4}
stack	[]	[]	[]	[]	[]	[1]	[1,3,2]	[1,3,2,0]	[1,3,2,0,5]	[1,3,2,0,5,4]	[1,3,2,0,5,4]

Key Moments - 3 Insights

Why do we push the node to the stack only after visiting all its neighbors?

Because in the execution_table rows 9-10 and 11-12, nodes are pushed after all neighbors are visited, ensuring dependencies come before the node in the final order.

What happens if a neighbor is already visited during DFS?

As shown in rows 23-24, the DFS skips already visited neighbors to avoid cycles and repeated work.

Why do we pop nodes from the stack to get the topological order?

Because nodes are pushed after visiting neighbors, the stack reverses this order. Popping gives the correct topological order as in row 28.

Visual Quiz - 3 Questions

Look at the execution_table at step 10, what is the stack state?

A [1]

B [1,3]

C []

D [3]

💡 Hint

Check the 'Stack State' column at step 10 in execution_table

At which step does node 4 get pushed onto the stack?

A Step 20

B Step 18

C Step 26

D Step 14

💡 Hint

Look for 'Push 4' operation in execution_table

If node 3 had an additional neighbor 6 unvisited, what would change in the execution_table?

A Node 3 would be pushed to stack earlier

B DFS would visit node 6 before pushing 3 to stack

C Node 6 would be skipped as visited

D Stack would be empty

💡 Hint

Recall DFS visits all unvisited neighbors before pushing current node (see steps 5-12)

Concept Snapshot

Topological Sort Using DFS:
- Visit each unvisited node with DFS
- Recursively visit all neighbors first
- Push node to stack after neighbors
- Pop stack for topological order
- Ensures dependencies come before dependents

Full Transcript

Topological sort using DFS works by visiting each node that is not yet visited. For each node, we mark it visited and recursively visit all its neighbors. After visiting all neighbors, we push the node onto a stack. This ensures that nodes with dependencies come after their dependencies in the stack. After DFS completes for all nodes, popping nodes from the stack gives the topological order. The execution trace shows step-by-step how nodes are visited, pushed to stack, and how the visited set and stack evolve. Key moments include why nodes are pushed after neighbors and how visited nodes are skipped. The final topological order is obtained by popping all nodes from the stack.

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