DFS Depth First Search on Graph in DSA Go - Execution Trace

Concept Flow - DFS Depth First Search on Graph

Start at chosen node

↓

Mark node as visited

↓

For each neighbor

↓

If neighbor not visited?

No→Skip

Yes↓

Recursively DFS on neighbor

↓

All neighbors visited?

↓

Backtrack to previous node

↓

Done when all reachable nodes visited

Start from a node, visit it, then recursively visit each unvisited neighbor, backtracking when no new neighbors remain.

Execution Sample

DSA Go

func DFS(node string, graph map[string][]string, visited map[string]bool) {
    visited[node] = true
    for _, neighbor := range graph[node] {
        if !visited[neighbor] {
            DFS(neighbor, graph, visited)
        }
    }
}

This code visits nodes in depth-first order, marking each visited and recursively exploring neighbors.

Execution Table

Step	Operation	Current Node	Visited Set	Stack (Call Trace)	Action	Graph State
1	Start DFS	A	{}	[A]	Mark A visited	Graph unchanged
2	Explore neighbors of A	A	{A}	[A]	Check B	Graph unchanged
3	DFS call on B	B	{A}	[A, B]	Mark B visited	Graph unchanged
4	Explore neighbors of B	B	{A, B}	[A, B]	Check C	Graph unchanged
5	DFS call on C	C	{A, B}	[A, B, C]	Mark C visited	Graph unchanged
6	Explore neighbors of C	C	{A, B, C}	[A, B, C]	Check D	Graph unchanged
7	DFS call on D	D	{A, B, C}	[A, B, C, D]	Mark D visited	Graph unchanged
8	Explore neighbors of D	D	{A, B, C, D}	[A, B, C, D]	Check B	Graph unchanged
9	Neighbor B already visited	D	{A, B, C, D}	[A, B, C, D]	Skip B	Graph unchanged
10	All neighbors of D visited	D	{A, B, C, D}	[A, B, C, D]	Backtrack	Graph unchanged
11	Back to C	C	{A, B, C, D}	[A, B, C]	Check E	Graph unchanged
12	DFS call on E	E	{A, B, C, D}	[A, B, C, E]	Mark E visited	Graph unchanged
13	Explore neighbors of E	E	{A, B, C, D, E}	[A, B, C, E]	Check F	Graph unchanged
14	DFS call on F	F	{A, B, C, D, E}	[A, B, C, E, F]	Mark F visited	Graph unchanged
15	Explore neighbors of F	F	{A, B, C, D, E, F}	[A, B, C, E, F]	Check C	Graph unchanged
16	Neighbor C already visited	F	{A, B, C, D, E, F}	[A, B, C, E, F]	Skip C	Graph unchanged
17	All neighbors of F visited	F	{A, B, C, D, E, F}	[A, B, C, E, F]	Backtrack	Graph unchanged
18	Back to E	E	{A, B, C, D, E, F}	[A, B, C, E]	All neighbors visited	Graph unchanged
19	Back to C	C	{A, B, C, D, E, F}	[A, B, C]	All neighbors visited	Graph unchanged
20	Back to B	B	{A, B, C, D, E, F}	[A, B]	All neighbors visited	Graph unchanged
21	Back to A	A	{A, B, C, D, E, F}	[A]	Check C	Graph unchanged
22	Neighbor C already visited	A	{A, B, C, D, E, F}	[A]	Skip C	Graph unchanged
23	All neighbors of A visited	A	{A, B, C, D, E, F}	[]	DFS complete	Graph unchanged

💡 All reachable nodes visited, recursion unwound fully

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 5	After Step 7	After Step 12	After Step 14	After Step 23
Current Node	None	A	B	C	D	E	F	None
Visited Set	{}	{A}	{A, B}	{A, B, C}	{A, B, C, D}	{A, B, C, D, E}	{A, B, C, D, E, F}	{A, B, C, D, E, F}
Stack (Call Trace)	[]	[A]	[A, B]	[A, B, C]	[A, B, C, D]	[A, B, C, E]	[A, B, C, E, F]	[]

Key Moments - 3 Insights

Why do we skip neighbors that are already visited instead of visiting them again?

Because revisiting nodes would cause infinite loops. The execution_table rows 8 and 15 show skipping neighbors already in the visited set to prevent repeated visits.

Why does the stack (call trace) grow and shrink during DFS?

The stack grows when we go deeper into neighbors (recursive calls) and shrinks when we backtrack after visiting all neighbors. See rows 3 to 10 for stack growth and rows 10 to 23 for shrinking.

What does backtracking mean in DFS?

Backtracking means returning to the previous node after all neighbors are visited. This is shown in rows 10, 17, 18, and onwards where the stack shrinks and the current node moves back.

Visual Quiz - 3 Questions

Look at the execution_table at Step 7, which nodes are visited?

A {A, B, C}

B {A, B}

C {A, B, C, D}

D {A}

💡 Hint

Check the 'Visited Set' column at Step 7 in the execution_table.

At which step does the DFS first backtrack from node D?

A Step 10

B Step 9

C Step 11

D Step 8

💡 Hint

Look for 'Backtrack' action in the execution_table after visiting D.

If node E had no neighbors, how would the stack change at Step 12?

A Stack would remain [A, B, C, E]

B Stack would immediately shrink after Step 12

C Stack would grow larger than [A, B, C, E]

D Stack would be empty

💡 Hint

Consider that no neighbors means no further recursive calls, so backtracking happens immediately.

