Connected Components Using BFS in DSA C++

Mental Model

We find groups of nodes where each node can reach every other node in the same group by walking through edges. BFS helps explore each group fully before moving to the next.

Analogy: Imagine a party where people hold hands forming groups. BFS is like starting from one person and walking through their hand-holding friends until you find everyone in that group before moving to another group.

Graph:
0 -> 1
↑    ↓
2    3

Groups:
Group 1: 0 -> 1 -> 3 -> 2
Group 2: 4

0 -> 1 -> 3 -> 2 -> null
4 -> null

Dry Run Walkthrough

Input: Graph with edges: 0-1, 1-3, 3-2, and isolated node 4

Goal: Identify all connected groups of nodes using BFS

Step 1: Start BFS from node 0, mark it visited and add to queue

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

Why: We begin exploring from node 0 to find its connected group

Step 2: Dequeue 0, enqueue its neighbor 1, mark visited

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

Why: Explore neighbors of 0 to find all connected nodes

Step 3: Dequeue 1, enqueue neighbor 3, mark visited

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

Why: Continue BFS to include all reachable nodes

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

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

Why: Continue BFS to include all reachable nodes

Step 5: Dequeue 2, no new neighbors to add

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

Why: Finished exploring first connected component

Step 6: Start BFS from node 4 (unvisited), mark visited and add to queue

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

Why: Find next connected component starting from unvisited node

Step 7: Dequeue 4, no neighbors to add

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

Why: Isolated node forms its own connected component

Result:

Connected Components:
Component 1: 0 -> 1 -> 3 -> 2 -> null
Component 2: 4 -> null

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class Graph {
public:
    int V;
    vector<vector<int>> adj;

    Graph(int vertices) {
        V = vertices;
        adj.resize(V);
    }

    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u); // undirected graph
    }

    void BFS(int start, vector<bool>& visited, vector<int>& component) {
        queue<int> q;
        q.push(start);
        visited[start] = true; // mark start visited

        while (!q.empty()) {
            int node = q.front();
            q.pop();
            component.push_back(node); // add node to current component

            for (int neighbor : adj[node]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true; // mark neighbor visited
                    q.push(neighbor); // enqueue neighbor
                }
            }
        }
    }

    vector<vector<int>> connectedComponents() {
        vector<bool> visited(V, false);
        vector<vector<int>> components;

        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                vector<int> component;
                BFS(i, visited, component); // find one component
                components.push_back(component); // store it
            }
        }
        return components;
    }
};

int main() {
    Graph g(5);
    g.addEdge(0, 1);
    g.addEdge(1, 3);
    g.addEdge(3, 2);

    vector<vector<int>> comps = g.connectedComponents();

    for (int i = 0; i < comps.size(); i++) {
        cout << "Component " << i + 1 << ": ";
        for (int node : comps[i]) {
            cout << node << " -> ";
        }
        cout << "null" << endl;
    }
    return 0;
}

visited[start] = true; // mark start visited

mark the starting node as visited to avoid revisiting

int node = q.front(); q.pop(); component.push_back(node);

process current node and add it to the current connected component

for (int neighbor : adj[node]) { if (!visited[neighbor]) { visited[neighbor] = true; q.push(neighbor); } }

enqueue all unvisited neighbors to explore the full component

for (int i = 0; i < V; i++) { if (!visited[i]) { BFS(i, visited, component); components.push_back(component); } }

iterate all nodes to find all connected components

Output

Component 1: 0 -> 1 -> 3 -> 2 -> null

Component 2: 4 -> null

Complexity Analysis

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

Space: O(V) for the visited array and queue used in BFS

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

Edge Cases

Graph with no edges (all nodes isolated)

Each node forms its own connected component

DSA C++

if (!visited[i]) { BFS(i, visited, component); components.push_back(component); }

Graph with a single node

One connected component containing that single node

DSA C++

if (!visited[i]) { BFS(i, visited, component); components.push_back(component); }

Graph with all nodes connected

Only one connected component containing all nodes

DSA C++

if (!visited[i]) { BFS(i, visited, component); components.push_back(component); }

When to Use This Pattern

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

Common Mistakes

Mistake: Not marking nodes as visited before enqueueing them
Fix: Mark nodes as visited immediately when enqueueing to avoid duplicates in the queue

Mistake: Only running BFS from node 0 and missing other components
Fix: Run BFS from every unvisited node to find all connected components

Summary

Finds all groups of connected nodes in an undirected graph using BFS.

Use when you want to identify separate connected parts of a graph.

The key is to explore all reachable nodes from a start node before moving to the next unvisited node.

Practice

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

easy

A. The total number of edges in the graph

B. The shortest path between two nodes only

C. The maximum degree of any node in the graph

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

Solution

