Topological Sort Using DFS in DSA Go - 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

↓

Add node to stack after all neighbors visited

↓

Repeat for all nodes

↓

Pop all nodes from stack for topological order

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

Execution Sample

DSA Go

func topoSortDFS(graph map[int][]int) []int {
  visited := map[int]bool{}
  stack := []int{}
  var dfs func(int)
  dfs = func(node int) {
    visited[node] = true
    for _, n := range graph[node] {
      if !visited[n] {
        dfs(n)
      }
    }
    stack = append(stack, node)
  }
  for node := range graph {
    if !visited[node] {
      dfs(node)
    }
  }
  // reverse stack for order
  for i, j := 0, len(stack)-1; i < j; i, j = i+1, j-1 {
    stack[i], stack[j] = stack[j], stack[i]
  }
  return stack
}

This code performs a topological sort on a directed graph using DFS and returns the sorted order.

Execution Table

Step	Operation	Current Node	Visited Set	Stack (after push)	Visual State
1	Start DFS at 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	Go to neighbor 2	2	{5}	[]	Traverse edge 5->2
4	Visit node 2	2	{5,2}	[]	Visited 2
5	Go to neighbor 3	3	{5,2}	[]	Traverse edge 2->3
6	Visit node 3	3	{5,2,3}	[]	Visited 3
7	Go to neighbor 1	1	{5,2,3}	[]	Traverse edge 3->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	3	{5,2,3,1}	[1]	All neighbors visited, push 3
11	Push 3 to stack	3	{5,2,3,1}	[1,3]	Stack updated
12	Back to node 2	2	{5,2,3,1}	[1,3]	All neighbors visited, push 2
13	Push 2 to stack	2	{5,2,3,1}	[1,3,2]	Stack updated
14	Back to node 5	5	{5,2,3,1}	[1,3,2]	Next neighbor 0
15	Go to neighbor 0	0	{5,2,3,1}	[1,3,2]	Traverse edge 5->0
16	Visit node 0	0	{5,2,3,1,0}	[1,3,2]	Visited 0
17	Node 0 has no neighbors	0	{5,2,3,1,0}	[1,3,2,0]	Push 0 to stack
18	Back to node 5	5	{5,2,3,1,0}	[1,3,2,0]	All neighbors visited, push 5
19	Push 5 to stack	5	{5,2,3,1,0}	[1,3,2,0,5]	Stack updated
20	Start DFS at node 4	4	{5,2,3,1,0}	[1,3,2,0,5]	Node 4 unvisited
21	Visit node 4	4	{5,2,3,1,0,4}	[1,3,2,0,5]	Visited 4
22	Go to neighbor 0	0	{5,2,3,1,0,4}	[1,3,2,0,5]	Neighbor 0 already visited, skip
23	Go to neighbor 1	1	{5,2,3,1,0,4}	[1,3,2,0,5]	Neighbor 1 already visited, skip
24	All neighbors visited for 4	4	{5,2,3,1,0,4}	[1,3,2,0,5,4]	Push 4 to stack
25	All nodes visited	-	{5,2,3,1,0,4}	[1,3,2,0,5,4]	DFS complete
26	Reverse stack for order	-	-	-	Final topological order: [4,5,0,2,3,1]

💡 All nodes visited, DFS complete, stack reversed for topological order

Variable Tracker

Variable	Start	After Step 2	After Step 9	After Step 13	After Step 17	After Step 19	After Step 24	Final
visited	{}	{5}	{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]	[4,5,0,2,3,1] (reversed)
current_node	-	5	1	2	0	5	4	-

Key Moments - 3 Insights

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

Because in topological sort, a node must come after all nodes it points to. Adding after visiting neighbors ensures dependencies are pushed first (see steps 9, 11, 13).

Why do we reverse the stack at the end?

Nodes are pushed after their dependencies, so the stack has reverse order. Reversing it gives the correct topological order (see step 26).

What happens if a neighbor is already visited?

We skip it to avoid cycles and repeated work, as shown in steps 22 and 23 where neighbors 0 and 1 are already visited.

Visual Quiz - 3 Questions

Look at the execution table, what is the stack after step 13?

A [1,3,2]

B [1,3]

C [1]

D [1,3,2,0]

💡 Hint

Check the 'Stack (after push)' column at step 13 in the execution table.

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

A Step 19

B Step 17

C Step 9

D Step 24

💡 Hint

Look for when node 0 has no neighbors and is pushed (see step 17).

If we did not reverse the stack at the end, what would be the first node in the output?

A 4

B 5

C 1

D 0

💡 Hint

Look at the stack before reversal at step 25; the last pushed node is at the end.

Concept Snapshot

Topological Sort Using DFS:
- Visit each unvisited node with DFS
- Recursively visit neighbors first
- After neighbors, push node to stack
- Reverse stack for topological order
- Works only on Directed Acyclic Graphs (DAGs)

Full Transcript

Topological sort using DFS visits each node and its neighbors recursively. When all neighbors of a node are visited, the node is pushed onto a stack. This ensures nodes appear after their dependencies. After DFS completes for all nodes, the stack is reversed to get the correct topological order. The execution table shows step-by-step visits, stack updates, and visited nodes. Key moments clarify why nodes are pushed after neighbors and why the stack is reversed. The visual quiz tests understanding of stack states and order of operations.

Practice

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

easy

A. To visit nodes in a way that ensures dependencies come before dependents

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 dependencies of a node are visited before the node itself.

