DFS Depth First Search on Graph in DSA C - 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

↓

Done when all reachable nodes visited

Start from a node, mark it visited, then explore each unvisited neighbor deeply before backtracking.

Execution Sample

DSA C

void dfs(int node) {
  visited[node] = 1;
  for (int i = 0; i < graph[node].size(); i++) {
    int neighbor = graph[node][i];
    if (!visited[neighbor]) dfs(neighbor);
  }
}

This code visits nodes deeply in a graph using recursion, marking nodes visited to avoid repeats.

Execution Table

Step	Operation	Current Node	Visited Set	Call Stack	Action	Graph State
1	Start DFS	A	{}	[A]	Mark A visited	A: [B, C], B: [D], C: [E], D: [], E: []
2	Explore neighbor	A	{A}	[A, B]	B not visited, recurse	Same
3	Mark visited	B	{A}	[A, B]	Mark B visited	Same
4	Explore neighbor	B	{A, B}	[A, B, D]	D not visited, recurse	Same
5	Mark visited	D	{A, B}	[A, B, D]	Mark D visited	Same
6	Explore neighbors	D	{A, B, D}	[A, B, D]	No neighbors, backtrack	Same
7	Backtrack	B	{A, B, D}	[A, B]	Return to B	Same
8	All neighbors done	B	{A, B, D}	[A]	Backtrack to A	Same
9	Explore neighbor	A	{A, B, D}	[A, C]	C not visited, recurse	Same
10	Mark visited	C	{A, B, D}	[A, C]	Mark C visited	Same
11	Explore neighbor	C	{A, B, D, C}	[A, C, E]	E not visited, recurse	Same
12	Mark visited	E	{A, B, D, C}	[A, C, E]	Mark E visited	Same
13	Explore neighbors	E	{A, B, D, C, E}	[A, C, E]	No neighbors, backtrack	Same
14	Backtrack	C	{A, B, D, C, E}	[A, C]	Return to C	Same
15	All neighbors done	C	{A, B, D, C, E}	[A]	Backtrack to A	Same
16	All neighbors done	A	{A, B, D, C, E}	[]	DFS complete	Same

💡 All reachable nodes visited, call stack empty, DFS ends

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 5	After Step 9	After Step 12	Final
visited	{}	{A}	{A, B}	{A, B, D}	{A, B, D}	{A, B, D, C, E}	{A, B, D, C, E}
call_stack	[]	[A]	[A, B]	[A, B, D]	[A, C]	[A, C, E]	[]

Key Moments - 3 Insights

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

Marking visited early (see Step 1 and Step 3) prevents revisiting the same node and infinite loops, as shown in the visited set updates in the execution_table.

Why does DFS backtrack when a node has no unvisited neighbors?

When no neighbors are left (Step 6 and Step 13), DFS returns to the previous node to explore other paths, shown by the call stack shrinking in the execution_table.

How does the call stack represent the current path in DFS?

The call stack (variable_tracker) shows nodes currently being explored; pushing when recursing deeper and popping when backtracking, matching the execution_table's Call Stack column.

Visual Quiz - 3 Questions

Look at the execution_table at Step 5, which nodes are marked visited?

A {A}

B {A, B, D}

C {A, B}

D {}

💡 Hint

Check the Visited Set column at Step 5 in the execution_table.

At which step does DFS start exploring node C?

A Step 9

B Step 7

C Step 12

D Step 3

💡 Hint

Look at the Current Node and Operation columns in the execution_table.

If node E had a neighbor F not visited, what would happen at Step 12?

A DFS would backtrack immediately

B Node E would be skipped

C DFS would recurse into F, adding it to the call stack

D DFS would restart from node A

💡 Hint

Refer to the recursion behavior shown in Steps 2-5 in the execution_table.

Concept Snapshot

DFS explores graph nodes deeply by:
- Starting at a node, marking it visited
- Recursively visiting unvisited neighbors
- Using a call stack to track path
- Backtracking when no neighbors left
- Ends when all reachable nodes visited

Full Transcript

Depth First Search (DFS) starts at a chosen node, marks it visited to avoid repeats, then explores each neighbor deeply before backtracking. The call stack tracks the current path. When a node has no unvisited neighbors, DFS backtracks to explore other paths. This continues until all reachable nodes are visited. The visited set prevents cycles and repeated visits. The execution table shows each step's current node, visited nodes, call stack, and actions taken, illustrating the recursive nature of DFS.

