DFS Depth First Search on Graph in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

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

DFS explores as far as possible along each branch before backtracking, visiting nodes deeply before moving to neighbors.

beginner

In DFS, what data structure is commonly used to keep track of nodes to visit next?

A stack is used, either explicitly or via recursion call stack, to remember nodes to visit next.

beginner

How does DFS avoid visiting the same node multiple times?

DFS uses a 'visited' set or array to mark nodes that have already been explored.

intermediate

What is the difference between DFS and BFS in graph traversal?

DFS goes deep into a branch before backtracking, while BFS explores neighbors level by level.

intermediate

What is the time complexity of DFS on a graph with V vertices and E edges?

The time complexity is O(V + E) because each vertex and edge is visited once.

Which data structure is naturally used by DFS when implemented recursively?

A Heap

B Queue

C Hash Table

D Stack

DFS uses the call stack implicitly, which behaves like a stack data structure.

What does DFS do when it reaches a node with no unvisited neighbors?

A Backtracks to previous node

B Stops completely

C Restarts from the first node

D Skips to a random node

DFS backtracks to the previous node to explore other branches.

Which of these is NOT a typical use case of DFS?

A Finding shortest path in unweighted graph

B Topological sorting

C Finding connected components

D Detecting cycles in a graph

Shortest path in unweighted graphs is better found by BFS, not DFS.

What is the purpose of the 'visited' array in DFS?

A To store node values

B To mark nodes already explored

C To count edges

D To sort nodes

The 'visited' array prevents revisiting nodes and infinite loops.

If a graph has 5 vertices and 7 edges, what is the maximum number of times DFS will visit edges?

A 5

B 12

C 7

D 35

DFS visits each edge once, so maximum is 7.

Explain how DFS explores a graph starting from a given node.

Think about going deep first before moving sideways.

Describe how DFS can be used to detect cycles in a graph.

Focus on revisiting nodes during the current path.

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