DFS Depth First Search on Graph in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of DFS traversal on a simple graph

What is the output of the following DFS traversal starting from node 0?

DSA C++

/* Graph adjacency list representation:
0: 1, 2
1: 2
2: 0, 3
3: 3
*/

#include <iostream>
#include <vector>
using namespace std;

void dfs(int node, vector<vector<int>>& graph, vector<bool>& visited) {
    visited[node] = true;
    cout << node << " ";
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor, graph, visited);
        }
    }
}

int main() {
    vector<vector<int>> graph = {
        {1, 2},
        {2},
        {0, 3},
        {3}
    };
    vector<bool> visited(4, false);
    dfs(0, graph, visited);
    return 0;
}

A 0 2 1 3

B 0 2 3 1

C 0 1 3 2

D 0 1 2 3

💡 Hint

Trace the DFS calls starting from node 0 and follow neighbors in order.

The DFS starts at node 0, visits 1 first (the first neighbor), then from 1 visits 2, and from 2 visits 3. The output is the order nodes are first visited.

🧠 Conceptual

intermediate

DFS stack behavior on graph traversal

Which data structure does DFS use implicitly or explicitly to keep track of nodes to visit next?

A Queue

B Stack

C Hash Table

D Heap

💡 Hint

Think about the order in which nodes are revisited in DFS.

DFS uses a stack (explicitly or via recursion call stack) to remember nodes to visit next, exploring as deep as possible before backtracking.

🔧 Debug

advanced

Identify the error in DFS implementation

What error will occur when running this DFS code on a graph with cycles?

DSA C++

#include <iostream>
#include <vector>
using namespace std;

void dfs(int node, vector<vector<int>>& graph) {
    cout << node << " ";
    for (int neighbor : graph[node]) {
        dfs(neighbor, graph);
    }
}

int main() {
    vector<vector<int>> graph = {
        {1},
        {2},
        {0}
    };
    dfs(0, graph);
    return 0;
}

A No output printed

B Compilation error: missing visited array

C Stack overflow due to infinite recursion

D Program runs correctly and prints 0 1 2

💡 Hint

Consider what happens when the graph has a cycle and no visited check.

The DFS does not track visited nodes, so it revisits nodes endlessly in a cycle, causing infinite recursion and stack overflow.

❓ Predict Output

advanced

DFS traversal order with multiple neighbors

What is the output of DFS starting from node 1 on this graph?

DSA C++

/* Graph adjacency list:
0: 2, 3
1: 0, 4
2: 3
3: 4
4: 
*/

#include <iostream>
#include <vector>
using namespace std;

void dfs(int node, vector<vector<int>>& graph, vector<bool>& visited) {
    visited[node] = true;
    cout << node << " ";
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor, graph, visited);
        }
    }
}

int main() {
    vector<vector<int>> graph = {
        {2, 3},
        {0, 4},
        {3},
        {4},
        {}
    };
    vector<bool> visited(5, false);
    dfs(1, graph, visited);
    return 0;
}

A 1 0 3 4 2

B 1 4 0 2 3

C 1 0 3 2 4

D 1 0 2 3 4

💡 Hint

Follow neighbors in order and mark visited nodes carefully.

Starting at 1, DFS visits 0 first, then from 0 visits 2, then from 2 visits 3, and finally from 3 visits 4.

🧠 Conceptual

expert

DFS time complexity on graph with V vertices and E edges

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

A O(V + E)

B O(V^2)

C O(V * E)

D O(E^2)

💡 Hint

Consider how many times each vertex and edge is visited during DFS.

DFS visits each vertex once and explores each edge once, so total time is proportional to vertices plus edges.

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