Practice

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

easy

A. Visit all nodes at the current depth before moving deeper

B. Visit nodes randomly without any order

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

D. Only visit nodes with no outgoing edges

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 with other traversal methods

   BFS visits nodes level by level, but DFS goes deep first.

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 nodes level-wise
• Assuming DFS visits nodes randomly

2. Which of the following is the correct way to start a DFS function in C for a graph represented by adjacency list adj and visited array visited?

easy

A. void dfs(int node) { visited[node] = 1; for(int i=0; i

B. void dfs(int node) { visited[node] = true; for(int i=0; i

C. void dfs(int node) { visited[node] = 0; for(int i=0; i

D. void dfs(int node) { visited[node] = 1; for(int i=0; i

Solution

1. Step 1: Mark current node as visited

   Set visited[node] = 1 (or true) to avoid revisiting.

2. Step 2: Traverse neighbors only if not visited

   Check if neighbor is unvisited before recursive DFS call to prevent infinite loops.

3. Final Answer:

   void dfs(int node) { visited[node] = 1; for(int i=0; i -> Option D

4. Quick Check:

   Mark visited and check before recursion [OK]

Hint: Always check visited before recursive DFS call [OK]

Common Mistakes:

• Not checking if neighbor is visited
• Using wrong visited value (0 instead of 1)
• Using .size() instead of .length in C arrays

3. Consider the following graph adjacency list:
0: [1, 2]
1: [2]
2: [0, 3]
3: [3]
Starting DFS from node 2, what is the order of nodes visited?

medium

A. [2, 3, 0, 1]

B. [2, 0, 1, 3]

C. [2, 0, 3, 1]

D. [2, 1, 0, 3]

Solution

1. Step 1: Start DFS at node 2

   Visit 2, mark visited. Neighbors: 0 and 3.

2. Step 2: Visit neighbor 0 first

   From 2, go to 0. Visit 0, neighbors: 1 and 2 (2 already visited).

3. Step 3: Visit neighbor 1 from 0

   Visit 1, neighbor: 2 (visited). Backtrack.

4. Step 4: Back to 2, visit neighbor 3

   Visit 3, neighbor: 3 (already visited). End.

5. Final Answer:

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

6. Quick Check:

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

Hint: Follow neighbors depth-first, mark visited to avoid repeats [OK]

Common Mistakes:

• Visiting nodes multiple times
• Visiting neighbors in wrong order
• Ignoring visited checks causing loops

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

void dfs(int node) {
  visited[node] = 1;
  for(int i=0; i<adj[node].length; i++) {
    dfs(adj[node][i]);
  }
}

medium

A. Missing check if neighbor is already visited before recursive call

B. Visited array is not initialized

C. Incorrect loop condition syntax

D. Visited[node] should be set after recursion

Solution

1. Step 1: Analyze DFS recursion calls

   The code calls dfs on all neighbors without checking if they are visited.

2. Step 2: Identify risk of infinite recursion

   Without visited check, DFS may revisit nodes endlessly causing stack overflow.

3. Final Answer:

   Missing check if neighbor is already visited before recursive call -> Option A

4. Quick Check:

   Always check visited before recursion [OK]

Hint: Check visited before recursive DFS call to avoid loops [OK]

Common Mistakes:

• Assuming visited check is optional
• Setting visited after recursion
• Ignoring infinite recursion risk

5. Given a directed graph with possible cycles, how can DFS be modified to detect if a cycle exists?

hard

A. Use a recursion stack array to track nodes in the current path and check if a node is revisited in this stack

B. Only mark nodes visited after all neighbors are processed

C. Use BFS instead of DFS to detect cycles

D. Ignore visited array and rely on node values

Solution

1. Step 1: Understand cycle detection in DFS

   Detect cycles by tracking nodes currently in recursion (call) stack.

2. Step 2: Use recursion stack array

   Maintain an array marking nodes in current DFS path; if a neighbor is in this stack, a cycle exists.

3. Step 3: Differentiate from visited array

   Visited marks all visited nodes; recursion stack tracks current path only.

4. Final Answer:

   Use a recursion stack array to track nodes in the current path and check if a node is revisited in this stack -> Option A

5. Quick Check:

   Recursion stack detects cycles in DFS [OK]

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

Common Mistakes:

• Confusing visited with recursion stack
• Using BFS for cycle detection in directed graphs
• Not tracking current path nodes