Connected Components Using BFS in DSA C++ - Execution Trace

Concept Flow - Connected Components Using BFS

Start with graph

↓

Initialize visited set

↓

For each node in graph

↓

If node not visited?

No→Skip to next node

Yes↓

Start BFS from node

↓

Mark node visited, add to queue

↓

While queue not empty

↓

Pop node from queue

↓

For each neighbor

↓

If neighbor not visited

↓

Mark visited, add to queue

↓

Repeat until queue empty

↓

One connected component found

↓

Repeat for next unvisited node

↓

All nodes visited, done

The flow shows how BFS explores each connected component by visiting nodes and their neighbors, marking them visited to avoid repeats.

Execution Sample

DSA C++

graph = {
 0: [1],
 1: [0, 2],
 2: [1],
 3: [4],
 4: [3]
}
visited = set()
components = 0

def BFS(start):
    queue = [start]
    visited.add(start)
    while queue:
        node = queue.pop(0)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

for node in graph:
    if node not in visited:
        BFS(node)
        components += 1

This code finds connected components in an undirected graph using BFS.

Execution Table

Step	Operation	Current Node	Visited Set	Queue	Connected Component Nodes	Visual State
1	Start BFS from node 0	0	{}	[0]	[]	Graph: 0--1--2 3--4
2	Pop from queue	0	{0}	[]	[0]	Visited 0, queue empty
3	Check neighbors of 0	0	{0}	[]	[0]	Neighbor 1 not visited
4	Add neighbor 1 to queue	0	{0,1}	[1]	[0]	Queue: [1]
5	Pop from queue	1	{0,1}	[]	[0,1]	Visited 1, queue empty
6	Check neighbors of 1	1	{0,1}	[]	[0,1]	Neighbors 0 (visited), 2 (not visited)
7	Add neighbor 2 to queue	1	{0,1,2}	[2]	[0,1]	Queue: [2]
8	Pop from queue	2	{0,1,2}	[]	[0,1,2]	Visited 2, queue empty
9	Check neighbors of 2	2	{0,1,2}	[]	[0,1,2]	Neighbor 1 visited, no add
10	BFS complete for component	-	{0,1,2}	[]	[0,1,2]	Component 1 found: nodes 0,1,2
11	Next node 1 already visited	1	{0,1,2}	[]	[0,1,2]	Skip node 1
12	Next node 2 already visited	2	{0,1,2}	[]	[0,1,2]	Skip node 2
13	Start BFS from node 3	3	{0,1,2}	[3]	[0,1,2]	Start component 2
14	Pop from queue	3	{0,1,2,3}	[]	[0,1,2,3]	Visited 3, queue empty
15	Check neighbors of 3	3	{0,1,2,3}	[]	[0,1,2,3]	Neighbor 4 not visited
16	Add neighbor 4 to queue	3	{0,1,2,3,4}	[4]	[0,1,2,3]	Queue: [4]
17	Pop from queue	4	{0,1,2,3,4}	[]	[0,1,2,3,4]	Visited 4, queue empty
18	Check neighbors of 4	4	{0,1,2,3,4}	[]	[0,1,2,3,4]	Neighbor 3 visited, no add
19	BFS complete for component	-	{0,1,2,3,4}	[]	[0,1,2,3,4]	Component 2 found: nodes 3,4
20	Next node 4 already visited	4	{0,1,2,3,4}	[]	[0,1,2,3,4]	Skip node 4
21	All nodes visited	-	{0,1,2,3,4}	[]	[0,1,2,3,4]	Done: 2 connected components

💡 All nodes visited, no unvisited nodes remain to start BFS

Variable Tracker

Variable	Start	After Step 1	After Step 5	After Step 10	After Step 13	After Step 19	Final
visited	{}	{}	{0,1}	{0,1,2}	{0,1,2}	{0,1,2,3,4}	{0,1,2,3,4}
queue	[]	[0]	[]	[]	[3]	[]	[]
connected_component_nodes	[]	[]	[0,1]	[0,1,2]	[0,1,2]	[0,1,2,3,4]	[0,1,2,3,4]
components_count	0	0	0	1	1	2	2

Key Moments - 3 Insights

Why do we skip nodes already in the visited set when iterating over all nodes?

Because those nodes are already part of a connected component found by BFS, skipping them avoids repeated work. See execution_table rows 11 and 12 where nodes 1 and 2 are skipped.

Why do we add neighbors to the queue only if they are not visited?

Adding only unvisited neighbors prevents infinite loops and repeated visits. This is shown in execution_table rows 6-7 and 15-16 where only unvisited neighbors are enqueued.

How do we know when one connected component BFS is complete?

When the queue becomes empty, BFS has visited all nodes reachable from the start node. See execution_table rows 9 and 18 where queue empties mark BFS completion.

Visual Quiz - 3 Questions

Look at the execution_table at step 5. What is the content of the queue?

A []

B [1]

C [2]

D [0]

💡 Hint

Check the 'Queue' column at step 5 in execution_table

At which step does the BFS finish exploring the first connected component?

A Step 8

B Step 10

C Step 13

D Step 19

💡 Hint

Look for the row where BFS completes for component 1 in execution_table

If node 3 had no neighbors, how would the queue change at step 16?

A Queue would be empty []

B Queue would contain [4]

C Queue would contain [3]

D Queue would contain [0,1,2]

💡 Hint

Check how neighbors affect queue additions in execution_table steps 15-16

Concept Snapshot

Connected Components Using BFS:
- Visit each node in graph
- If unvisited, start BFS
- Use queue to explore neighbors
- Mark visited nodes to avoid repeats
- Each BFS finds one connected component
- Repeat until all nodes visited

Full Transcript

This visualization shows how BFS finds connected components in an undirected graph. We start with an empty visited set and check each node. If a node is not visited, we start BFS from it, adding it to a queue and marking visited. We then explore neighbors, adding unvisited ones to the queue. When the queue empties, one connected component is found. We continue checking nodes until all are visited. The execution table tracks each step, showing the queue, visited set, and nodes in the current component. Key moments clarify why we skip visited nodes and how BFS completion is detected. The quiz tests understanding of queue contents and BFS progress. This method efficiently finds all connected components by exploring reachable nodes from each unvisited start 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