Connected Components Using BFS in DSA C

Mental Model

We find groups of nodes where each node can reach any other node in the same group by walking through edges. BFS helps explore all nodes connected to a starting node.

Analogy: Imagine a group of friends at a party. If you start talking to one friend and then meet all their friends, and their friends' friends, you find one connected group. BFS is like spreading the conversation to find everyone in that group.

Graph:
0 -> 1
|
2

3 -> 4

Connected components:
Component 1: 0 -> 1 -> 2
Component 2: 3 -> 4

Dry Run Walkthrough

Input: Graph with edges: 0-1, 0-2, 3-4; nodes = 5

Goal: Identify all connected components using BFS

Step 1: Start BFS from node 0, mark 0 visited

Queue: [0]
Visited: [0]
Components found: []

Why: We start exploring from the first unvisited node to find its connected component

Step 2: Dequeue 0, enqueue neighbors 1 and 2, mark visited

Queue: [1, 2]
Visited: [0,1,2]
Components found: []

Why: Explore all nodes connected to 0

Step 3: Dequeue 1, no new neighbors to enqueue

Queue: [2]
Visited: [0,1,2]
Components found: []

Why: 1's neighbors are already visited

Step 4: Dequeue 2, no new neighbors to enqueue

Queue: []
Visited: [0,1,2]
Components found: []

Why: 2's neighbors are already visited

Step 5: BFS ends for component starting at 0; record component {0,1,2}

Components found: [{0,1,2}]

Why: All nodes connected to 0 are found

Step 6: Next unvisited node is 3; start BFS from 3, mark visited

Queue: [3]
Visited: [0,1,2,3]
Components found: [{0,1,2}]

Why: Find next connected component

Step 7: Dequeue 3, enqueue neighbor 4, mark visited

Queue: [4]
Visited: [0,1,2,3,4]
Components found: [{0,1,2}]

Why: Explore nodes connected to 3

Step 8: Dequeue 4, no new neighbors

Queue: []
Visited: [0,1,2,3,4]
Components found: [{0,1,2}]

Why: 4's neighbors are already visited

Step 9: BFS ends for component starting at 3; record component {3,4}

Components found: [{0,1,2}, {3,4}]

Why: All nodes connected to 3 are found

Result:

Components found:
Component 1: 0 -> 1 -> 2
Component 2: 3 -> 4

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

#define MAX_NODES 100

// Queue structure for BFS
typedef struct {
    int items[MAX_NODES];
    int front;
    int rear;
} Queue;

void initQueue(Queue* q) {
    q->front = -1;
    q->rear = -1;
}

int isEmpty(Queue* q) {
    return q->front == -1;
}

void enqueue(Queue* q, int value) {
    if (q->rear == MAX_NODES - 1) return; // Queue full
    if (q->front == -1) q->front = 0;
    q->rear++;
    q->items[q->rear] = value;
}

int dequeue(Queue* q) {
    if (isEmpty(q)) return -1;
    int item = q->items[q->front];
    if (q->front >= q->rear) {
        q->front = -1;
        q->rear = -1;
    } else {
        q->front++;
    }
    return item;
}

// BFS to find connected component starting from start_node
void bfs(int graph[MAX_NODES][MAX_NODES], int n, int start_node, int visited[MAX_NODES]) {
    Queue q;
    initQueue(&q);
    enqueue(&q, start_node);
    visited[start_node] = 1;
    printf("Component nodes: ");

    while (!isEmpty(&q)) {
        int current = dequeue(&q); // dequeue current node
        printf("%d ", current);

        for (int i = 0; i < n; i++) {
            if (graph[current][i] == 1 && !visited[i]) {
                enqueue(&q, i); // enqueue neighbor
                visited[i] = 1; // mark visited
            }
        }
    }
    printf("\n");
}

int main() {
    int n = 5;
    int graph[MAX_NODES][MAX_NODES] = {0};

    // Edges: 0-1, 0-2, 3-4
    graph[0][1] = 1; graph[1][0] = 1;
    graph[0][2] = 1; graph[2][0] = 1;
    graph[3][4] = 1; graph[4][3] = 1;

    int visited[MAX_NODES] = {0};

    printf("Connected Components:\n");
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            bfs(graph, n, i, visited); // find component
        }
    }

    return 0;
}

enqueue(&q, start_node); visited[start_node] = 1;

start BFS from start_node and mark it visited

int current = dequeue(&q);

dequeue current node to explore its neighbors

if (graph[current][i] == 1 && !visited[i]) { enqueue(&q, i); visited[i] = 1; }

enqueue unvisited neighbors and mark them visited

for (int i = 0; i < n; i++) { if (!visited[i]) { bfs(graph, n, i, visited); } }

iterate all nodes to find unvisited nodes and run BFS to find components

Output

Connected Components:

Component nodes: 0 1 2 

Component nodes: 3 4 

Complexity Analysis

Time: O(V + E) because BFS visits every vertex and edge once

Space: O(V) for the visited array and queue to store nodes during BFS

vs Alternative: Compared to DFS, BFS has similar time and space complexity but explores neighbors level by level

Edge Cases

Empty graph (no nodes)

No components found, BFS never runs

DSA C

for (int i = 0; i < n; i++) { if (!visited[i]) { bfs(...); } }

Graph with single node and no edges

One component with single node is found

DSA C

enqueue(&q, start_node); visited[start_node] = 1;

Graph with all nodes disconnected

Each node forms its own component

DSA C

for (int i = 0; i < n; i++) { if (!visited[i]) { bfs(...); } }

When to Use This Pattern

When you need to find groups of connected nodes in a graph, use BFS to explore each group fully before moving to the next.

Common Mistakes

Mistake: Not marking nodes as visited when enqueued, causing repeated visits
Fix: Mark nodes visited immediately when enqueued to avoid duplicates

Mistake: Starting BFS from all nodes without checking visited, causing repeated components
Fix: Check if node is visited before starting BFS

Summary

Finds all connected groups of nodes in a graph using BFS.

Use when you want to identify separate connected parts in an undirected graph.

Start BFS from unvisited nodes to explore and mark all nodes in that connected component.

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