Connected Components Using BFS in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of BFS Connected Components Count

What is the output of the following C code that counts connected components using BFS on an undirected graph?

DSA C

#include <stdio.h>
#include <stdlib.h>
#define MAX 5

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

int visited[MAX] = {0};

void bfs(int start) {
    int queue[MAX], front = 0, rear = 0;
    queue[rear++] = start;
    visited[start] = 1;
    while(front < rear) {
        int node = queue[front++];
        for(int i = 0; i < MAX; i++) {
            if(graph[node][i] == 1 && !visited[i]) {
                visited[i] = 1;
                queue[rear++] = i;
            }
        }
    }
}

int main() {
    int count = 0;
    for(int i = 0; i < MAX; i++) {
        if(!visited[i]) {
            bfs(i);
            count++;
        }
    }
    printf("%d\n", count);
    return 0;
}

A 2

B 0

C 3

D 1

💡 Hint

Count how many times BFS starts from an unvisited node.

The graph has two connected components: nodes 0-1-2 and nodes 3-4. BFS runs twice, so output is 2.

🧠 Conceptual

intermediate

Understanding BFS Queue Behavior in Connected Components

In BFS for connected components, what is the role of the queue?

A It stores nodes to visit next in FIFO order.

B It stores only the starting node of BFS.

C It stores all nodes in the graph at once.

D It stores nodes already visited to avoid repetition.

💡 Hint

Think about how BFS explores neighbors level by level.

The queue holds nodes discovered but not yet explored, ensuring BFS visits nodes in order of distance from start.

🔧 Debug

advanced

Identify the Bug in BFS Connected Components Code

What error will occur when running this BFS connected components code snippet?

DSA C

#include <stdio.h>
#define MAX 4

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

int visited[MAX] = {0};

void bfs(int start) {
    int queue[MAX], front = 0, rear = 0;
    queue[rear++] = start;
    visited[start] = 1;
    while(front <= rear) {
        int node = queue[front++];
        for(int i = 0; i < MAX; i++) {
            if(graph[node][i] == 1 && !visited[i]) {
                visited[i] = 1;
                queue[rear++] = i;
            }
        }
    }
}

int main() {
    int count = 0;
    for(int i = 0; i < MAX; i++) {
        if(!visited[i]) {
            bfs(i);
            count++;
        }
    }
    printf("%d\n", count);
    return 0;
}

A Infinite loop because front never increments

B No output because visited array is never updated

C Array index out of bounds due to incorrect queue condition

D Compilation error due to missing semicolon

💡 Hint

Check the while loop condition controlling queue processing.

The condition 'front <= rear' allows front to equal rear, causing queue[rear] access which is invalid. It should be 'front < rear'.

🚀 Application

advanced

Number of Connected Components After Adding an Edge

Given a graph with 3 connected components, if you add an edge connecting two nodes from different components, what happens to the number of connected components?

A It becomes zero

B It increases by 1

C It stays the same

D It decreases by 1

💡 Hint

Connecting two separate groups merges them into one.

Adding an edge between two different components merges them, reducing total components by one.

❓ Predict Output

expert

Output of BFS Connected Components with Disconnected Single Node

What is the output of this C code counting connected components using BFS on a graph with one isolated node?

DSA C

#include <stdio.h>
#define MAX 6

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

int visited[MAX] = {0};

void bfs(int start) {
    int queue[MAX], front = 0, rear = 0;
    queue[rear++] = start;
    visited[start] = 1;
    while(front < rear) {
        int node = queue[front++];
        for(int i = 0; i < MAX; i++) {
            if(graph[node][i] == 1 && !visited[i]) {
                visited[i] = 1;
                queue[rear++] = i;
            }
        }
    }
}

int main() {
    int count = 0;
    for(int i = 0; i < MAX; i++) {
        if(!visited[i]) {
            bfs(i);
            count++;
        }
    }
    printf("%d\n", count);
    return 0;
}

A 2

B 3

C 1

D 4

💡 Hint

Count connected groups including isolated nodes.

There are three connected components: nodes 0-1-2, nodes 3-4, and isolated node 5 alone.