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] = true;
  foreach (var neighbor in graph[node]) {
    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	Stack (Call Trace)	Visual State
1	Start DFS	A	{}	[]	Graph: A-B-C-D-E No nodes visited
2	Visit node	A	{A}	[A]	A visited
3	Check neighbor B	A	{A}	[A]	A visited
4	Visit neighbor B	B	{A,B}	[A,B]	A->B visited
5	Check neighbor C	B	{A,B}	[A,B]	A->B visited
6	Visit neighbor C	C	{A,B,C}	[A,B,C]	A->B->C visited
7	Check neighbor D	C	{A,B,C}	[A,B,C]	A->B->C visited
8	Visit neighbor D	D	{A,B,C,D}	[A,B,C,D]	A->B->C->D visited
9	Check neighbor E	D	{A,B,C,D}	[A,B,C,D]	A->B->C->D visited
10	Visit neighbor E	E	{A,B,C,D,E}	[A,B,C,D,E]	A->B->C->D->E visited
11	No unvisited neighbors	E	{A,B,C,D,E}	[A,B,C,D,E]	All neighbors of E visited
12	Backtrack	D	{A,B,C,D,E}	[A,B,C,D]	Back to D
13	No more neighbors	D	{A,B,C,D,E}	[A,B,C]	Back to C
14	No more neighbors	C	{A,B,C,D,E}	[A,B]	Back to B
15	No more neighbors	B	{A,B,C,D,E}	[A]	Back to A
16	No more neighbors	A	{A,B,C,D,E}	[]	DFS complete
17	End	-	{A,B,C,D,E}	[]	All reachable nodes visited

💡 All nodes reachable from A are visited, recursion stack is empty, DFS ends.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 8	After Step 10	Final
visited	{}	{A}	{A,B}	{A,B,C}	{A,B,C,D}	{A,B,C,D,E}	{A,B,C,D,E}
stack	[]	[A]	[A,B]	[A,B,C]	[A,B,C,D]	[A,B,C,D,E]	[]
current_node	-	A	B	C	D	E	-

Key Moments - 3 Insights

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

Marking as visited early (see Step 2) prevents revisiting the same node and infinite loops in cycles.

Why does the stack grow and shrink during DFS?

The stack (call trace) grows as we go deeper (Steps 2,4,6...) and shrinks when backtracking (Steps 12-15), showing recursion depth.

What happens if a neighbor is already visited?

If neighbor is visited (not shown explicitly here), DFS skips it to avoid repeated visits, ensuring each node is processed once.

Visual Quiz - 3 Questions

Look at the execution table, what is the visited set after Step 6?

A {A,B,C}

B {A,B}

C {A,B,C,D}

D {A}

💡 Hint

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

At which step does the DFS start backtracking from node E?

A Step 10

B Step 11

C Step 12

D Step 13

💡 Hint

Look for 'Backtrack' operation and node E in the execution_table.

If node C had no neighbor D, how would the stack change at Step 8?

A Stack would include D anyway

B Stack would not include D, backtrack earlier

C Stack would be empty at Step 8

D Stack would include E directly

💡 Hint

Refer to the stack changes in execution_table and how neighbors affect recursion depth.

Concept Snapshot

DFS (Depth First Search) explores graph nodes deeply before backtracking.
Start at a node, mark visited, recursively visit unvisited neighbors.
Uses recursion stack to track path.
Prevents cycles by marking visited early.
Ends when all reachable nodes are visited.

Full Transcript

DFS Depth First Search starts at a chosen node, marks it visited, then explores each neighbor deeply using recursion. The recursion stack grows as we go deeper and shrinks when backtracking. Each node is visited once to avoid cycles. The process ends when all reachable nodes are visited and the recursion stack is empty.

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 until all are visited

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 neighbors first, 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 neighbors first
• Assuming DFS visits nodes by distance

2. Which of the following is the correct way to start a DFS traversal in C# using recursion on a graph represented by adjacency list Dictionary<int, List<int>> graph?

easy

A. void DFS(int node, HashSet<int> visited) { if (visited.Contains(node)) return; visited.Add(node); foreach (var neighbor in graph[node]) DFS(neighbor, visited); }

B. void DFS(int node) { visited.Add(node); foreach (var neighbor in graph[node]) DFS(neighbor); }

C. void DFS(int node, List<int> visited) { if (visited.Contains(node)) return; visited.Add(node); foreach (var neighbor in graph[node]) DFS(neighbor, visited); }

D. void DFS(int node, HashSet<int> visited) { visited.Add(node); foreach (var neighbor in graph) DFS(neighbor, visited); }

Solution

1. Step 1: Check parameters and visited tracking

   void DFS(int node, HashSet<int> visited) { if (visited.Contains(node)) return; visited.Add(node); foreach (var neighbor in graph[node]) DFS(neighbor, visited); } uses HashSet to track visited nodes and prevents revisiting.

2. Step 2: Verify iteration over neighbors

   void DFS(int node, HashSet<int> visited) { if (visited.Contains(node)) return; visited.Add(node); foreach (var neighbor in graph[node]) DFS(neighbor, visited); } correctly iterates over neighbors of the current node from the graph dictionary.

3. Final Answer:

   void DFS(int node, HashSet<int> visited) { if (visited.Contains(node)) return; visited.Add(node); foreach (var neighbor in graph[node]) DFS(neighbor, visited); } -> Option A

4. Quick Check:

   Correct recursion with visited check [OK]

Hint: Use HashSet to track visited nodes in DFS recursion [OK]

Common Mistakes:

• Not checking if node is visited before recursion
• Using List instead of HashSet for visited (slow lookup)
• Iterating over graph keys instead of neighbors

3. Given the graph adjacency list:

var graph = new Dictionary {
  {1, new List<int>{2, 3}},
  {2, new List<int>{4}},
  {3, new List<int>{4}},
  {4, new List<int>()}
};

List<int> visited = new List<int>();
DFS(1, visited); // DFS as defined in option C above
Console.WriteLine(string.Join(", ", visited));

What is the output?

medium

A. 1, 2, 3, 4

B. 1, 2, 4, 3

C. 1, 3, 4, 2

D. 1, 4, 2, 3

Solution

1. Step 1: Start DFS from node 1

   Visit 1, mark visited. Neighbors: 2, 3.

2. Step 2: Visit neighbor 2 first

   Visit 2, then its neighbor 4. 4 has no neighbors, backtrack.

3. Step 3: Backtrack to 1 and visit neighbor 3

   Visit 3, then neighbor 4 (already visited, skip).

4. Step 4: Order of visited nodes

   Visited nodes in order: 1, 2, 4, 3.

5. Final Answer:

   1, 2, 4, 3 -> Option B

6. Quick Check:

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

Hint: DFS visits neighbors in order, backtracks after deepest node [OK]

Common Mistakes:

• Assuming BFS order instead of DFS
• Visiting node 3 before node 2
• Revisiting already visited nodes

4. Consider this DFS code snippet in C#:

void DFS(int node, HashSet<int> visited) {
  visited.Add(node);
  foreach (var neighbor in graph.Keys) {
    if (!visited.Contains(neighbor)) {
      DFS(neighbor, visited);
    }
  }
}

What is the main problem with this DFS implementation?

medium

A. It iterates over all graph nodes instead of neighbors of the current node

B. It does not add the current node to visited

C. It uses List instead of HashSet for visited nodes

D. It does not check if the node is null before recursion

Solution

1. Step 1: Analyze the foreach loop

   The loop iterates over all keys in the graph, not neighbors of the current node.

2. Step 2: Understand DFS neighbor traversal

   DFS should explore neighbors of the current node, not all nodes in the graph.

3. Final Answer:

   It iterates over all graph nodes instead of neighbors of the current node -> Option A

4. Quick Check:

   DFS must visit neighbors, not all nodes [OK]

Hint: Loop over neighbors, not all graph keys [OK]

Common Mistakes:

• Looping over graph.Keys instead of graph[node]
• Forgetting to add node to visited
• Not checking visited before recursion

5. You want to find if there is a path from node 1 to node 5 in this directed graph:

var graph = new Dictionary {
  {1, new List<int>{2, 3}},
  {2, new List<int>{4}},
  {3, new List<int>{4, 5}},
  {4, new List<int>{}},
  {5, new List<int>{}}
};

bool DFS(int current, int target, HashSet<int> visited) {
  if (current == target) return true;
  visited.Add(current);
  foreach (var neighbor in graph[current]) {
    if (!visited.Contains(neighbor)) {
      if (DFS(neighbor, target, visited)) return true;
    }
  }
  return false;
}

var visited = new HashSet<int>();
bool result = DFS(1, 5, visited);
Console.WriteLine(result);

What will be printed?

hard

A. Runtime exception

B. False

C. Compilation error

D. True

Solution

1. Step 1: Start DFS from node 1 looking for 5

   Visit 1, neighbors 2 and 3.

2. Step 2: Explore neighbor 2

   From 2, visit 4. 4 has no neighbors, backtrack.

3. Step 3: Explore neighbor 3

   From 3, neighbors are 4 and 5. 4 visited, then 5 found matches target.

4. Step 4: DFS returns true when target found

   DFS returns true and prints True.

5. Final Answer:

   True -> Option D

6. Quick Check:

   Path exists from 1 to 5 [OK]

Hint: DFS returns true immediately when target found [OK]

Common Mistakes:

• Assuming no path because 5 is not direct neighbor
• Not returning true when target found
• Forgetting to mark visited nodes