Shortest Path in Unweighted Graph Using BFS in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of BFS shortest path distance array

What is the output of the distance array after running BFS from node 0 on the given graph?

DSA C++

/* Graph edges:
0 - 1
0 - 2
1 - 2
1 - 3
2 - 4
3 - 4

BFS from node 0 to find shortest distances */
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    int n = 5;
    vector<vector<int>> adj(n);
    adj[0] = {1, 2};
    adj[1] = {0, 2, 3};
    adj[2] = {0, 1, 4};
    adj[3] = {1, 4};
    adj[4] = {2, 3};

    vector<int> dist(n, -1);
    queue<int> q;
    dist[0] = 0;
    q.push(0);

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }

    for (int d : dist) cout << d << " ";
    return 0;
}

A [0, 1, 2, 1, 2]

B [0, 1, 1, 2, 2]

C [0, 1, 1, 1, 2]

D [0, 2, 1, 2, 3]

💡 Hint

Trace BFS layer by layer starting from node 0.

Starting from node 0, nodes 1 and 2 are at distance 1. Node 3 is reached via node 1 at distance 2. Node 4 is reached via node 2 or 3 at distance 2.

🧠 Conceptual

intermediate

Why BFS finds shortest path in unweighted graphs?

Why does BFS guarantee the shortest path distance in an unweighted graph?

A Because BFS calculates edge weights during traversal.

B Because BFS uses a stack to explore nodes deeply first.

C Because BFS marks nodes visited only after exploring all neighbors.

D Because BFS explores nodes in increasing order of their distance from the start node.

💡 Hint

Think about the order nodes are visited in BFS.

BFS visits nodes layer by layer, so the first time it reaches a node is via the shortest path.

🔧 Debug

advanced

Identify the error in BFS shortest path code

What error will this BFS code produce when finding shortest path distances?

DSA C++

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

int main() {
    int n = 4;
    vector<vector<int>> adj(n);
    adj[0] = {1};
    adj[1] = {0, 2};
    adj[2] = {1, 3};
    adj[3] = {2};

    vector<int> dist(n, 0);
    queue<int> q;
    dist[0] = 0;
    q.push(0);

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (dist[v] == 0) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }

    for (int d : dist) cout << d << " ";
    return 0;
}

A The code will run correctly and output shortest distances.

B The code will cause a runtime error due to accessing out-of-bound indices.

C The code will output incorrect distances because nodes with distance 0 are considered unvisited, but node 0 also has distance 0.

D The code will cause a syntax error due to missing semicolons.

💡 Hint

Check how unvisited nodes are marked.

Using 0 as initial distance causes confusion with the start node's distance 0, so unvisited nodes are not detected properly.

❓ Predict Output

advanced

Output of BFS shortest path parent array

What is the parent array after running BFS from node 0 on this graph?

DSA C++

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

BFS from node 0 to find parents */
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    int n = 4;
    vector<vector<int>> adj(n);
    adj[0] = {1, 2};
    adj[1] = {0, 3};
    adj[2] = {0, 3};
    adj[3] = {1, 2};

    vector<int> parent(n, -1);
    queue<int> q;
    parent[0] = 0;
    q.push(0);

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (parent[v] == -1) {
                parent[v] = u;
                q.push(v);
            }
        }
    }

    for (int p : parent) cout << p << " ";
    return 0;
}

A [0, 0, 0, 1]

B [0, -1, -1, -1]

C [0, 1, 2, 0]

D [0, 0, 0, 2]

💡 Hint

Check which node discovers node 3 first.

Node 3 is discovered first from node 1, so parent[3] = 1. Nodes 1 and 2 have parent 0.

🧠 Conceptual

expert

Why BFS is not suitable for weighted graphs?

Why does BFS fail to find the shortest path in graphs with weighted edges?

A Because BFS treats all edges as having equal weight, ignoring actual edge costs.

B Because BFS cannot handle cycles in weighted graphs.

C Because BFS uses a priority queue which is inefficient for weighted graphs.

D Because BFS only works on directed graphs.

💡 Hint

Think about how BFS measures distance.

BFS counts edges, not weights, so it cannot find shortest weighted paths; algorithms like Dijkstra are needed.

Practice

1. What is the main purpose of using BFS (Breadth-First Search) in an unweighted graph?

easy

A. To sort the nodes in topological order

B. To find the maximum depth of the graph

C. To find the shortest path from a source node to all other nodes

D. To detect cycles in the graph

Solution

1. Step 1: Understand BFS traversal

   BFS explores nodes level by level starting from the source node.

2. Step 2: BFS finds shortest paths in unweighted graphs

   Because BFS visits nodes in order of increasing distance, it finds shortest paths from source to all nodes.

3. Final Answer:

   To find the shortest path from a source node to all other nodes -> Option C

4. Quick Check:

   BFS shortest path = D [OK]

