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 neighbor : graph[node]) {
    if (!visited[neighbor]) dfs(neighbor);
  }
  stack.push(node);
}

This code visits nodes recursively and pushes them to 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,4,3,2,1,0; No nodes visited
2	Visit node 5	5	{5}	[]	Visited 5
3	Check neighbors of 5: 2,0	5	{5}	[]	Neighbors 2 and 0 unvisited
4	DFS on neighbor 2	2	{5}	[]	Move to node 2
5	Visit node 2	2	{2,5}	[]	Visited 2
6	Check neighbors of 2: 3	2	{2,5}	[]	Neighbor 3 unvisited
7	DFS on neighbor 3	3	{2,5}	[]	Move to node 3
8	Visit node 3	3	{2,3,5}	[]	Visited 3
9	Check neighbors of 3: 1	3	{2,3,5}	[]	Neighbor 1 unvisited
10	DFS on neighbor 1	1	{2,3,5}	[]	Move to node 1
11	Visit node 1	1	{1,2,3,5}	[]	Visited 1
12	Check neighbors of 1: none	1	{1,2,3,5}	[]	No neighbors
13	Push node 1 to stack	1	{1,2,3,5}	[1]	Stack: 1
14	Return to node 3	3	{1,2,3,5}	[1]	Back to 3
15	Push node 3 to stack	3	{1,2,3,5}	[1,3]	Stack: 1 -> 3
16	Return to node 2	2	{1,2,3,5}	[1,3]	Back to 2
17	Push node 2 to stack	2	{1,2,3,5}	[1,3,2]	Stack: 1 -> 3 -> 2
18	Return to node 5	5	{1,2,3,5}	[1,3,2]	Back to 5
19	Check neighbor 0 of 5	5	{1,2,3,5}	[1,3,2]	Neighbor 0 unvisited
20	DFS on neighbor 0	0	{1,2,3,5}	[1,3,2]	Move to node 0
21	Visit node 0	0	{0,1,2,3,5}	[1,3,2]	Visited 0
22	Check neighbors of 0: none	0	{0,1,2,3,5}	[1,3,2]	No neighbors
23	Push node 0 to stack	0	{0,1,2,3,5}	[1,3,2,0]	Stack: 1 -> 3 -> 2 -> 0
24	Return to node 5	5	{0,1,2,3,5}	[1,3,2,0]	Back to 5
25	Push node 5 to stack	5	{0,1,2,3,5}	[1,3,2,0,5]	Stack: 1 -> 3 -> 2 -> 0 -> 5
26	Start DFS at node 4	4	{0,1,2,3,5}	[1,3,2,0,5]	Node 4 unvisited
27	Visit node 4	4	{0,1,2,3,4,5}	[1,3,2,0,5]	Visited 4
28	Check neighbors of 4: 1	4	{0,1,2,3,4,5}	[1,3,2,0,5]	Neighbor 1 visited
29	Push node 4 to stack	4	{0,1,2,3,4,5}	[1,3,2,0,5,4]	Stack: 1 -> 3 -> 2 -> 0 -> 5 -> 4
30	All nodes visited	-	{0,1,2,3,4,5}	[1,3,2,0,5,4]	DFS complete
31	Pop all nodes from stack	-	-	-	Topological order: 4 -> 5 -> 0 -> 2 -> 3 -> 1

💡 All nodes visited and pushed to stack; popping stack gives topological order

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 8	After Step 11	After Step 13	After Step 15	After Step 17	After Step 23	After Step 25	After Step 29	Final
visited	{}	{5}	{2,5}	{2,3,5}	{1,2,3,5}	{1,2,3,5}	{1,2,3,5}	{1,2,3,5}	{0,1,2,3,5}	{0,1,2,3,5}	{0,1,2,3,4,5}	{0,1,2,3,4,5}
stack	[]	[]	[]	[]	[]	[1]	[1,3]	[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 12-13 and 22-23, nodes are pushed after all neighbors are visited, ensuring dependencies come before the node in the topological order.

What happens if a node has no neighbors?

As shown in rows 12 and 22, if a node has no neighbors, it is pushed immediately to the stack, since there are no dependencies to wait for.

Why do we start DFS from unvisited nodes only?

Because in row 26, DFS starts only at node 4 which was unvisited; visited nodes are skipped to avoid repeated work and infinite loops.

Visual Quiz - 3 Questions

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

A [1]

B [3]

C [1,3]

D []

💡 Hint

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

At which step does the node 0 get pushed to the stack?

A Step 20

B Step 23

C Step 22

D Step 25

💡 Hint

Look for 'Push node 0 to stack' operation in execution_table

If node 4 had a neighbor 5 (already visited), what would happen at step 28?

A Node 5 would be removed from visited set

B Node 4 would be pushed to stack immediately

C DFS would skip neighbor 5 and continue

D DFS would recurse on 5 again

💡 Hint

Refer to step 28 where neighbor 1 is visited and DFS does not recurse again

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 has not been visited yet. For each node, we mark it visited and recursively visit all its neighbors. After all neighbors are visited, we push the current node to a stack. This ensures that nodes are pushed only after their dependencies. Finally, popping all nodes from the stack gives the topological order. The execution table shows step-by-step how nodes are visited, neighbors checked, and nodes pushed to the stack. The variable tracker shows how the visited set and stack change over time. Key moments clarify why nodes are pushed after neighbors and why DFS starts only at unvisited nodes. The visual quiz tests understanding of stack states and DFS behavior.

Practice

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

easy

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

B. To find the shortest path between two nodes

C. To detect cycles in an undirected graph

D. To count the number of connected components

Solution

1. Step 1: Understand DFS role in Topological Sort

   DFS visits nodes deeply, ensuring all nodes reachable from a node are visited before the node itself.

2. Step 2: Relate DFS to dependency order

   This ensures nodes appear after all their dependencies, which is the goal of topological sorting.

3. Final Answer:

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

4. Quick Check:

   DFS orders nodes respecting dependencies [OK]

Hint: DFS ensures dependencies come before nodes in topological order [OK]

Common Mistakes:

• Confusing topological sort with shortest path
• Thinking DFS detects cycles in undirected graphs here
• Mixing connected components with topological order

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] = 1;