Concept Snapshot

DFS (Depth First Search) explores graph nodes by going deep along neighbors before backtracking.
Start at a node, mark visited, recursively visit unvisited neighbors.
Uses recursion stack to track path.
Prevents cycles by skipping visited nodes.
Backtracking occurs when no unvisited neighbors remain.
Useful for exploring all reachable nodes deeply.

Full Transcript

DFS Depth First Search starts at a chosen node, marks it visited, then explores each neighbor recursively if not visited. The recursion stack grows as we go deeper and shrinks when backtracking. Visited nodes are tracked to avoid cycles. The process ends when all reachable nodes are visited and recursion unwinds fully. This trace shows step-by-step how nodes are visited, neighbors checked, and backtracking happens, with the stack and visited set changing accordingly.

Practice

1. What is the main idea behind Depth First Search (DFS) on a graph?

easy

A. Visit nodes in order of their distance from the start node

B. Visit all neighbors of a node before moving deeper

C. Explore as far as possible along each branch before backtracking

D. Randomly visit nodes without any order

Solution

1. Step 1: Understand DFS traversal

   DFS explores a graph by going deep into one branch before backtracking to explore others.

2. Step 2: Compare options with DFS behavior

   Explore as far as possible along each branch before backtracking matches this behavior exactly, while others describe BFS or incorrect methods.

3. Final Answer:

   Explore as far as possible along each branch before backtracking -> Option C

4. Quick Check:

   DFS = deep exploration first [OK]

Hint: DFS means go deep first, then backtrack [OK]

Common Mistakes:

• Confusing DFS with BFS
• Thinking DFS visits neighbors first
• Assuming DFS visits nodes by distance

2. Which of the following is the correct way to start a DFS function in Go for a graph represented as adjacency list graph map[int][]int?

easy

A. func dfs(node int, visited map[int]bool) {}

B. func dfs(node int, visited []int) {}

C. func dfs(node int, visited map[int]int) {}

D. func dfs(node int, visited []bool) {}

Solution

1. Step 1: Identify correct visited type for DFS

   Visited should be a map[int]bool to mark nodes visited or not.

2. Step 2: Check options for visited parameter type

   Only func dfs(node int, visited map[int]bool) {} uses map[int]bool, others use incorrect types.

3. Final Answer:

   func dfs(node int, visited map[int]bool) {} -> Option A

4. Quick Check:

   Visited map with bool = correct DFS parameter [OK]

Hint: Use map[int]bool to track visited nodes in Go DFS [OK]

Common Mistakes:

• Using slice instead of map for visited
• Using wrong map value type
• Ignoring visited parameter

3. What is the output of the following Go code snippet using DFS on the graph?

graph := map[int][]int{
  1: {2, 3},
  2: {4},
  3: {},
  4: {},
}
visited := map[int]bool{}
var result []int
var dfs func(int)
dfs = func(node int) {
  if visited[node] {
    return
  }
  visited[node] = true
  result = append(result, node)
  for _, n := range graph[node] {
    dfs(n)
  }
}
dfs(1)
fmt.Println(result)

medium

A. [1 2 4 3]

B. [1 3 2 4]

C. [1 2 3 4]

D. [1 4 2 3]

Solution

1. Step 1: Trace DFS starting at node 1

   Visit 1, then go to 2, then 4 (no children), backtrack, then visit 3.

2. Step 2: Record order of visited nodes

   Order is 1, 2, 4, 3 as DFS explores deep before backtracking.

3. Final Answer:

   [1 2 4 3] -> Option A

4. Quick Check:

   DFS order = [1 2 4 3] [OK]

Hint: Follow each branch fully before moving to next neighbor [OK]

Common Mistakes:

• Visiting neighbors in wrong order
• Confusing BFS order with DFS
• Not marking visited nodes

4. The following DFS code in Go has a bug. What is the error?

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

// Called as dfs(1, graph, visited)

medium

A. Missing base case to stop recursion

B. Visited map is not updated correctly

C. Incorrect parameter types in function

D. No code to process or print the node

Solution

1. Step 1: Analyze DFS function behavior

   Function marks visited and recurses but does not process or print nodes.

2. Step 2: Identify missing action

   DFS usually processes nodes (e.g., print or collect), missing here causes no visible output.

3. Final Answer:

   No code to process or print the node -> Option D

4. Quick Check:

   DFS missing node processing step [OK]

Hint: DFS must process nodes inside function [OK]

Common Mistakes:

• Assuming marking visited is enough
• Forgetting to print or collect nodes
• Thinking recursion stops without base case

5. Given a graph with possible cycles, how can you modify DFS in Go to detect if a cycle exists?

hard

A. Only mark nodes visited after all neighbors are processed

B. Use a recursion stack map to track nodes currently in the call stack

C. Use BFS instead of DFS to detect cycles

D. Ignore visited nodes and traverse all edges

Solution

1. Step 1: Understand cycle detection in DFS

   Detect cycles by tracking nodes currently in recursion stack to find back edges.

2. Step 2: Choose correct method

   Using a recursion stack map helps detect if a node is revisited while still in the current path.

3. Final Answer:

   Use a recursion stack map to track nodes currently in the call stack -> Option B

4. Quick Check:

   Cycle detection = recursion stack tracking [OK]

Hint: Track recursion stack to find cycles in DFS [OK]

Common Mistakes:

• Marking visited too late
• Using BFS which doesn't detect cycles easily
• Ignoring visited nodes causing infinite loops