1. Step 1: Understand BFS traversal in undirected graph

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

2. Step 2: Connect BFS to connected components

   All nodes visited during BFS from a start node belong to the same connected component.

3. Final Answer:

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

4. Quick Check:

   BFS finds connected components = All nodes reachable from a starting node forming one connected component [OK]

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

Common Mistakes:

• Confusing BFS with shortest path only
• Thinking BFS counts edges
• Mixing connected components with node degrees

2. Which of the following is the correct way to mark a node as visited in BFS when using a vector<bool> visited in C++?

easy

A. visited[node] = true;

B. visited.push_back(node);

C. visited.insert(node);

D. visited[node] == true;

Solution

1. Step 1: Understand vector<bool> usage for visited nodes

   visited is a boolean vector indexed by node number; marking visited means setting visited[node] to true.

2. Step 2: Identify correct syntax for assignment

   Assigning true to visited[node] is done by visited[node] = true; other options are invalid or comparisons.

3. Final Answer:

   visited[node] = true; -> Option A

4. Quick Check:

   Mark visited with assignment = visited[node] = true; [OK]

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

Common Mistakes:

• Using == instead of = for assignment
• Trying to push_back in a fixed-size vector
• Using insert which is for sets, not vectors

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

int n = 5;
vector adj = {{1}, {0, 2}, {1}, {4}, {3}};
vector<bool> visited(n, false);
int count = 0;
for (int i = 0; i < n; i++) {
  if (!visited[i]) {
    queue<int> q;
    q.push(i);
    visited[i] = true;
    while (!q.empty()) {
      int u = q.front(); q.pop();
      for (int v : adj[u]) {
        if (!visited[v]) {
          visited[v] = true;
          q.push(v);
        }
      }
    }
    count++;
  }
}
cout << count << endl;

medium

A. 1

B. 2

C. 3

D. 4

Solution

1. Step 1: Analyze the graph adjacency list

   Nodes 0,1,2 form one connected component (0 connected to 1, 1 connected to 2). Nodes 3 and 4 form another connected component (3 connected to 4).

2. Step 2: Trace BFS and count connected components

   Start BFS at node 0: visits 0,1,2 (component 1). Next unvisited node is 3: visits 3,4 (component 2). Total components = 2.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Two connected groups = 2 [OK]

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

Common Mistakes:

• Counting edges instead of components
• Not marking visited correctly causing overcount
• Misreading adjacency list connections

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

int count = 0;
for (int i = 0; i < n; i++) {
  if (visited[i]) {
    queue<int> q;
    q.push(i);
    visited[i] = true;
    while (!q.empty()) {
      int u = q.front(); q.pop();
      for (int v : adj[u]) {
        if (!visited[v]) {
          visited[v] = true;
          q.push(v);
        }
      }
    }
    count++;
}

medium

A. The condition should be if (!visited[i]) instead of if (visited[i])

B. visited[i] should be set to false before pushing to queue

C. Queue should be declared outside the for loop

D. count++ should be inside the inner while loop

Solution

1. Step 1: Check the condition to start BFS

   The BFS should start only from unvisited nodes, so the condition must be if (!visited[i]). The code incorrectly starts BFS from visited nodes.

2. Step 2: Understand impact of wrong condition

   Starting BFS from visited nodes means some components won't be counted, causing incorrect count.

3. Final Answer:

   The condition should be if (!visited[i]) instead of if (visited[i]) -> Option A

4. Quick Check:

   Start BFS on unvisited nodes = The condition should be if (!visited[i]) instead of if (visited[i]) [OK]

Hint: Start BFS only if node is not visited [OK]

Common Mistakes:

• Starting BFS on visited nodes
• Misplacing count increment inside loop
• Incorrect queue scope causing logic errors

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 correct order of BFS starting nodes and the total number of connected components?

hard

A. Start nodes: 0, 1, 3, 5; Total components: 4

B. Start nodes: 0, 2, 4; Total components: 4

C. Start nodes: 0, 3, 5; Total components: 3

D. Start nodes: 1, 3, 5; Total components: 2

Solution

1. Step 1: Identify connected components from edges

   Edges connect nodes into groups: {0,1,2}, {3,4}, {5,6} forming 3 components.

2. Step 2: Determine BFS start nodes

   BFS starts from the smallest unvisited node in each component: 0 for first, 3 for second, 5 for third.

3. Final Answer:

   Start nodes: 0, 3, 5; Total components: 3 -> Option C

4. Quick Check:

   3 components starting at 0,3,5 = Start nodes: 0, 3, 5; Total components: 3 [OK]

Hint: Start BFS at smallest unvisited node per component [OK]

Common Mistakes:

• Counting wrong number of components
• Starting BFS at nodes inside components instead of smallest
• Confusing edges with components count