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.

Practice

1. What does the BFS algorithm help find in an undirected graph when used to find connected components?

easy

A. All nodes reachable from a starting node forming one connected component

B. The shortest path between two nodes only

C. The number of edges in the graph

D. The degree of each node

Solution

1. Step 1: Understand BFS traversal in undirected graphs

   BFS explores all nodes reachable from a given start node by visiting neighbors level by level.

2. Step 2: Connect BFS to connected components

   By running BFS from an unvisited node, we find all nodes in that node's connected component.

3. Final Answer:

   All nodes reachable from a starting node forming one connected component -> Option A

4. Quick Check:

   BFS finds connected components by exploring reachable nodes [OK]

Hint: BFS visits all nodes in one connected component [OK]

Common Mistakes:

• Thinking BFS only finds shortest paths
• Confusing connected components with edge counts
• Assuming BFS finds node degrees

2. Which of the following is the correct way to mark a node as visited in BFS when using an array named visited and current node u?

easy

A. visited[u] = 0;

B. visited[u] = true;

C. visited[u] == true;

D. visited[u] = null;

Solution

1. Step 1: Understand marking visited nodes

   To mark a node visited, assign true to visited[u], indicating it is visited.

2. Step 2: Check syntax correctness

   Using visited[u] = true; correctly assigns the boolean true. Using == is a comparison, not assignment.

3. Final Answer:

   visited[u] = true; -> Option B

4. Quick Check:

   Assign true to mark visited[u] [OK]

Hint: Use assignment (=), not comparison (==), to mark visited [OK]

Common Mistakes:

• Using == instead of = for assignment
• Assigning 0 instead of true to visited
• Assigning null which is invalid in C

3. Given the following graph adjacency list and BFS code snippet, what is the output number of connected components?

int n = 5;
int adj[5][5] = {
  {0,1,0,0,0},
  {1,0,0,0,0},
  {0,0,0,1,1},
  {0,0,1,0,0},
  {0,0,1,0,0}
};
bool visited[5] = {false};

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

medium

A. 2

B. 1

C. 3

D. 4

Solution

1. Step 1: Analyze adjacency matrix for connected components

   Nodes 0 and 1 are connected; nodes 2, 3, 4 form another connected group.

2. Step 2: Count connected components using BFS

   BFS from node 0 visits nodes 0 and 1; BFS from node 2 visits nodes 2, 3, 4. Total components = 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Two groups found by BFS = 2 [OK]

Hint: Count BFS runs on unvisited nodes for components [OK]

Common Mistakes:

• Counting edges instead of components
• Misreading adjacency matrix connections
• Forgetting to mark visited nodes

4. Identify the bug in this BFS function for counting connected components:

void bfs(int start, int adj[][5], bool visited[], int n) {
  queue<int> q;
  q.push(start);
  visited[start] = true;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int v = 0; v < n; v++) {
      if (adj[u][v] == 1 && visited[v] == false) {
        q.push(v);
      }
    }
  }
}

medium

A. Loop condition should be while(q.size() > 1)

B. Queue is not initialized properly

C. Start node is not marked visited

D. Missing visited[v] = true; inside the loop

Solution

1. Step 1: Check BFS neighbor processing

   When a neighbor v is found unvisited, it must be marked visited immediately to avoid re-adding.

2. Step 2: Identify missing visited mark

   The code pushes v to queue but does not mark visited[v] = true; causing repeated visits.

3. Final Answer:

   Missing visited[v] = true; inside the loop -> Option D

4. Quick Check:

   Mark visited when enqueueing neighbors [OK]

Hint: Mark visited when pushing to queue, not after popping [OK]

Common Mistakes:

• Marking visited only after popping from queue
• Incorrect queue initialization
• Wrong loop condition for BFS

5. You have a graph with 7 nodes and edges: (0-1), (1-2), (3-4), (5-6). Using BFS to find connected components, what is the minimum number of BFS calls needed to find all components?

hard

A. 1

B. 2

C. 3

D. 4

Solution

1. Step 1: Identify connected components from edges

   Edges connect nodes into groups: {0,1,2}, {3,4}, {5,6}. Since nodes are numbered 0 to 6, there are no other nodes.

2. Step 2: Count connected components

   Groups are: {0,1,2}, {3,4}, {5,6} -> 3 components total.

3. Step 3: BFS calls equal connected components

   Each BFS call finds one component, so minimum BFS calls = 3.

4. Final Answer:

   3 -> Option C

5. Quick Check:

   Number of BFS calls = number of connected components [OK]

Hint: Count connected groups; BFS calls = groups [OK]

Common Mistakes:

• Counting edges instead of components
• Miscounting isolated nodes
• Assuming BFS calls equal nodes