BFS Breadth First Search on Graph in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of BFS traversal on a simple graph

What is the output of the BFS traversal starting from node 0 in the given graph?

DSA C++

/* Graph edges:
0 -> 1, 2
1 -> 2
2 -> 0, 3
3 -> 3
*/

#include <iostream>
#include <vector>
#include <queue>

void bfs(int start, const std::vector<std::vector<int>>& graph) {
    std::vector<bool> visited(graph.size(), false);
    std::queue<int> q;
    q.push(start);
    visited[start] = true;
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        std::cout << node << " ";
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}

int main() {
    std::vector<std::vector<int>> graph = {
        {1, 2},
        {2},
        {0, 3},
        {3}
    };
    bfs(0, graph);
    return 0;
}

A 0 1 2 3

B 0 1 3 2

C 0 2 1 3

D 0 3 2 1

💡 Hint

Remember BFS visits neighbors level by level, starting from the start node.

Starting from node 0, BFS visits neighbors 1 and 2 in order. Then from 1, it visits 2 but 2 is already visited. From 2, it visits 3. So the order is 0 1 2 3.

❓ Predict Output

intermediate

BFS traversal output on disconnected graph

What is the output of BFS traversal starting from node 1 in this disconnected graph?

DSA C++

#include <iostream>
#include <vector>
#include <queue>

void bfs(int start, const std::vector<std::vector<int>>& graph) {
    std::vector<bool> visited(graph.size(), false);
    std::queue<int> q;
    q.push(start);
    visited[start] = true;
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        std::cout << node << " ";
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}

int main() {
    std::vector<std::vector<int>> graph = {
        {1},
        {},
        {3},
        {}
    };
    bfs(1, graph);
    return 0;
}

A 1

B 1 0

C 1 3

D 1 0 3

💡 Hint

Check which nodes are reachable from node 1.

Node 1 has no neighbors, so BFS visits only node 1.

🔧 Debug

advanced

Identify the error in BFS implementation

What error will this BFS code produce when run on the given graph?

DSA C++

#include <iostream>
#include <vector>
#include <queue>

void bfs(int start, const std::vector<std::vector<int>>& graph) {
    std::vector<bool> visited(graph.size(), false);
    std::queue<int> q;
    q.push(start);
    // Missing visited[start] = true;
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        std::cout << node << " ";
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}

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

A Prints 0 1 2 once and ends normally

B Program crashes with segmentation fault

C Infinite loop printing 0 1 2 repeatedly

D Compilation error due to missing header

💡 Hint

Check if the start node is marked visited before starting the loop.

Since visited[start] is not set true initially, the start node is re-added repeatedly causing infinite loop.

🧠 Conceptual

advanced

BFS uses which data structure to keep track of nodes to visit?

Which data structure is used internally by BFS to keep track of nodes to visit next?

A Hash Map

B Stack

C Priority Queue

D Queue

💡 Hint

BFS visits nodes level by level in order of discovery.

BFS uses a queue to process nodes in the order they are discovered, ensuring level order traversal.

🚀 Application

expert

Shortest path length using BFS in unweighted graph

Given an unweighted graph, which BFS modification helps find the shortest path length from start node to all other nodes?

A Use a stack instead of a queue to process nodes

B Keep a distance array initialized with -1, set start node distance to 0, update neighbors with distance +1

C Use DFS instead of BFS to find shortest paths

D Mark nodes as visited only after processing all neighbors

💡 Hint

Shortest path in unweighted graph is found by levels of BFS.

By tracking distance from start node and updating neighbors with distance +1 when first visited, BFS finds shortest paths.

Practice

1. What does BFS (Breadth First Search) primarily use to keep track of nodes to visit next in a graph?

easy

A. A queue data structure

B. A stack data structure

C. A priority queue

D. A hash map

Solution

1. Step 1: Understand BFS traversal method

   BFS explores nodes level by level, visiting all neighbors before moving deeper.

2. Step 2: Identify the data structure used

   To maintain the order of visiting nodes level-wise, BFS uses a queue which follows FIFO (First In First Out).

