Connected Components Using BFS in DSA C++ - Build from Scratch

Connected Components Using BFS

📖 Scenario: Imagine you have a map of cities connected by roads. You want to find groups of cities where each city is reachable from any other city in the same group by traveling along these roads.

🎯 Goal: You will build a program to find all connected groups of cities using Breadth-First Search (BFS).

📋 What You'll Learn

Create an adjacency list to represent the map of cities.

Use a boolean vector to track visited cities.

Implement BFS to explore connected cities.

Find and print all connected components.

💡 Why This Matters

🌍 Real World

Finding connected groups in networks like social media, road maps, or computer networks helps understand clusters and isolate problems.

💼 Career

Graph traversal and connected components are common in software engineering, data analysis, and network security roles.

1

Create the adjacency list for the graph

Create a vector of vectors called graph with 6 elements (for cities 0 to 5). Add edges to represent these connections: 0-1, 0-2, 3-4.

DSA C++

#include 
#include 

int main() {
    // Create adjacency list for 6 cities
    // Your code here
    return 0;
}

Hint

Use std::vector> graph(6); to create the adjacency list. Add edges by pushing neighbors to each city's vector.

2

Create a visited vector to track cities

Create a boolean vector called visited with 6 elements, all initialized to false.

DSA C++

#include 
#include 

int main() {
    std::vector> graph(6);
    graph[0].push_back(1);
    graph[1].push_back(0);
    graph[0].push_back(2);
    graph[2].push_back(0);
    graph[3].push_back(4);
    graph[4].push_back(3);

    // Create visited vector
    // Your code here

    return 0;
}

Hint

Use std::vector visited(6, false); to create the visited vector.

3

Implement BFS to find connected components

Include #include <queue>. Write a function called bfs that takes graph, visited, and a starting city start. Use a queue to visit all connected cities and mark them visited.

DSA C++

#include 
#include 
#include 

void bfs(const std::vector>& graph, std::vector& visited, int start) {
    // Implement BFS using a queue
    // Your code here
}

int main() {
    std::vector> graph(6);
    graph[0].push_back(1);
    graph[1].push_back(0);
    graph[0].push_back(2);
    graph[2].push_back(0);
    graph[3].push_back(4);
    graph[4].push_back(3);

    std::vector visited(6, false);

    return 0;
}

Hint

Use a queue to explore neighbors. Mark each visited city as true to avoid repeats.

4

Find and print all connected components

In main, use a for loop from 0 to 5. If visited[i] is false, call bfs(graph, visited, i) and print the component number starting from 1. Print "Component " followed by the component number.

DSA C++

#include 
#include 
#include 

void bfs(const std::vector>& graph, std::vector& visited, int start) {
    std::queue q;
    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int city = q.front();
        q.pop();

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

int main() {
    std::vector> graph(6);
    graph[0].push_back(1);
    graph[1].push_back(0);
    graph[0].push_back(2);
    graph[2].push_back(0);
    graph[3].push_back(4);
    graph[4].push_back(3);

    std::vector visited(6, false);

    // Use a for loop to find and print connected components
    // Your code here

    return 0;
}

Hint

Loop through all cities. If a city is not visited, run BFS from it and print the component number.

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