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

Concept Flow - DFS Depth First Search on Graph

Start at source 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

DFS starts at a node, marks it visited, then explores each unvisited neighbor deeply before backtracking.

Execution Sample

DSA Java

void dfs(int node, boolean[] visited, List<Integer>[] graph) {
  visited[node] = true;
  for (int neighbor : graph[node]) {
    if (!visited[neighbor]) dfs(neighbor, visited, graph);
  }
}

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

Execution Table

Step	Operation	Current Node	Visited Set	Call Stack	Action Taken
1	Start DFS	0	[0]	[0]	Mark 0 visited, explore neighbors 1,2
2	Visit neighbor	1	[0,1]	[0,1]	Mark 1 visited, explore neighbors 0,3
3	Check neighbor	3	[0,1,3]	[0,1,3]	Mark 3 visited, explore neighbors 1,4
4	Check neighbor	4	[0,1,3,4]	[0,1,3,4]	Mark 4 visited, explore neighbors 3
5	Neighbor visited	3	[0,1,3,4]	[0,1,3,4]	3 already visited, backtrack
6	Backtrack	4	[0,1,3,4]	[0,1,3]	All neighbors done, backtrack
7	Backtrack	3	[0,1,3,4]	[0,1]	All neighbors done, backtrack
8	Check neighbor	2	[0,1,2,3,4]	[0,2]	Mark 2 visited, explore neighbors 0
9	Neighbor visited	0	[0,1,2,3,4]	[0,2]	0 already visited, backtrack
10	Backtrack	2	[0,1,2,3,4]	[0]	All neighbors done, backtrack
11	Backtrack	0	[0,1,2,3,4]	[]	All neighbors done, DFS complete

💡 All nodes reachable from 0 visited, recursion ends

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	After Step 10	Final
visited	[false,false,false,false,false]	[true,false,false,false,false]	[true,true,false,false,false]	[true,true,false,true,false]	[true,true,false,true,true]	[true,true,false,true,true]	[true,true,false,true,true]	[true,true,false,true,true]	[true,true,true,true,true]	[true,true,true,true,true]	[true,true,true,true,true]	[true,true,true,true,true]
call_stack	[]	[0]	[0,1]	[0,1,3]	[0,1,3,4]	[0,1,3,4]	[0,1,3]	[0,1]	[0,2]	[0,2]	[0]	[]
current_node	N/A	0	1	3	4	3	4	3	2	0	2	0

Key Moments - 3 Insights

Why do we mark a node as visited before exploring its neighbors?

Marking a node visited before exploring neighbors prevents revisiting it and infinite loops, as shown in steps 1 and 2 where node 0 and 1 are marked before recursion.

Why do we backtrack after all neighbors are visited?

Backtracking happens when no unvisited neighbors remain, allowing DFS to return to previous nodes to explore other paths, as seen in steps 6 and 7.

Why does DFS use a call stack to track nodes?

The call stack keeps track of nodes to return to after exploring neighbors, shown in the call_stack column where nodes are pushed and popped during recursion.

Visual Quiz - 3 Questions

Look at the execution table, what is the visited set after step 4?

A [0,1,3]

B [0,1,2,3]

C [0,1,3,4]

D [0,1]

💡 Hint

Check the Visited Set column at step 4 in the execution_table

At which step does DFS backtrack from node 3 for the first time?

A Step 5

B Step 6

C Step 7

D Step 8

💡 Hint

Look at the Action Taken and Current Node columns around steps 5-7

If node 2 had an unvisited neighbor, how would the call stack change at step 9?

A It would clear the stack

B It would add the neighbor to the stack

C It would remove node 2 from the stack

D It would remain unchanged

💡 Hint

Refer to how call_stack changes when visiting neighbors in the execution_table

Concept Snapshot

DFS explores graph nodes by going deep before backtracking.
Start at a node, mark visited, recursively visit unvisited neighbors.
Uses call stack to remember path.
Prevents cycles by marking visited early.
Backtracks when no neighbors left.
Useful for connectivity and path finding.

Full Transcript

Depth First Search (DFS) on a graph starts at a chosen node, marks it visited, then explores each neighbor deeply before backtracking. The code marks nodes visited before recursion to avoid cycles. The call stack tracks the path of nodes being explored. When all neighbors of a node are visited, DFS backtracks to explore other paths. This process continues until all reachable nodes are visited. The execution table shows step-by-step how nodes are visited, the call stack changes, and when backtracking occurs. Key moments include why marking visited early is important, how backtracking works, and the role of the call stack. The visual quiz tests understanding of visited sets, backtracking steps, and call stack behavior. DFS is a fundamental graph traversal technique useful for many problems.