3. Final Answer:

   A queue data structure -> Option A

4. Quick Check:

   BFS uses queue = B [OK]

Hint: BFS uses FIFO order, so it needs a queue [OK]

Common Mistakes:

• Confusing BFS with DFS which uses a stack
• Thinking BFS uses a priority queue
• Assuming BFS uses a hash map for order

2. Which of the following is the correct way to declare a queue for BFS traversal of integers in C++?

easy

A. vector<int> q;

B. queue<int> q;

C. stack<int> q;

D. list<int> q;

Solution

1. Step 1: Identify the correct STL container for queue

   In C++, the standard queue container is declared as queue<type>.

2. Step 2: Match the declaration for integer queue

   queue<int> q; correctly declares a queue of integers.

3. Final Answer:

   queue<int> q; -> Option B

4. Quick Check:

   Correct queue syntax = queue<int> q; [OK]

Hint: Use queue<int> for BFS integer queue in C++ [OK]

Common Mistakes:

• Using stack instead of queue
• Using vector or list which are not queues
• Missing template angle brackets

3. Consider the following graph represented as adjacency list:

0: 1, 2
1: 0, 3
2: 0, 3
3: 1, 2

If BFS starts from node 0, what is the order of nodes visited?

medium

A. [0, 1, 3, 2]

B. [0, 2, 1, 3]

C. [0, 3, 1, 2]

D. [0, 1, 2, 3]

Solution

1. Step 1: Start BFS from node 0

   Visit node 0 first, enqueue neighbors 1 and 2.

2. Step 2: Visit neighbors in queue order

   Dequeue 1, enqueue its neighbor 3 (0 already visited). Then dequeue 2, enqueue 3 but already visited.

3. Step 3: Visit node 3

   Finally dequeue 3.

4. Final Answer:

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

5. Quick Check:

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

Hint: Visit neighbors in queue order, avoid revisits [OK]

Common Mistakes:

• Visiting neighbors in wrong order
• Revisiting nodes already visited
• Confusing BFS with DFS order

4. The following BFS code snippet has a bug. What is the error?

void bfs(int start, vector& adj) {
  vector<bool> visited(adj.size(), false);
  queue<int> q;
  q.push(start);
  while (!q.empty()) {
    int node = q.front();
    q.pop();
    cout << node << " ";
    for (int neighbor : adj[node]) {
      if (!visited[neighbor]) {
        q.push(neighbor);
      }
    }
  }
}

medium

A. Neighbors are not iterated correctly

B. Queue is not initialized properly

C. Visited array is never updated to true for visited nodes

D. Start node is not pushed into the queue

Solution

1. Step 1: Check visited array usage

   Visited array is created but nodes are never marked visited after visiting.

2. Step 2: Understand impact on BFS

   Without marking visited true, nodes can be enqueued multiple times causing infinite loops or repeated visits.

3. Final Answer:

   Visited array is never updated to true for visited nodes -> Option C

4. Quick Check:

   Must mark visited[node] = true after popping [OK]

Hint: Always mark nodes visited after dequeuing [OK]

Common Mistakes:

• Forgetting to mark visited nodes
• Pushing start node multiple times
• Incorrect loop conditions

5. Given a graph with nodes 0 to 4 and edges: 0-1, 0-2, 1-3, 2-3, 3-4. Using BFS starting from node 0, which node is visited at the 3rd position in the BFS order?

hard

A. 2

B. 4

C. 1

D. 3

Solution

1. Step 1: List neighbors and BFS order

   Start at 0, enqueue neighbors 1 and 2. BFS order so far: [0]

2. Step 2: Visit nodes in queue order

   Dequeue 1 (2nd visited), enqueue 3. Dequeue 2 (3rd visited), enqueue 3 but already enqueued.

3. Step 3: Confirm 3rd visited node

   The third node visited is 2.

4. Final Answer:

   2 -> Option A

5. Quick Check:

   Third visited node = 2 [OK]

Hint: Track queue order carefully to find nth visited node [OK]

Common Mistakes:

• Mixing order of neighbors
• Counting start node incorrectly
• Ignoring repeated nodes in queue