C. visited[node] == true;

D. visited[node] = false;

Solution

1. Step 1: Understand C syntax for arrays

   In C, arrays use square brackets to access elements, so visited[node] is correct.

2. Step 2: Assigning visited status

   Assigning 1 marks the node as visited; '==' is comparison, not assignment; 'false' would mark unvisited.

3. Final Answer:

   visited[node] = 1; -> Option B

4. Quick Check:

   Use visited[node] = 1 to mark visited [OK]

Hint: Use visited[node] = 1 to mark visited in C arrays [OK]

Common Mistakes:

• Using parentheses instead of brackets for arrays
• Using '==' instead of '=' for assignment
• Assigning false instead of true/1 to mark visited

3. What is the output order of nodes after performing DFS-based topological sort on this graph?

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

Assume nodes are pushed to stack after visiting all neighbors and stack is printed top to bottom.

medium

A. [0, 2, 1, 3]

B. [3, 2, 1, 0]

C. [0, 1, 2, 3]

D. [3, 1, 2, 0]

Solution

1. Step 1: Perform DFS starting from node 0

   Visit 0, then neighbors 1 then 2 (edge order). From 1 to 3, from 2 to 3 (visited).

2. Step 2: Push nodes to stack after visiting neighbors

   Push 3, then 1, then 3 already visited, then 2, then 0. Stack top to bottom: [3, 1, 2, 0].

3. Final Answer:

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

4. Quick Check:

   Stack top to bottom after DFS = [3, 1, 2, 0] [OK]

Hint: Push nodes after neighbors; output is stack top to bottom [OK]

Common Mistakes:

• Pushing nodes before visiting neighbors
• Confusing order of neighbors visited
• Printing stack bottom to top instead of top to bottom

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

void dfs(int node) {
  visited[node] = 1;
  for (int i = 0; i < adj[node].size(); i++) {
    int nbr = adj[node][i];
    if (!visited[nbr])
      dfs(nbr);
  }
  stack.push(node);
}

medium

A. Stack push should be before recursive calls

B. Missing base case for cycle detection

C. Using adj[node].size() is invalid in C

D. visited array should be initialized to 2 instead of 1

Solution

1. Step 1: Check syntax for adjacency list size in C

   adj[node].size() is C++ syntax; C does not support .size() method on arrays.

2. Step 2: Identify correct way to get adjacency list size in C

   In C, adjacency lists are usually arrays with separate size variables; .size() causes compile error.

3. Final Answer:

   Using adj[node].size() is invalid in C -> Option C

4. Quick Check:

   adj[node].size() is C++ only, not C [OK]

Hint: Use array length variables in C, not .size() method [OK]

Common Mistakes:

• Confusing C and C++ syntax for containers
• Ignoring cycle detection in topological sort
• Pushing nodes before recursive calls

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 order using DFS-based topological sort?

hard

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

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

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

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

Solution

1. Step 1: Analyze prerequisites from edges

   (u -> v means u before v): 5 before 2 and 0; 4 before 0 and 1; 2 before 3; 3 before 1.

2. Step 2: Check each option for prerequisite order

   [4, 5, 2, 3, 1, 0]: 4 before 0 and 1, 5 before 2 and 0, 2 before 3, 3 before 1, all correct.

3. Final Answer:

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

4. Quick Check:

   All edges respected in order D [OK]

Hint: Check each edge u->v: u appears before v in order [OK]

Common Mistakes:

• Ignoring edge directions in order
• Placing dependent nodes before their prerequisites
• Assuming any order with all nodes is valid