Why DFS Depth First Search on Graph in DSA C++?

The Big Idea

What if you could explore every path in a maze without ever getting lost or repeating steps?

The Scenario

Imagine you have a huge maze with many paths and rooms. You want to find if there is a way to reach a certain room starting from the entrance. Trying to check every path by hand would be confusing and take forever.

The Problem

Manually exploring each path can be slow and you might get lost or repeat the same paths again and again. It is easy to miss some rooms or waste time going back and forth without a clear plan.

The Solution

Depth First Search (DFS) helps by exploring one path deeply before backtracking. It uses a simple rule to remember where it has been, so it never repeats or misses rooms. This makes searching fast and organized.

Before vs After

✗ Before

void search(int start) {
  // Try all paths randomly
  // No memory of visited rooms
  // May repeat or miss rooms
}

✓ After

void dfs(int node) {
  visited[node] = true;
  for (int neighbor : graph[node]) {
    if (!visited[neighbor]) dfs(neighbor);
  }
}

What It Enables

DFS enables efficient and complete exploration of all connected parts of a graph or maze without getting lost or repeating work.

Real Life Example

Finding all friends connected to you in a social network by exploring friend connections deeply one by one.

Key Takeaways

Manual path checking is slow and confusing.

DFS explores deeply and remembers visited nodes.

DFS helps find all reachable nodes efficiently.

Practice

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

easy

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

B. Visit all neighbors of a node before moving deeper

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

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 other branches.

2. Step 2: Compare with other traversal methods

   BFS visits neighbors first, but DFS goes deep first, matching Explore as far as possible along each branch before backtracking.

3. Final Answer:

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

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 C++ syntax to start a DFS from node 0 using recursion?

easy

A. DFS(visited, graph, 0);

B. dfs(0, visited, graph);

C. dfs(graph, 0, visited);

D. dfs(visited, 0, graph);

Solution

1. Step 1: Check typical DFS function signature

   Usually, DFS is called as dfs(node, visited, graph) where node is current node.

2. Step 2: Match the correct order

   dfs(0, visited, graph); matches the common order: dfs(0, visited, graph).

3. Final Answer:

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

4. Quick Check:

   Call dfs with node first [OK]

Hint: DFS call starts with node, then visited, then graph [OK]

Common Mistakes:

• Swapping argument order
• Using uppercase DFS instead of dfs
• Passing graph before node

3. What will be the output order of nodes visited by DFS starting from node 0 in the graph below?

Graph adjacency list:
0: [1, 2]
1: [3]
2: []
3: []

Assuming DFS visits neighbors in ascending order.

medium

A. [0, 3, 1, 2]

B. [0, 2, 1, 3]

C. [0, 1, 3, 2]

D. [0, 1, 2, 3]

Solution

1. Step 1: Start DFS at node 0

   Visit 0, then explore neighbors in ascending order: 1, then 2.

2. Step 2: Explore neighbor 1

   From 1, visit 3 (only neighbor), then backtrack.

3. Step 3: Explore neighbor 2

   Node 2 has no neighbors, so visit and backtrack.

4. Final Answer:

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

5. Quick Check:

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

Hint: Visit neighbors in order, go deep first [OK]

Common Mistakes:

• Visiting node 2 before node 1
• Not backtracking properly
• Confusing BFS order with DFS

4. Given the following DFS code snippet, what is the error?

void dfs(int node, vector<bool> &visited, vector &graph) {
  visited[node] = true;
  for (int i = 0; i < graph[node].size(); i++) {
    int neighbor = graph[node][i];
    if (visited[neighbor] = false) {
      dfs(neighbor, visited, graph);
    }
  }
}

medium

A. The function should return an int instead of void

B. The loop should use 'i <= graph[node].size()' instead of '<'

C. The visited vector should be passed by value, not reference

D. The condition 'if (visited[neighbor] = false)' uses assignment instead of comparison

Solution

1. Step 1: Check the if condition inside the loop

   The condition uses '=' which assigns false instead of comparing.

2. Step 2: Understand the impact of assignment in condition

   This causes the condition to always be false, so DFS won't recurse properly.

3. Final Answer:

   The condition 'if (visited[neighbor] = false)' uses assignment instead of comparison -> Option D

4. Quick Check:

   Use '==' for comparison, not '=' [OK]

Hint: Use '==' to compare, not '=' [OK]

Common Mistakes:

• Using '=' instead of '==' in conditions
• Loop boundary off-by-one errors
• Passing visited by value causing no effect

5. You have a graph with 5 nodes (0 to 4) and edges: 0-1, 0-2, 1-3, 1-4. Using DFS starting at node 0, how can you modify the algorithm to count the number of nodes reachable from node 0?

hard

A. Add a counter variable incremented each time a node is visited during DFS

B. Count nodes after DFS by checking which nodes have no neighbors

C. Use BFS instead of DFS to count nodes reachable

D. Count nodes by summing the degrees of all nodes

Solution

1. Step 1: Understand counting reachable nodes

   Counting nodes visited during DFS means incrementing a counter when marking a node visited.

2. Step 2: Why other options fail

   Counting nodes with no neighbors or summing degrees won't give reachable count; BFS is alternative but not required.

3. Final Answer:

   Add a counter variable incremented each time a node is visited during DFS -> Option A

4. Quick Check:

   Count nodes when visited in DFS [OK]

Hint: Increment count inside DFS when visiting nodes [OK]

Common Mistakes:

• Counting nodes with no neighbors instead of visited
• Using BFS unnecessarily
• Summing degrees instead of counting visited