Hint: BFS explores neighbors level-wise to find shortest paths [OK]

Common Mistakes:

• Confusing BFS with DFS for shortest path
• Thinking BFS finds maximum depth
• Assuming BFS sorts nodes topologically

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

easy

A. queue<int> q; q.push(0);

B. stack<int> q; q.push(0);

C. queue<int> q; q.insert(0);

D. queue<int> q; q.add(0);

Solution

1. Step 1: Identify correct queue declaration

   In C++, BFS uses std::queue with push() to add elements.

2. Step 2: Check method names

   push() is correct for queue; insert() and add() are invalid; stack is wrong data structure.

3. Final Answer:

   queue<int> q; q.push(0); -> Option A

4. Quick Check:

   queue push() method = C [OK]

Hint: Use std::queue and push() to add elements in BFS [OK]

Common Mistakes:

• Using stack instead of queue
• Using insert() or add() instead of push()
• Confusing queue methods with vector methods

3. Consider the following C++ code snippet for BFS shortest path in an unweighted graph:

int n = 4;
vector adj = {{1,2}, {0,2,3}, {0,1,3}, {1,2}};
vector<int> dist(n, -1);
queue<int> q;
dist[0] = 0;
q.push(0);
while(!q.empty()) {
  int u = q.front(); q.pop();
  for(int v : adj[u]) {
    if(dist[v] == -1) {
      dist[v] = dist[u] + 1;
      q.push(v);
    }
  }
}
for(int i=0; iWhat is the output?

medium

A. 0 1 1 2

B. 0 1 2 3

C. 0 2 1 1

D. 0 1 1 1

Solution

1. Step 1: Initialize distances and start BFS

   dist[0]=0, others -1; start from node 0.

2. Step 2: BFS visits neighbors and updates distances

   From 0: neighbors 1,2 get dist=1; from 1 and 2: neighbor 3 gets dist=2.

3. Final Answer:

   0 1 1 2 -> Option A

4. Quick Check:

   BFS distance array = 0 1 1 2 [OK]

Hint: BFS distance increments by 1 per level from source [OK]

Common Mistakes:

• Mixing up node indices and distances
• Not initializing distances to -1
• Forgetting to check if node was visited

4. The following BFS code snippet is intended to find shortest paths in an unweighted graph. Identify the bug:

int n = 3;
vector adj = {{1}, {0,2}, {1}};
vector<int> dist(n, 0);
queue<int> q;
dist[0] = 0;
q.push(0);
while(!q.empty()) {
  int u = q.front(); q.pop();
  for(int v : adj[u]) {
    if(dist[v] == 0) {
      dist[v] = dist[u] + 1;
      q.push(v);
    }
  }
}
for(int i=0; i

medium

A. dist[u] is not updated inside the loop

B. Queue is not used properly

C. Adjacency list is incorrect

D. dist vector initialized with 0 instead of -1

Solution

1. Step 1: Check distance initialization

   dist initialized with 0 means unvisited nodes are indistinguishable from source.

2. Step 2: Identify impact on BFS logic

   Condition dist[v] == 0 fails to detect unvisited nodes correctly, causing wrong or no updates.

3. Final Answer:

   dist vector initialized with 0 instead of -1 -> Option D

4. Quick Check:

   dist init must be -1 to mark unvisited [OK]

Hint: Initialize distances with -1 to mark unvisited nodes [OK]

Common Mistakes:

• Using 0 as unvisited marker
• Not checking visited condition properly
• Misusing queue operations

5. You have an unweighted graph with 5 nodes and edges: 0-1, 0-2, 1-3, 2-3, 3-4. Using BFS from node 0, what is the shortest path distance to node 4? Also, which nodes are on one shortest path from 0 to 4?

hard

A. Distance: 2; Path: 0 -> 1 -> 3 -> 4

B. Distance: 3; Path: 0 -> 2 -> 3 -> 4

C. Distance: 2; Path: 0 -> 3 -> 4

D. Distance: 4; Path: 0 -> 2 -> 3 -> 4

Solution

1. Step 1: Build graph and run BFS from node 0

   Edges: 0-1,0-2; 1-3; 2-3; 3-4. BFS levels: 0(dist=0), 1 and 2(dist=1), 3(dist=2), 4(dist=3).

2. Step 2: Identify shortest path to node 4

   Shortest distance to 4 is 3. Paths: 0->1->3->4 or 0->2->3->4. Distance: 3; Path: 0 -> 2 -> 3 -> 4 shows correct distance and one valid path.

3. Final Answer:

   Distance: 3; Path: 0 -> 2 -> 3 -> 4 -> Option B

4. Quick Check:

   Shortest path length = 3 via node 2 [OK]

Hint: Trace BFS levels to find shortest path and distance [OK]

Common Mistakes:

• Assuming direct edge from 0 to 3
• Confusing distance with number of edges
• Ignoring multiple shortest paths