Topological Sort Using DFS in DSA C# - Execution Trace

Concept Flow - Topological Sort Using DFS

Start with all nodes

↓

Pick unvisited node

↓

DFS: Mark node visited

↓

For each neighbor

↓

If neighbor unvisited

↓

Recursive DFS on neighbor

↓

After all neighbors visited

↓

Add node to stack

↓

Repeat until all nodes visited

↓

Pop all nodes from stack for topological order

Start DFS from unvisited nodes, visit neighbors recursively, then add nodes to stack. Finally, pop stack for topological order.

Execution Sample

DSA C#

void DFS(int node) {
  visited[node] = true;
  foreach (var n in graph[node]) {
    if (!visited[n]) DFS(n);
  }
  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 from node 5	5	{}	[]	Graph nodes: 5->2, 5->0, 4->0, 4->1, 2->3, 3->1
2	Visit node 5	5	{5}	[]	Visited 5
3	Visit neighbor 2 of 5	2	{5}	[]	Moving to 2
4	Visit node 2	2	{5,2}	[]	Visited 2
5	Visit neighbor 3 of 2	3	{5,2}	[]	Moving to 3
6	Visit node 3	3	{5,2,3}	[]	Visited 3
7	Visit neighbor 1 of 3	1	{5,2,3}	[]	Moving to 1
8	Visit node 1	1	{5,2,3,1}	[]	Visited 1
9	Node 1 has no neighbors	1	{5,2,3,1}	[1]	Push 1 to stack
10	Back to node 3, all neighbors visited	3	{5,2,3,1}	[1,3]	Push 3 to stack
11	Back to node 2, all neighbors visited	2	{5,2,3,1}	[1,3,2]	Push 2 to stack
12	Back to node 5, visit neighbor 0	0	{5,2,3,1}	[1,3,2]	Moving to 0
13	Visit node 0	0	{5,2,3,1,0}	[1,3,2]	Visited 0
14	Node 0 has no neighbors	0	{5,2,3,1,0}	[1,3,2,0]	Push 0 to stack
15	Back to node 5, all neighbors visited	5	{5,2,3,1,0}	[1,3,2,0,5]	Push 5 to stack
16	Start DFS from node 4	4	{5,2,3,1,0}	[1,3,2,0,5]	Moving to 4
17	Visit node 4	4	{5,2,3,1,0,4}	[1,3,2,0,5]	Visited 4
18	Visit neighbor 0 of 4 (already visited)	0	{5,2,3,1,0,4}	[1,3,2,0,5]	Skip 0
19	Visit neighbor 1 of 4 (already visited)	1	{5,2,3,1,0,4}	[1,3,2,0,5]	Skip 1
20	All neighbors of 4 visited	4	{5,2,3,1,0,4}	[1,3,2,0,5,4]	Push 4 to stack
21	All nodes visited	-	{5,2,3,1,0,4}	[1,3,2,0,5,4]	DFS complete
22	Pop stack for topological order	-	-	-	Order: 4 -> 5 -> 0 -> 2 -> 3 -> 1

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

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 9	After Step 14	After Step 15	After Step 20	Final
visited	{}	{5}	{5,2}	{5,2,3}	{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,0]	[1,3,2,0,5]	[1,3,2,0,5,4]	[1,3,2,0,5,4]
current_node	-	5	2	3	1	0	5	4	-

Key Moments - 3 Insights

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

Because in the execution_table at step 9 and 10, nodes are pushed after all neighbors are visited, ensuring dependencies come before the node in the final order.

Why do we skip neighbors that are already visited?

As shown in steps 18 and 19, skipping visited neighbors prevents infinite loops and repeated work, ensuring each node is processed once.

How does popping the stack at the end give the correct topological order?

The stack stores nodes after visiting dependencies; popping reverses this order, so nodes appear after their dependencies, as seen in step 22.

Visual Quiz - 3 Questions

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

A [1]

B []

C [1,3]

D [1,3,2]

💡 Hint

Check the 'Stack State' column at step 9 in execution_table.

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

A Step 15

B Step 18

C Step 20

D Step 22

💡 Hint

Look for 'Push 4 to stack' in the 'Operation' column of execution_table.

If node 0 was not visited before node 4, how would the stack state change at step 20?

A Stack would be empty

B Stack would include node 0 before node 4

C Stack would not include node 4

D Stack would include node 4 before node 0

💡 Hint

Refer to variable_tracker and execution_table steps 14 and 20 for node visit order.

Concept Snapshot

Topological Sort Using DFS:
- Visit unvisited nodes recursively
- After visiting all neighbors, push node to stack
- Repeat until all nodes visited
- Pop stack for topological order
- Ensures dependencies come before dependent nodes

Full Transcript

Topological Sort using DFS starts by picking unvisited nodes and visiting them recursively. Each node is marked visited when first encountered. For each neighbor, if unvisited, DFS is called recursively. After all neighbors are visited, the node is pushed onto a stack. This process repeats until all nodes are visited. Finally, popping nodes from the stack gives the topological order, ensuring nodes appear after their dependencies. The execution table shows each step with current node, visited set, stack state, and visual graph state. Key moments clarify why nodes are pushed after neighbors and why visited nodes are skipped. The visual quiz tests understanding of stack states and node visit order. This method is efficient for ordering tasks with dependencies.

Practice

1. What is the main purpose of using DFS in Topological Sort on a directed graph?

easy

A. To find the shortest path between two nodes

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

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 order to dependencies

   In Topological Sort, nodes must appear after all their dependencies, which DFS achieves by post-order traversal.

3. Final Answer:

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

4. Quick Check:

   DFS ensures dependency order [OK]

Hint: DFS post-order gives correct dependency order [OK]

Common Mistakes:

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

2. Which of the following C# code snippets correctly starts a DFS-based topological sort on all nodes in a graph represented as adjacency list Dictionary?

easy

A. for(int i=0; i

B. while(graph.Count > 0) DFS(graph.First().Key);

C. foreach(var node in graph.Keys) if(!visited[node]) DFS(node);

D. foreach(var node in graph.Values) DFS(node[0]);

Solution

1. Step 1: Identify correct iteration over nodes

   We must iterate over all keys (nodes) and call DFS only if not visited.

2. Step 2: Check each option's correctness

   foreach(var node in graph.Keys) if(!visited[node]) DFS(node); correctly iterates keys and checks visited. for(int i=0; i 0) DFS(graph.First().Key); modifies graph during iteration, unsafe. foreach(var node in graph.Values) DFS(node[0]); iterates values, not nodes.

3. Final Answer:

   foreach(var node in graph.Keys) if(!visited[node]) DFS(node); -> Option C

4. Quick Check:

   Iterate keys and check visited [OK]

Hint: Iterate graph keys, check visited before DFS [OK]

Common Mistakes:

• Iterating over graph.Values instead of Keys
• Assuming node indices are continuous from 0
• Modifying collection during iteration

3. What is the output of the following C# code performing topological sort using DFS on the graph edges: 5->2, 5->0, 4->0, 4->1, 2->3, 3->1?

var graph = new Dictionary {
  {5, new List<int>{2,0}},
  {4, new List<int>{0,1}},
  {2, new List<int>{3}},
  {3, new List<int>{1}},
  {0, new List<int>()},
  {1, new List<int>()}
};
var visited = new HashSet<int>();
var stack = new Stack<int>();
void DFS(int node) {
  visited.Add(node);
  foreach(var n in graph[node]) {
    if(!visited.Contains(n)) DFS(n);
  }
  stack.Push(node);
}
foreach(var node in graph.Keys) {
  if(!visited.Contains(node)) DFS(node);
}
var result = stack.ToArray();
Console.WriteLine(string.Join(", ", result));

medium

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

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

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

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

Solution

1. Step 1: Perform DFS and track stack push order

   Start DFS from 5: visit 2, then 3, then 1; push 1, 3, 2, then 0 from 5's other edge; push 5. Then DFS from 4: visit 0 and 1 already visited, push 4.

2. Step 2: Stack order and output

   Stack push order is 1, 3, 2, 0, 5, 4. Converting stack to array reverses order: 4, 5, 0, 2, 3, 1.

3. Final Answer:

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

4. Quick Check:

   DFS post-order reversed = topological order [OK]

Hint: Stack reversed after DFS gives topological order [OK]

Common Mistakes:

• Not reversing stack before output
• Visiting nodes in wrong order
• Ignoring nodes with no outgoing edges

4. The following C# DFS-based topological sort code throws a runtime error. What is the likely cause?

void DFS(int node) {
  visited.Add(node);
  foreach(var n in graph[node]) {
    if(!visited.Contains(n)) DFS(n);
  }
  stack.Push(node);
}
foreach(var node in graph.Keys) {
  DFS(node);
}

medium

A. No error; code runs correctly

B. NullReferenceException because graph is empty

C. Stack overflow due to infinite recursion from cycles

D. KeyNotFoundException because some nodes are missing in graph keys

Solution

1. Step 1: Analyze potential runtime errors in DFS

   When recursing to a neighbor n not present as a key in the graph (common for sink nodes), accessing graph[n] throws KeyNotFoundException.

2. Step 2: Outer loop issue

   Missing !visited check before DFS(node) causes duplicate stack pushes (logical error), not runtime error. Cycle detection needs separate recursion stack.

3. Final Answer:

   KeyNotFoundException because some nodes are missing in graph keys -> Option D

4. Quick Check:

   graph[n] for missing sink node key -> KeyNotFoundException [OK]

Hint: Include all nodes as keys with empty lists [OK]

Common Mistakes:

• Omitting sink/leaf nodes from graph keys
• Not initializing empty List<int>() for nodes with no outgoing edges
• Assuming all edge targets are automatically graph keys

5. Given a directed acyclic graph (DAG) with nodes representing tasks and edges representing dependencies, how can you modify the DFS-based topological sort to detect if the graph contains a cycle?

hard

A. Use an additional recursion stack set to track nodes in the current DFS path and detect back edges

B. Count the number of nodes visited and compare with total nodes after DFS

C. Run BFS instead of DFS to detect cycles

D. Sort nodes by their degree before DFS

Solution

1. Step 1: Understand cycle detection in DFS

   Use a recursion stack set to mark nodes currently in the DFS path. If a node is revisited while in this set, a cycle exists.

2. Step 2: Explain why other options fail

   Counting visited nodes doesn't detect cycles. BFS alone doesn't detect cycles in directed graphs. Sorting by degree doesn't help detect cycles.

3. Final Answer:

   Use an additional recursion stack set to track nodes in the current DFS path and detect back edges -> Option A

4. Quick Check:

   Recursion stack detects cycles in DFS [OK]

Hint: Track recursion stack to find back edges indicating cycles [OK]

Common Mistakes:

• Ignoring recursion stack for cycle detection
• Assuming BFS detects cycles in directed graphs
• Using node count to detect cycles