BFS Breadth First Search on Graph in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the queue front index.

DSA C

int front = [1];

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

A1

B0

C-1

DNULL

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing front to -1 causes invalid array access like queue[front].

Using NULL is invalid for integer index.

The queue front index is initialized to 0 (with rear typically -1) to indicate the queue is empty.

2fill in blank

medium

Complete the code to enqueue a vertex into the queue.

DSA C

queue[++rear] = [1];

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

Avertex

Bvisited

Cadjacency

Dfront

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'visited' instead of vertex causes wrong data in queue.

Using 'front' or 'adjacency' is incorrect for enqueue operation.

We enqueue the current vertex by placing it at the rear of the queue.

3fill in blank

medium

Fix the error in the BFS loop condition to continue while queue is not empty.

DSA C

while (front [1] rear) {

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

A<

B>

C==

D<=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' misses the last element in the queue.

Using '==' only runs once and stops prematurely.

The loop continues while front is less than or equal to rear, meaning queue has elements.

4fill in blank

hard

Fill both blanks to mark a vertex as visited and enqueue it.

DSA C

if (!visited[adjacency[i]]) {
    visited[adjacency[i]] = [1];
    queue[++rear] = [2];
}

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

A1

B0

Cadjacency[i]

Di

Attempts:

3 left

💡 Hint

Common Mistakes

Setting visited to 0 means not visited.

Enqueueing 'i' instead of adjacency[i] adds wrong vertex.

Mark the adjacency vertex as visited by setting 1, then enqueue that vertex.

5fill in blank

hard

Fill all three blanks to print the BFS traversal order.

DSA C

for (int i = [1]; i [2] [3]; i++) {
    printf("%d ", queue[i]);
}

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

Afront

B<

Crear + 1

Drear

Attempts:

3 left

💡 Hint

Common Mistakes

Starting from front + 1 skips first element.

Using '<=' with rear + 1 causes out-of-bound access.

Start from front, go while i < rear + 1 to print all elements in queue.

Practice

1. What does BFS (Breadth First Search) primarily use to keep track of nodes to visit next in a graph?

easy

A. A queue to explore nodes level by level

B. A stack to explore nodes deeply first

C. A hash map to store visited nodes only

D. A priority queue to explore nodes by weight

Solution

1. Step 1: Understand BFS traversal method

   BFS explores nodes in layers, visiting all neighbors before going deeper.

2. Step 2: Identify the data structure used

   To achieve level-by-level traversal, BFS uses a queue to store nodes to visit next.

3. Final Answer:

   A queue to explore nodes level by level -> Option A

4. Quick Check:

   BFS uses queue = A [OK]

Hint: BFS uses a queue, DFS uses a stack [OK]

Common Mistakes:

• Confusing BFS with DFS and choosing stack
• Thinking BFS uses priority queue for weights
• Ignoring the need for a data structure to track nodes

2. Which of the following is the correct way to enqueue a node `v` in a BFS implementation using C?

easy

A. queue.push(v);

B. queue.insert(v);

C. queue.add(v);

D. enqueue(queue, v);

Solution

1. Step 1: Recognize C queue operation syntax

   In C, queues are usually implemented with functions like enqueue(queue, value).

2. Step 2: Identify correct enqueue function call

   queue.push and queue.add are not standard C; enqueue(queue, v) is typical.

3. Final Answer:

   enqueue(queue, v); -> Option D

4. Quick Check:

   Use enqueue(queue, v) in C [OK]

Hint: C uses enqueue(queue, value) for queues [OK]

Common Mistakes:

• Using push or add which are not C queue functions
• Confusing queue insertion with array insertion
• Using incorrect method names from other languages

3. Consider the following graph represented as adjacency list:

0: 1, 2
1: 0, 3
2: 0, 3
3: 1, 2

If BFS starts from node 0, what is the order of nodes visited?

medium

A. [0, 2, 1, 3]

B. [0, 1, 2, 3]

C. [0, 3, 1, 2]

D. [0, 1, 3, 2]

Solution

1. Step 1: Start BFS from node 0

   Visit 0, enqueue neighbors 1 and 2.

2. Step 2: Visit nodes in queue order

   Dequeue 1, enqueue its unvisited neighbor 3; then dequeue 2, neighbor 3 already visited.

3. Step 3: Visit remaining node 3

   Dequeue 3, no new neighbors.

4. Final Answer:

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

5. Quick Check:

   BFS order = [0, 1, 2, 3] [OK]

Hint: BFS visits neighbors in queue order [OK]

Common Mistakes:

• Visiting nodes in DFS order instead
• Mixing neighbor order causing wrong sequence
• Not marking visited nodes causing repeats

4. The following BFS code snippet has a bug. What is the error?

void bfs(int start, int n, int adj[][n]) {
  int visited[n];
  for(int i=0; i<n; i++) visited[i] = 0;
  int queue[n], front=0, rear=0;
  queue[rear++] = start;
  visited[start] = 1;
  while(front < rear) {
    int u = queue[front++];
    printf("%d ", u);
    for(int v=0; v<n; v++) {
      if(adj[u][v] == 1 && visited[v] == 0) {
        queue[rear++] = v;
        // Missing visited mark here
      }
    }
  }
}

medium

A. Visited array is not initialized

B. Queue overflow not checked

C. Visited mark missing inside neighbor loop

D. Start node not enqueued

Solution

1. Step 1: Check visited array initialization

   Visited array is initialized to 0 for all nodes, so no issue here.

2. Step 2: Inspect neighbor loop for visited marking

   Inside the neighbor loop, nodes are enqueued but visited[v] is not set to 1, causing repeated visits.

3. Step 3: Confirm other options

   Queue overflow is not handled but not the main bug; start node is enqueued correctly.

4. Final Answer:

   Visited mark missing inside neighbor loop -> Option C

5. Quick Check:

   Mark visited when enqueueing neighbors [OK]

Hint: Always mark visited when enqueueing nodes [OK]

Common Mistakes:

• Forgetting to mark visited inside neighbor loop
• Assuming initialization fixes all visited issues
• Ignoring queue overflow but it's not main bug

5. Given a graph with nodes 0 to 4 and edges: 0-1, 0-2, 1-3, 2-3, 3-4. Using BFS starting at node 0, which node is visited at the 3rd step (0-based index)?

hard

A. 2

B. 3

C. 1

D. 4

Solution

1. Step 1: List BFS order from node 0

   Start at 0, enqueue neighbors 1 and 2. Visit order so far: [0]

2. Step 2: Visit nodes in queue order

   Visit 1 (step 1), enqueue neighbor 3; visit 2 (step 2), neighbor 3 already enqueued.

3. Step 3: Visit node 2 (step 3)

   Next node dequeued is 2, which is the 3rd step (0-based index).

4. Final Answer:

   2 -> Option A

5. Quick Check:

   BFS step 3 node = 2 [OK]

Hint: Track BFS queue order stepwise [OK]

Common Mistakes:

• Counting steps starting at 1 instead of 0
• Visiting neighbors out of enqueue order
• Forgetting node 3 is enqueued twice but visited once