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

void bfs_shortest_path(int graph[][5], int n, int src, int dest) {
  int visited[5] = {0};
  int dist[5];
  int parent[5];
  int INF = 999;
  for(int i = 0; i < n; i++) {
    dist[i] = INF;
    parent[i] = -1;
  }
  dist[src] = 0;
  int q[5];
  int front = 0;
  int rear = -1;
  q[++rear] = src;
  visited[src] = 1;
  while(front <= rear) {
    int u = q[front++];
    for(int v = 0; v < n; v++) {
      if(graph[u][v] && !visited[v]) {
        visited[v] = 1;
        dist[v] = dist[u] + 1;
        parent[v] = u;
        q[++rear] = v;
      }
    }
  }
  // TODO: Reconstruct path from src to dest using parent array
}

This code runs BFS on an unweighted graph to find the shortest path from src to dest.

Execution Table

Step	Operation	Current Node	Queue State	Visited Nodes	Distance Array	Parent Array	Visual State
1	Initialize	-	[0]	[0,0,0,0,0]	[0,∞,∞,∞,∞]	[-1,-1,-1,-1,-1]	Start with source node 0 in queue
2	Dequeue	0	[]	[1,0,0,0,0]	[0,∞,∞,∞,∞]	[-1,-1,-1,-1,-1]	Visit node 0
3	Visit neighbors of 0	0	[1,3]	[1,1,0,1,0]	[0,1,∞,1,∞]	[-1,0,-1,0,-1]	Neighbors 1 and 3 enqueued
4	Dequeue	1	[3]	[1,1,0,1,0]	[0,1,∞,1,∞]	[-1,0,-1,0,-1]	Visit node 1
5	Visit neighbors of 1	1	[3,2]	[1,1,1,1,0]	[0,1,2,1,∞]	[-1,0,1,0,-1]	Neighbor 2 enqueued
6	Dequeue	3	[2]	[1,1,1,1,0]	[0,1,2,1,∞]	[-1,0,1,0,-1]	Visit node 3
7	Visit neighbors of 3	3	[2,4]	[1,1,1,1,1]	[0,1,2,1,2]	[-1,0,1,0,3]	Neighbor 4 enqueued
8	Dequeue	2	[4]	[1,1,1,1,1]	[0,1,2,1,2]	[-1,0,1,0,3]	Visit node 2
9	Visit neighbors of 2	2	[4]	[1,1,1,1,1]	[0,1,2,1,2]	[-1,0,1,0,3]	No new neighbors to enqueue
10	Dequeue	4	[]	[1,1,1,1,1]	[0,1,2,1,2]	[-1,0,1,0,3]	Visit node 4
11	Visit neighbors of 4	4	[]	[1,1,1,1,1]	[0,1,2,1,2]	[-1,0,1,0,3]	No new neighbors to enqueue
12	Queue empty	-	[]	[1,1,1,1,1]	[0,1,2,1,2]	[-1,0,1,0,3]	BFS complete, shortest paths found

💡 Queue is empty, BFS traversal finished

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 5	After Step 7	Final
visited	[0,0,0,0,0]	[1,0,0,0,0]	[1,1,0,1,0]	[1,1,1,1,0]	[1,1,1,1,1]	[1,1,1,1,1]
dist	[0,∞,∞,∞,∞]	[0,∞,∞,∞,∞]	[0,1,∞,1,∞]	[0,1,2,1,∞]	[0,1,2,1,2]	[0,1,2,1,2]
parent	[-1,-1,-1,-1,-1]	[-1,-1,-1,-1,-1]	[-1,0,-1,0,-1]	[-1,0,1,0,-1]	[-1,0,1,0,3]	[-1,0,1,0,3]
queue	[]	[]	[1,3]	[3,2]	[2,4]	[]

Key Moments - 3 Insights

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

Marking visited when enqueuing (see step 3) prevents adding the same node multiple times to the queue, ensuring BFS explores each node once.

How do we know the distance array holds shortest distances?

Distances are set when first visiting a node (step 3, 5, 7), and BFS explores nodes in order of increasing distance, so first distance set is shortest.

Why do we keep a parent array?

Parent array (step 3, 5, 7) helps reconstruct the shortest path from destination back to source after BFS finishes.

Visual Quiz - 3 Questions

Look at the execution table at step 3, which nodes are added to the queue?

A Nodes 1 and 3

B Nodes 2 and 4

C Node 0 only

D No nodes added

💡 Hint

Check the 'Queue State' and 'Operation' columns at step 3 in the execution table

At which step does the BFS queue become empty?

A Step 10

B Step 12

C Step 8

D Step 5

💡 Hint

Look at the 'Queue State' column and 'exit_note' in the execution table

If node 2 was connected to node 4, how would the queue change after visiting node 2?

A Node 4 would be added to the queue after node 2

B Node 4 would be added to the queue after node 3

C No change, node 4 is already visited

D Node 2 would be removed from the queue earlier

💡 Hint

