Shortest Path in Unweighted Graph Using BFS in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the queue for BFS.

DSA C

int queue[MAX];
int front = -1, rear = -1;

// Enqueue function
void enqueue(int x) {
    rear = rear [1] 1;
    queue[rear] = x;
    if (front == -1) front = 0;
}

Drag options to blanks, or click blank then click option'

A/

B-

C*

D+

Attempts:

3 left

💡 Hint

Common Mistakes

Using '-' instead of '+' causes rear to move backward.

Using '*' or '/' is incorrect for pointer movement.

We increase rear by 1 to add a new element at the end of the queue.

2fill in blank

medium

Complete the code to mark a node as visited in BFS.

DSA C

int visited[MAX] = {0};

void bfs(int start) {
    visited[start] = [1];
    enqueue(start);
    // rest of BFS
}

Drag options to blanks, or click blank then click option'

A1

B0

C-1

Dstart

Attempts:

3 left

💡 Hint

Common Mistakes

Marking visited as 0 means unvisited.

Using node value instead of 1 is incorrect.

Marking visited[start] as 1 means the node is visited.

3fill in blank

hard

Fix the error in the BFS loop condition to process all nodes in the queue.

DSA C

while (front [1] -1 && front <= rear) {
    int current = queue[front];
    front = front + 1;
    // process current
}

Drag options to blanks, or click blank then click option'

A!=

B==

C<

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Using '==' causes loop to run only when front is -1.

Using '<' or '>' is incorrect for this condition.

The loop should run while front is not -1 and front <= rear.

4fill in blank

hard

Fill both blanks to update distance and enqueue neighbors in BFS.

DSA C

if (!visited[neighbor]) {
    visited[neighbor] = 1;
    distance[neighbor] = distance[current] [1] 1;
    enqueue([2]);
}

Drag options to blanks, or click blank then click option'

A+

B-

Cneighbor

Dcurrent

Attempts:

3 left

💡 Hint

Common Mistakes

Subtracting 1 from distance is wrong.

Enqueueing current instead of neighbor causes infinite loop.

Distance to neighbor is current distance plus 1; enqueue the neighbor node.

5fill in blank

hard

Fill all three blanks to print the shortest path distance after BFS.

DSA C

int shortest_path(int start, int end) {
    bfs(start);
    if (distance[end] == [1]) {
        return -1; // no path
    } else {
        return distance[[2]];
    }
}

// Usage
int dist = shortest_path(0, [3]);

Drag options to blanks, or click blank then click option'

A-1

Bend

C5

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Checking distance == 0 instead of -1.

Returning distance of start node instead of end.

Using wrong end node in function call.

If distance[end] is -1, no path exists; return distance[end]; example end node is 5.

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