Practice

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

easy

A. Randomly visit nodes until all are visited

B. Visit all neighbors of a node before moving deeper

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

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

Solution

1. Step 1: Understand DFS traversal

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

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 D

4. Quick Check:

   DFS = deep exploration first [OK]

Hint: DFS goes deep first, BFS goes wide first [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 traversal from node 0 in Java using recursion?

easy

A. dfs(0, visited, graph);

B. DFS(visited, graph, 0);

C. dfs(graph, 0, visited);

D. dfs(visited, 0, graph);

Solution

1. Step 1: Identify typical DFS method signature

   Common DFS signature is dfs(currentNode, visitedArray, graph).

2. Step 2: Match options to this signature

   dfs(0, visited, graph); matches the order: node, visited, graph. Others have wrong parameter order.

3. Final Answer:

   dfs(0, visited, graph); -> Option A

4. Quick Check:

   Correct parameter order = dfs(node, visited, graph) [OK]

Hint: DFS method usually starts with node, visited, graph [OK]

Common Mistakes:

• Mixing parameter order
• Using uppercase method name 'DFS'
• Passing graph before node

3. Given the graph adjacency list: graph = {{1, 2}, {0, 3}, {0}, {1}} and starting DFS from node 0, what is the order of nodes visited?

medium

A. [0, 1, 3, 2]

B. [0, 2, 1, 3]

C. [0, 1, 2, 3]

D. [0, 3, 1, 2]

Solution

1. Step 1: Start DFS at node 0 and visit neighbors

   From 0, neighbors are 1 and 2. DFS visits 1 first (assuming adjacency order).

2. Step 2: From node 1, visit its neighbors

   Neighbors of 1 are 0 (visited) and 3. Visit 3 next.

3. Step 3: Backtrack and visit remaining neighbors

   After 3, backtrack to 0 and visit 2.

4. Final Answer:

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

5. Quick Check:

   DFS order = 0,1,3,2 [OK]

Hint: Follow neighbors deeply in adjacency order [OK]

Common Mistakes:

• Visiting neighbors in wrong order
• Not backtracking correctly
• Confusing BFS order with DFS

4. What is wrong with this DFS code snippet in Java?

void dfs(int node, boolean[] visited, List<Integer>[] graph) {
  visited[node] = true;
  for (int neighbor : graph[node]) {
    if (visited[neighbor]) {
      dfs(neighbor, visited, graph);
    }
  }
}

medium

A. It does not mark nodes as visited

B. It calls dfs on already visited neighbors causing infinite recursion

C. It uses wrong data types for graph

D. It misses the base case for recursion

Solution

1. Step 1: Check visited condition before recursive call

   The code calls dfs(neighbor) only if visited[neighbor] is true, which means already visited.

2. Step 2: Identify the problem caused

   This causes infinite recursion because it revisits nodes already visited instead of skipping them.

3. Final Answer:

   It calls dfs on already visited neighbors causing infinite recursion -> Option B

4. Quick Check:

   Call dfs only if neighbor not visited [OK]

Hint: Call dfs only if neighbor is NOT visited [OK]

Common Mistakes:

• Calling dfs on visited nodes
• Forgetting to mark visited nodes
• Incorrect loop over neighbors

5. You want to find if there is a path between node 0 and node 4 in this graph:

graph = {{1, 2}, {0, 3}, {0, 4}, {1}, {2}}

Which DFS approach correctly determines if node 4 is reachable from node 0?

hard

A. Run DFS from 4, stop and return true if node 0 is found during traversal

B. Run DFS from 0 and count all visited nodes without checking for 4

C. Run DFS from 0, stop and return true if node 4 is found during traversal

D. Run DFS from 0 but skip node 2 to avoid cycles

Solution

1. Step 1: Understand the goal

   We want to check if node 4 is reachable from node 0, so start DFS at 0.

2. Step 2: Use DFS to find target node

   During DFS, if node 4 is found, stop and return true immediately.

3. Step 3: Evaluate options

   Run DFS from 0, stop and return true if node 4 is found during traversal matches this approach. Run DFS from 4, stop and return true if node 0 is found during traversal starts from wrong node. Run DFS from 0 and count all visited nodes without checking for 4 ignores target. Run DFS from 0 but skip node 2 to avoid cycles skips nodes incorrectly.

4. Final Answer:

   Run DFS from 0, stop and return true if node 4 is found during traversal -> Option C

5. Quick Check:

   DFS from start, stop on target found [OK]

Hint: Stop DFS early when target node is found [OK]

Common Mistakes:

• Starting DFS from wrong node
• Not checking for target during traversal
• Skipping nodes that are part of path