DFS Depth First Search on Graph in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to start DFS from the given node.

DSA C++

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

Drag options to blanks, or click blank then click option'

Avisited

Bnode

Cgraph

Dadj

Attempts:

3 left

💡 Hint

Common Mistakes

Using the current node instead of the adjacent node in the visited check.

The DFS visits adjacent nodes. We check if the adjacent node adj is visited before calling DFS recursively.

2fill in blank

medium

Complete the code to initialize the visited vector for DFS.

DSA C++

int n = graph.size();
vector<bool> visited([1], false);

Drag options to blanks, or click blank then click option'

A0

Bn

Cgraph.size() - 1

Dn + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using size off by one, causing out-of-range errors.

The visited vector size should match the number of nodes n in the graph.

3fill in blank

hard

Fix the error in the DFS recursive call to avoid infinite recursion.

DSA C++

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

Drag options to blanks, or click blank then click option'

Anode

Bvisited

Cadj

Dgraph[node]

Attempts:

3 left

💡 Hint

Common Mistakes

Passing the current node instead of the adjacent node.

The recursive call must be on the adjacent node adj, not the current node node.

4fill in blank

hard

Fill both blanks to create a DFS function that prints nodes in order of visit.

DSA C++

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

Drag options to blanks, or click blank then click option'

Anode

Badj

Cgraph

Dvisited

Attempts:

3 left

💡 Hint

Common Mistakes

Marking or printing the adjacent node instead of the current node.

We mark the current node node as visited and print it before visiting adjacent nodes.

5fill in blank

hard

Fill all three blanks to create a DFS that counts connected components in an undirected graph.

DSA C++

int countComponents(int n, vector<vector<int>>& graph) {
    vector<bool> visited(n, false);
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (!visited[[1]]) {
            dfs([2], graph, visited);
            count[3];
        }
    }
    return count;
}

Drag options to blanks, or click blank then click option'

Ai

C++

D--

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong variable in visited check or DFS call.

Forgetting to increment count.

We check if node i is visited, run DFS from i, and increment the count of connected components.

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