BFS Breadth First Search on Graph in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of BFS traversal on a simple graph

What is the output of the BFS traversal starting from node 0 in the given graph?

DSA C

/* Graph adjacency list representation:
   0: 1, 2
   1: 0, 3
   2: 0, 4
   3: 1
   4: 2
*/

void bfs(int start, int graph[][5], int n) {
    int queue[10], front = 0, rear = 0;
    int visited[5] = {0};
    queue[rear++] = start;
    visited[start] = 1;

    while (front < rear) {
        int node = queue[front++];
        printf("%d ", node);
        for (int i = 0; i < n; i++) {
            if (graph[node][i] == 1 && !visited[i]) {
                queue[rear++] = i;
                visited[i] = 1;
            }
        }
    }
}

int main() {
    int graph[5][5] = {
        {0,1,1,0,0},
        {1,0,0,1,0},
        {1,0,0,0,1},
        {0,1,0,0,0},
        {0,0,1,0,0}
    };
    bfs(0, graph, 5);
    return 0;
}

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

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

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

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

💡 Hint

Remember BFS visits neighbors level by level starting from the start node.

BFS starts at node 0, visits neighbors 1 and 2, then visits neighbors of 1 (which is 3) and neighbors of 2 (which is 4). So the order is 0, 1, 2, 3, 4.

🧠 Conceptual

intermediate

Number of nodes visited in BFS

Given a graph with 6 nodes where node 5 is disconnected, how many nodes will BFS visit starting from node 0?

A 6

B 1

C 4

D 5

💡 Hint

BFS only visits nodes reachable from the start node.

Since node 5 is disconnected, BFS starting at node 0 visits only the 5 connected nodes.

🔧 Debug

advanced

Identify the error in BFS implementation

What error will this BFS code produce when run on a graph with 4 nodes?

DSA C

void bfs(int start, int graph[][4], int n) {
    int queue[10], front = 0, rear = 0;
    int visited[4] = {0};
    queue[rear++] = start;
    visited[start] = 1;

    while (front < rear) {
        int node = queue[front++];
        printf("%d ", node);
        for (int i = 0; i < n; i++) {
            if (graph[node][i] == 1 && !visited[i]) {
                queue[rear++] = i;
                visited[i] = 1;
            }
        }
    }
}

A Runs correctly and prints BFS order

B Runtime error due to accessing queue out of bounds

C Compilation error due to wrong array size

D Infinite loop because front never exceeds rear

💡 Hint

Check the loop condition carefully.

The original loop condition 'front <= rear' causes the loop to run one extra time after the queue is empty, leading to reading invalid data and infinite loop. Changing it to 'front < rear' fixes the issue.

🚀 Application

advanced

Shortest path length using BFS

Using BFS on an unweighted graph, what is the shortest path length from node 0 to node 4?

DSA C

/* Graph adjacency list:
0: 1, 2
1: 3
2: 4
3: 4
4: 
*/

int bfs_shortest_path(int start, int end, int graph[][5], int n) {
    int queue[10], front = 0, rear = 0;
    int visited[5] = {0};
    int distance[5] = {0};
    queue[rear++] = start;
    visited[start] = 1;
    distance[start] = 0;

    while (front < rear) {
        int node = queue[front++];
        if (node == end) return distance[node];
        for (int i = 0; i < n; i++) {
            if (graph[node][i] == 1 && !visited[i]) {
                queue[rear++] = i;
                visited[i] = 1;
                distance[i] = distance[node] + 1;
            }
        }
    }
    return -1;
}

int main() {
    int graph[5][5] = {
        {0,1,1,0,0},
        {0,0,0,1,0},
        {0,0,0,0,1},
        {0,0,0,0,1},
        {0,0,0,0,0}
    };
    int dist = bfs_shortest_path(0, 4, graph, 5);
    printf("%d", dist);
    return 0;
}

A 1

B 3

C 2

D 4

💡 Hint

BFS finds shortest path in unweighted graphs by levels.

Shortest path from 0 to 4 is 0->2->4 or 0->1->3->4 but 0->2->4 is shorter with length 2.

❓ Predict Output

expert

BFS traversal order on a directed graph with cycles

What is the BFS traversal order starting from node 0 on the directed graph below?

DSA C

/* Directed graph adjacency matrix:
0 -> 1, 2
1 -> 2, 3
2 -> 0, 3
3 -> 3
*/

void bfs(int start, int graph[][4], int n) {
    int queue[10], front = 0, rear = 0;
    int visited[4] = {0};
    queue[rear++] = start;
    visited[start] = 1;

    while (front < rear) {
        int node = queue[front++];
        printf("%d ", node);
        for (int i = 0; i < n; i++) {
            if (graph[node][i] == 1 && !visited[i]) {
                queue[rear++] = i;
                visited[i] = 1;
            }
        }
    }
}

int main() {
    int graph[4][4] = {
        {0,1,1,0},
        {0,0,1,1},
        {1,0,0,1},
        {0,0,0,1}
    };
    bfs(0, graph, 4);
    return 0;
}

A [0, 1, 2, 3]

B [0, 2, 1, 3]

C [0, 1, 3, 2]

D [0, 2, 3, 1]

💡 Hint

BFS visits nodes in order of discovery and marks visited to avoid cycles.

Starting at 0, neighbors 1 and 2 are visited. Then from 1, neighbor 3 is visited. Node 2's neighbors are already visited. Node 3 points to itself but is already visited. So order is 0,1,2,3.

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