Check 'visited' array in variable_tracker after step 7 to see if node 4 is already visited

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 in unweighted graphs
- Reconstruct path using parent array after BFS

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 recording their distance and parent. This process continues until the queue is empty. The distance array holds the shortest distance from the source to each node, and the parent array helps reconstruct the shortest path. Key points include marking nodes visited when enqueued to avoid duplicates and BFS's level-by-level exploration ensuring shortest paths.

Practice

1. What does BFS (Breadth-First Search) help find in an unweighted graph?

easy

A. The total number of nodes in the graph

B. The shortest path from a start node to all other nodes

C. The longest path between two nodes

D. The heaviest edge in the graph

Solution

1. Step 1: Understand BFS traversal

   BFS explores nodes level by level starting from the source node, visiting all neighbors before moving deeper.

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

   Because BFS visits nodes in order of increasing distance, it finds the shortest path in terms of edges from the start node.

3. Final Answer:

   The shortest path from a start node to all other nodes -> Option B

4. Quick Check:

   BFS = shortest path in unweighted graph [OK]

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

Common Mistakes:

• Confusing BFS with DFS for shortest path
• Thinking BFS finds longest path
• Assuming BFS works only for weighted graphs

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

easy

A. int queue[MAX]; int front = 0, rear = 0;

B. queue<int> q; // C++ syntax

C. Queue q = new Queue(); // Java syntax

D. var q = []; // JavaScript syntax

Solution

1. Step 1: Identify C syntax for queue

   C does not have built-in queue; we use arrays with front and rear indices to simulate queue.

2. Step 2: Check options for C correctness

   int queue[MAX]; int front = 0, rear = 0; uses array and indices, which is valid in C. Others use non-C syntax.

3. Final Answer:

   int queue[MAX]; int front = 0, rear = 0; -> Option A

4. Quick Check:

   C queue uses array + front/rear indices [OK]

Hint: Use array with front/rear for queue in C [OK]

Common Mistakes:

• Using C++ or Java syntax in C code
• Not initializing front and rear indices
• Assuming queue is built-in in C

3. What is the output distance array after running BFS from node 0 on this graph?

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

Assume nodes are 0 to 4 and distance to unreachable nodes is -1.

medium

A. [0, 1, 2, 3, 4]

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

C. [0, 1, 1, 2, 3]

D. [0, -1, -1, -1, -1]

Solution

1. Step 1: Start BFS from node 0 and set distance[0] = 0

   Initialize distances: distance[0]=0, others = -1.

2. Step 2: Visit neighbors level-wise

   Neighbors of 0: 1 and 2 get distance 1. Then neighbors of 1 and 2: node 3 gets distance 2. Finally, neighbor of 3: node 4 gets distance 3.

3. Final Answer:

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

4. Quick Check:

   Distances increase by 1 per BFS level [OK]

Hint: Distance increments by 1 each BFS level from start [OK]

Common Mistakes:

• Assigning wrong distances to nodes
• Confusing BFS with DFS order
• Not initializing unreachable nodes to -1

4. Identify the bug in this BFS code snippet for shortest path:

void bfs(int start) {
  queue[rear++] = start;
  visited[start] = 1;
  distance[start] = 0;
  while(front < rear) {
    int u = queue[front++];
    for(int v : adj[u]) {
      if(!visited[v]) {
        visited[v] = 1;
        distance[v] = distance[u] + 1;
        queue[rear++] = v;
      }
    }
  }
}

medium

A. Not marking start node as visited

B. Not initializing distance array before BFS

C. Queue overflow not handled

D. Using 'int v : adj[u]' is invalid in C

Solution

1. Step 1: Check syntax of for loop in C

   Range-based for loops like 'for(int v : adj[u])' are not valid in C; this is C++ syntax.

2. Step 2: Identify correct iteration method in C

   In C, adjacency lists require explicit indexing or pointer iteration, not range-based loops.

3. Final Answer:

   Using 'int v : adj[u]' is invalid in C -> Option D

4. Quick Check:

   Range-based for loops = invalid in C [OK]

Hint: C uses indexed loops, not range-based for [OK]

Common Mistakes:

• Using C++ syntax in C code
• Ignoring queue overflow possibility
• Forgetting to initialize arrays

5. Given an unweighted graph with 6 nodes (0 to 5) and edges:

0-1, 0-2, 1-3, 3-4, 4-5

Write the shortest path from node 0 to node 5 using BFS. What is the path?

hard

A. [0, 1, 3, 4, 5]

B. [0, 2, 3, 4, 5]

C. [0, 1, 2, 3, 4, 5]

D. [0, 5]

Solution

1. Step 1: Run BFS from node 0 to find shortest distances

   Distances: 0(0), 1(1), 2(1), 3(2), 4(3), 5(4). BFS visits neighbors level-wise.

2. Step 2: Trace shortest path from 5 back to 0

   From 5 to 4, 4 to 3, 3 to 1 (via 1-3 edge; no 2-3 edge), 1 to 0.

3. Final Answer:

   [0, 1, 3, 4, 5] -> Option A

4. Quick Check:

   Shortest path = BFS parent chain [OK]

Hint: Trace BFS parents backward for shortest path [OK]

Common Mistakes:

• Choosing longer paths ignoring BFS order
• Assuming direct edge from 0 to 5
• Confusing BFS with DFS path