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 distance array after running BFS from node 0 in this unweighted graph?

DSA C

int graph[5][5] = {
  {0, 1, 0, 0, 0},
  {1, 0, 1, 1, 0},
  {0, 1, 0, 0, 1},
  {0, 1, 0, 0, 1},
  {0, 0, 1, 1, 0}
};

int dist[5];
for (int i = 0; i < 5; i++) dist[i] = -1;
dist[0] = 0;

int queue[5], front = 0, rear = 0;
queue[rear++] = 0;

while (front < rear) {
  int u = queue[front++];
  for (int v = 0; v < 5; v++) {
    if (graph[u][v] == 1 && dist[v] == -1) {
      dist[v] = dist[u] + 1;
      queue[rear++] = v;
    }
  }
}

for (int i = 0; i < 5; i++) printf("%d ", dist[i]);

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

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

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

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

💡 Hint

Trace BFS layer by layer starting from node 0.

Starting from node 0 (dist=0), neighbor node 1 (dist=1). From node 1, neighbors 2 (dist=2) and 3 (dist=2). From node 2, node 4 (dist=3). From node 3, node 4 already visited. Distance array: [0, 1, 2, 2, 3].

🧠 Conceptual

intermediate

Why BFS finds shortest path in unweighted graphs?

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

A Because BFS uses a priority queue to select the next node.

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 in which BFS visits nodes.

BFS explores nodes layer by layer, so it visits all nodes at distance d before visiting nodes at distance d+1. This ensures the first time a node is visited, it is via the shortest path.

🔧 Debug

advanced

Identify the bug in BFS shortest path code

What error will this BFS code cause when run on an unweighted graph?

DSA C

int dist[5];
for (int i = 0; i < 5; i++) dist[i] = 0;

int queue[5], front = 0, rear = 0;
queue[rear++] = 0;

dist[0] = 0;

while (front < rear) {
  int u = queue[front++];
  for (int v = 0; v < 5; v++) {
    if (graph[u][v] == 1 && dist[v] == 0) {
      dist[v] = dist[u] + 1;
      queue[rear++] = v;
    }
  }
}

A Infinite loop because nodes are revisited endlessly

B No error, code runs correctly

C Array index out of bounds error

D Compilation error due to missing semicolon

💡 Hint

Check how visited nodes are tracked.

The code uses dist[v] == 0 to check unvisited, but dist[0] == 0. When processing node 1, it treats node 0 as unvisited, reenqueues it (extra entry), causing infinite loop or queue overflow.

❓ Predict Output

advanced

Output of BFS path reconstruction

What is the reconstructed shortest path from node 0 to node 4 after BFS?

DSA C

int parent[5];
for (int i = 0; i < 5; i++) parent[i] = -1;

int dist[5];
for (int i = 0; i < 5; i++) dist[i] = -1;
dist[0] = 0;

int queue[5], front = 0, rear = 0;
queue[rear++] = 0;

while (front < rear) {
  int u = queue[front++];
  for (int v = 0; v < 5; v++) {
    if (graph[u][v] == 1 && dist[v] == -1) {
      dist[v] = dist[u] + 1;
      parent[v] = u;
      queue[rear++] = v;
    }
  }
}

int path[5];
int count = 0;
for (int v = 4; v != -1; v = parent[v]) {
  path[count++] = v;
}

for (int i = count - 1; i >= 0; i--) printf("%d ", path[i]);

A 0 2 4

B 0 1 2 4

C 0 1 3 4

D 0 3 4

💡 Hint

Trace parent links from node 4 back to 0.

From 0 to 1 (parent[1]=0). From 1, loop v=0..4 discovers 2 before 3, enqueues 2 then 3 (parent[2]=1, parent[3]=1). Dequeues 2 first, sets parent[4]=2. Path: 4<-2<-1<-0 prints 0 1 2 4.

🧠 Conceptual

expert

Time complexity of BFS shortest path in adjacency matrix

What is the time complexity of BFS to find shortest path in an unweighted graph represented by an adjacency matrix of size N x N?

A O(N^2) because BFS checks all possible edges in the matrix

B O(N) because BFS visits each node once

C O(E) where E is number of edges, because BFS visits edges only

D O(log N) because BFS uses a queue

💡 Hint

Consider how adjacency matrix stores edges and how BFS scans neighbors.

In adjacency matrix, BFS checks all N nodes for each node to find neighbors, resulting in O(N^2) time.