2. Step 2: Relate DFS order to dependencies

   By pushing nodes to a stack after visiting all neighbors, we get an order where dependencies come before dependents.

3. Final Answer:

   To visit nodes in a way that ensures dependencies come before dependents -> Option A

4. Quick Check:

   DFS ensures dependency order = A [OK]

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

Common Mistakes:

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

2. Which of the following Go code snippets correctly declares a recursive DFS function for topological sort?

easy

A. func dfs(node int, graph map[int][]int, visited map[int]bool, stack *[]int) { if visited[node] { return } visited[node] = true *stack = append(*stack, node) for _, neighbor := range graph[node] { dfs(neighbor, graph, visited, stack) } }

B. func dfs(node int, graph map[int][]int, visited map[int]bool, stack []int) { if visited[node] { return } visited[node] = true for _, neighbor := range graph[node] { dfs(neighbor, graph, visited, stack) } stack = append(stack, node) }

C. func dfs(node int, graph map[int][]int, visited map[int]bool, stack *[]int) { if visited[node] { return } for _, neighbor := range graph[node] { dfs(neighbor, graph, visited, stack) } visited[node] = true *stack = append(*stack, node) }

D. func dfs(node int, graph map[int][]int, visited map[int]bool, stack *[]int) { if !visited[node] { visited[node] = true for _, neighbor := range graph[node] { dfs(neighbor, graph, visited, stack) } *stack = append(*stack, node) } }

Solution

1. Step 1: Check visited condition and marking

   func dfs(node int, graph map[int][]int, visited map[int]bool, stack *[]int) { if !visited[node] { visited[node] = true for _, neighbor := range graph[node] { dfs(neighbor, graph, visited, stack) } *stack = append(*stack, node) } } correctly checks if node is not visited before processing and marks it visited inside the condition.

2. Step 2: Confirm stack append and recursion

   It recursively calls dfs on neighbors and appends node to stack after visiting neighbors, using pointer to modify stack.

3. Final Answer:

   Option D code snippet -> Option D

4. Quick Check:

   Correct DFS recursion and stack append = D [OK]

Hint: Use pointer for stack to append in recursive DFS [OK]

Common Mistakes:

• Passing stack by value causing no changes
• Marking visited after recursion causing repeated visits
• Appending node before visiting neighbors

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

graph := map[int][]int{
  5: {2, 0},
  4: {0, 1},
  2: {3},
  3: {1},
  0: {},
  1: {},
}

Assuming DFS visits nodes in ascending order starting from 5, then 4.

medium

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

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

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

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

Solution

1. Step 1: Perform DFS starting from node 5

   DFS from 5 (neighbors ascending: 0 then 2): DFS(0) append 0; then DFS(2) -> DFS(3) -> DFS(1) append 1; append 3; append 2; append 5. Then DFS from 4 (0,1 visited), append 4.

2. Step 2: Collect nodes in post-order (append after visiting neighbors)

   Post-order stack push order: 0, 1, 3, 2, 5, 4. Reversing gives [4, 5, 2, 3, 1, 0].

3. Step 3: Consider DFS starting order and visited nodes

   Since DFS visits 5 first, then 4, the final topological order is the reverse of the post-order stack: [4, 5, 2, 3, 1, 0]. However, the question states DFS visits nodes in ascending order starting from 5, then 4. The actual post-order stack is [0,1,3,2,5,4], so reversed order is [4,5,2,3,1,0].

4. Final Answer:

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

5. Quick Check:

   Post-order reverse = [4,5,2,3,1,0] [OK]

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

Common Mistakes:

• Not reversing the stack after DFS
• Visiting nodes in wrong order
• Ignoring already visited nodes

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

func dfs(node int, graph map[int][]int, visited map[int]bool, stack *[]int) {
  if visited[node] {
    return
  }
  for _, neighbor := range graph[node] {
    dfs(neighbor, graph, visited, stack)
  }
  visited[node] = true
  *stack = append(*stack, node)
}

medium

A. Visited is marked after recursion, causing repeated visits

B. Stack is appended before visiting neighbors

C. Visited map is not initialized

D. Function does not return any value

Solution

1. Step 1: Check visited marking timing

   Visited is marked after recursive calls, so neighbors may revisit the same node multiple times.

2. Step 2: Correct visited marking position

   Visited should be marked before recursion to avoid repeated visits and infinite loops.

3. Final Answer:

   Visited is marked after recursion, causing repeated visits -> Option A

4. Quick Check:

   Mark visited before recursion = B [OK]

Hint: Mark visited before recursion to avoid repeats [OK]

Common Mistakes:

• Marking visited too late causing infinite recursion
• Appending stack before recursion
• Ignoring initialization of visited map

5. Given a directed graph with edges:

1 -> 2, 1 -> 3, 3 -> 4, 2 -> 4, 4 -> 5

If you want to find a valid order to complete tasks represented by nodes, which topological sort order is correct?

hard

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

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

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

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

Solution

1. Step 1: Analyze dependencies from edges

   Node 1 must come before 2 and 3; 2 and 3 before 4; 4 before 5.

2. Step 2: Find order respecting dependencies

   Order [1, 2, 3, 4, 5] respects all edges: 1 before 2 and 3, 2 and 3 before 4, 4 before 5.

3. Final Answer:

   [1, 2, 3, 4, 5] -> Option C

4. Quick Check:

   Dependencies respected = C [OK]

Hint: Start with nodes having no incoming edges [OK]

Common Mistakes:

• Reversing order ignoring dependencies
• Placing dependent before dependency
• Choosing order with cycles