Shortest Path in Unweighted Graph Using BFS in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does BFS stand for and what is its main use in graphs?

BFS stands for Breadth-First Search. It is used to explore nodes level by level and find the shortest path in an unweighted graph.

beginner

Why is BFS suitable for finding the shortest path in an unweighted graph?

Because BFS explores neighbors in layers, the first time it reaches a node, it has found the shortest path to that node.

beginner

In BFS for shortest path, what data structure is commonly used to keep track of nodes to visit next?

A queue is used to keep track of nodes to visit in the order they are discovered.

intermediate

What additional information do we store during BFS to reconstruct the shortest path?

We store the parent (or predecessor) of each node to trace back the path from the destination to the source.

intermediate

What is the time complexity of BFS when finding the shortest path in an unweighted graph?

The time complexity is O(V + E), where V is the number of vertices and E is the number of edges.

What data structure does BFS use to explore nodes?

A Queue

B Stack

C Priority Queue

D Hash Map

BFS uses a queue to explore nodes in the order they are discovered.

Why can BFS find the shortest path in an unweighted graph?

A It uses weights to calculate shortest path

B It explores nodes randomly

C It explores nodes in increasing order of distance from the source

D It uses recursion

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

What do we store to reconstruct the shortest path after BFS?

A Distance only

B All paths

C Visited nodes only

D Parent of each node

Storing the parent of each node allows us to trace back the shortest path.

What is the initial distance to the source node in BFS shortest path?

A 0

B 1

C Infinity

D -1

The source node distance is set to 0 because it is the starting point.

What is the time complexity of BFS in terms of vertices (V) and edges (E)?

A O(V^2)

B O(V + E)

C O(E^2)

D O(log V)

BFS visits each vertex and edge once, so the complexity is O(V + E).

Explain how BFS finds the shortest path in an unweighted graph.

Think about how BFS visits nodes in layers and how that helps find shortest paths.

Describe the steps to reconstruct the shortest path after running BFS.

Focus on how to use parent information to get the path.

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