Shortest Path in Unweighted Graph Using BFS in DSA C++ - Execution Trace

Concept Flow - Shortest Path in Unweighted Graph Using BFS

Start at source node

↓

Initialize queue with source

↓

While queue not empty

↓

Dequeue current node

↓

For each neighbor

↓

If neighbor not visited

↓

Mark visited, set distance, set parent

↓

Enqueue neighbor

↓

Repeat until queue empty

↓

Build shortest path using parent pointers

↓

Done

Start from the source node, explore neighbors level by level using a queue, track distances and parents to find shortest paths.

Execution Sample

DSA C++

graph = {
 0: [1, 2],
 1: [0, 3],
 2: [0, 3],
 3: [1, 2, 4],
 4: [3]
};
// BFS shortest path from 0 to 4

This code finds the shortest path from node 0 to node 4 in an unweighted graph using BFS.

Execution Table

Step	Operation	Current Node	Queue State	Visited Set	Distance Array	Parent Array	Visual State
1	Initialize	-	[0]	{0}	[0, ∞, ∞, ∞, ∞]	[-1, -1, -1, -1, -1]	Start at node 0, queue=[0]
2	Dequeue	0	[]	{0}	[0, ∞, ∞, ∞, ∞]	[-1, -1, -1, -1, -1]	Visit node 0
3	Visit neighbor 1	0	[1]	{0,1}	[0,1, ∞, ∞, ∞]	[-1,0,-1,-1,-1]	Enqueue 1, distance=1, parent=0
4	Visit neighbor 2	0	[1,2]	{0,1,2}	[0,1,1, ∞, ∞]	[-1,0,0,-1,-1]	Enqueue 2, distance=1, parent=0
5	Dequeue	1	[2]	{0,1,2}	[0,1,1, ∞, ∞]	[-1,0,0,-1,-1]	Visit node 1
6	Visit neighbor 3	1	[2,3]	{0,1,2,3}	[0,1,1,2, ∞]	[-1,0,0,1,-1]	Enqueue 3, distance=2, parent=1
7	Dequeue	2	[3]	{0,1,2,3}	[0,1,1,2, ∞]	[-1,0,0,1,-1]	Visit node 2
8	Visit neighbor 3 (already visited)	2	[3]	{0,1,2,3}	[0,1,1,2, ∞]	[-1,0,0,1,-1]	Skip 3, already visited
9	Dequeue	3	[]	{0,1,2,3}	[0,1,1,2, ∞]	[-1,0,0,1,-1]	Visit node 3
10	Visit neighbor 4	3	[4]	{0,1,2,3,4}	[0,1,1,2,3]	[-1,0,0,1,3]	Enqueue 4, distance=3, parent=3
11	Dequeue	4	[]	{0,1,2,3,4}	[0,1,1,2,3]	[-1,0,0,1,3]	Visit node 4 - target reached
12	Build path	-	-	-	-	-	Path: 0 -> 1 -> 3 -> 4
13	End	-	-	-	-	-	Queue empty, BFS complete

💡 Queue is empty, all reachable nodes visited, shortest path found

Variable Tracker

Variable	Start	After Step 1	After Step 4	After Step 6	After Step 10	Final
Queue	[]	[0]	[1,2]	[2,3]	[4]	[]
Visited Set	{}	{0}	{0,1,2}	{0,1,2,3}	{0,1,2,3,4}	{0,1,2,3,4}
Distance	[∞,∞,∞,∞,∞]	[0,∞,∞,∞,∞]	[0,1,1,∞,∞]	[0,1,1,2,∞]	[0,1,1,2,3]	[0,1,1,2,3]
Parent	[-1,-1,-1,-1,-1]	[-1,-1,-1,-1,-1]	[-1,0,0,-1,-1]	[-1,0,0,1,-1]	[-1,0,0,1,3]	[-1,0,0,1,3]

Key Moments - 3 Insights

Why do we mark a node as visited when we enqueue it, not when we dequeue it?

Marking visited when enqueuing (see steps 3 and 4) prevents adding the same node multiple times to the queue, avoiding repeated processing and infinite loops.

Why do we use a parent array in BFS?

The parent array (updated in steps 3, 4, 6, 10) helps reconstruct the shortest path after BFS finishes by tracing back from the target node to the source.

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

Because BFS explores nodes level by level (distance increments by 1 each level), the first time we reach a node is via the shortest path, as shown by the increasing distance values in the Distance array.

Visual Quiz - 3 Questions

Look at the execution table at step 6. What is the distance value assigned to node 3?

A 2

B 1

C 3

D ∞

💡 Hint

Check the Distance Array column at step 6 in the execution table.

At which step does the queue become empty, ending the BFS?

A Step 11

B Step 12

C Step 13

D Step 10

💡 Hint

Look at the Queue State column and the exit note in the execution table.

If we did not mark nodes as visited when enqueuing, what would happen to the queue at step 8?

A Node 4 would be enqueued earlier

B Node 3 would be enqueued again, causing duplicates

C Queue would be empty

D No change in queue

💡 Hint

Refer to step 8 where neighbor 3 is already visited and skipped.

Concept Snapshot

Shortest Path in Unweighted Graph Using BFS:
- Use a queue to explore nodes level by level
- Mark nodes visited when enqueued to avoid repeats
- Track distance and parent for each node
- BFS guarantees shortest path by first visit
- Reconstruct path from target to source using parents

Full Transcript

This visualization shows how BFS finds the shortest path in an unweighted graph. We start from the source node, add it to a queue, and mark it visited. Then, we repeatedly dequeue nodes, visit their neighbors, and enqueue unvisited neighbors while marking them visited and recording their distance and parent. This process continues until the queue is empty or the target node is reached. The parent array helps reconstruct the shortest path by tracing back from the target to the source. BFS explores nodes in layers, ensuring the first time a node is visited is via the shortest path. The execution table tracks each step, queue state, visited nodes, distances, and parents, showing the graph's state changes clearly.

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