Connected Components Using BFS in DSA C - Execution Trace

Concept Flow - Connected Components Using BFS

Start with all nodes unvisited

↓

Pick an unvisited node

↓

Initialize queue with this node

↓

While queue not empty

↓

Dequeue node, mark visited

↓

Enqueue all unvisited neighbors

↓

Repeat until queue empty

↓

One connected component found

↓

Repeat for next unvisited node

↓

All nodes visited, done

The BFS explores all nodes connected to a starting node, marking them visited to find one connected component. Repeat for all unvisited nodes to find all components.

Execution Sample

DSA C

void bfs(int start) {
  queue<int> q;
  q.push(start);
  visited[start] = true;
  while (!q.empty()) {
    int node = q.front(); q.pop();
    for (auto nbr : graph[node]) {
      if (!visited[nbr]) {
        visited[nbr] = true;
        q.push(nbr);
      }
    }
  }
}

This BFS function visits all nodes connected to 'start', marking them visited and using a queue to explore neighbors.

Execution Table

Step	Operation	Current Node	Queue State	Visited Nodes	Connected Component Found
1	Start BFS from node 0	-	[0]	[0]	[0]
2	Dequeue node 0	0	[]	[0]	[0]
3	Enqueue neighbors of 0: 1, 2	-	[1, 2]	[0,1,2]	[0,1,2]
4	Dequeue node 1	1	[2]	[0,1,2]	[0,1,2]
5	Enqueue neighbors of 1: 0 (visited), 3	-	[2, 3]	[0,1,2,3]	[0,1,2,3]
6	Dequeue node 2	2	[3]	[0,1,2,3]	[0,1,2,3]
7	Enqueue neighbors of 2: 0 (visited)	-	[3]	[0,1,2,3]	[0,1,2,3]
8	Dequeue node 3	3	[]	[0,1,2,3]	[0,1,2,3]
9	Enqueue neighbors of 3: 1 (visited)	-	[]	[0,1,2,3]	[0,1,2,3]
10	Queue empty, component complete	-	[]	[0,1,2,3]	[0,1,2,3]
11	Start BFS from next unvisited node 4	-	[4]	[0,1,2,3,4]	[0,1,2,3],[4]
12	Dequeue node 4	4	[]	[0,1,2,3,4]	[0,1,2,3],[4]
13	Enqueue neighbors of 4: 5	-	[5]	[0,1,2,3,4,5]	[0,1,2,3],[4,5]
14	Dequeue node 5	5	[]	[0,1,2,3,4,5]	[0,1,2,3],[4,5]
15	Enqueue neighbors of 5: 4 (visited)	-	[]	[0,1,2,3,4,5]	[0,1,2,3],[4,5]
16	Queue empty, component complete	-	[]	[0,1,2,3,4,5]	[0,1,2,3],[4,5]
17	All nodes visited, BFS ends	-	[]	[0,1,2,3,4,5]	[0,1,2,3],[4,5]

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

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 10	After Step 13	After Step 16	Final
visited	[false,false,false,false,false,false]	[true,true,true,false,false,false]	[true,true,true,true,false,false]	[true,true,true,true,false,false]	[true,true,true,true,true,true]	[true,true,true,true,true,true]	[true,true,true,true,true,true]
queue	[]	[1,2]	[2,3]	[]	[5]	[]	[]
connected_components	[]	[[0,1,2]]	[[0,1,2,3]]	[[0,1,2,3]]	[[0,1,2,3],[4,5]]	[[0,1,2,3],[4,5]]	[[0,1,2,3],[4,5]]

Key Moments - 3 Insights

Why do we mark nodes as visited when we enqueue them, not when we dequeue?

Marking nodes visited when enqueued (see steps 3 and 5) prevents adding the same node multiple times to the queue, avoiding repeated processing and infinite loops.

What happens if the graph is disconnected?

The BFS runs on one connected component at a time (steps 1-10 for first component, steps 11-16 for second), then starts BFS again from the next unvisited node to find all components.

Why do we stop BFS when the queue is empty?

An empty queue (steps 10 and 16) means all reachable nodes from the start node are visited, so one connected component is fully explored.

Visual Quiz - 3 Questions

Look at the execution table, what nodes are in the queue after step 5?

A [2, 3]

B [1, 2]

C [3]

D []

💡 Hint

Check the 'Queue State' column at step 5 in the execution_table.

At which step does BFS start exploring the second connected component?

A Step 10

B Step 11

C Step 13

D Step 16

💡 Hint

Look for the step where BFS starts from a new unvisited node in the execution_table.

If node 3 had an additional neighbor 6 (unvisited), when would it be added to the queue?

A At step 9 when dequeuing node 3

B At step 5 when dequeuing node 1

C At step 3 when dequeuing node 0

D At step 16 when exploring second component

💡 Hint

Neighbors are enqueued when their connected node is dequeued, see steps 3, 5, 8, 9.

Concept Snapshot

Connected Components Using BFS:
- Start BFS from any unvisited node.
- Use a queue to explore neighbors level by level.
- Mark nodes visited when enqueued to avoid repeats.
- When queue empties, one connected component is found.
- Repeat for all unvisited nodes to find all components.

Full Transcript

Connected Components Using BFS finds groups of nodes connected together in a graph. We start BFS from an unvisited node, add it to a queue, and mark it visited. Then we repeatedly dequeue nodes, visit their neighbors, and enqueue unvisited neighbors, marking them visited immediately. This process continues until the queue is empty, meaning one connected component is fully explored. Then BFS starts again from another unvisited node to find the next component. This repeats until all nodes are visited. The execution table shows each step, queue contents, visited nodes, and connected components found. Key points include marking visited when enqueued to avoid duplicates, handling disconnected graphs by restarting BFS, and stopping BFS when the queue is empty. The visual quiz tests understanding of queue states, BFS start steps, and neighbor enqueue timing.

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