Connected Components Using BFS in DSA Python - Execution Trace

Concept Flow - Connected Components Using BFS

Start with graph and unvisited nodes

↓

Pick an unvisited node

↓

Initialize BFS queue with this node

↓

While queue not empty

↓

Dequeue node -> Mark visited

↓

Add unvisited neighbors to queue

↓

Repeat until queue empty

↓

One connected component found

↓

Repeat for next unvisited node

↓

All nodes visited -> Done

Start BFS from an unvisited node, visit all reachable nodes marking them visited, then repeat for remaining unvisited nodes to find all connected components.

Execution Sample

DSA Python

from collections import deque

def bfs(start):
    queue = deque([start])
    visited.add(start)
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

graph = {
  0: [1],
  1: [0, 2],
  2: [1],
  3: [4],
  4: [3]
}

visited = set()
components = 0

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	Queue State	Visited Set	Connected Component Nodes	Visual State
1	Start BFS from node 0	0	[0]	{}	{}	0 -> ? -> ? -> ? -> ?
2	Dequeue 0, visit	0	[]	{0}	{0}	0 -> ? -> ? -> ? -> ?
3	Add neighbors of 0 (1) to queue	0	[1]	{0}	{0}	0 -> 1 -> ? -> ? -> ?
4	Dequeue 1, visit	1	[]	{0,1}	{0,1}	0 -> 1 -> ? -> ? -> ?
5	Add neighbors of 1 (0,2) to queue; 0 visited, add 2	1	[2]	{0,1}	{0,1}	0 -> 1 -> 2 -> ? -> ?
6	Dequeue 2, visit	2	[]	{0,1,2}	{0,1,2}	0 -> 1 -> 2 -> ? -> ?
7	Add neighbors of 2 (1) to queue; 1 visited, no add	2	[]	{0,1,2}	{0,1,2}	0 -> 1 -> 2 -> ? -> ?
8	Queue empty, component 1 complete	-	[]	{0,1,2}	{0,1,2}	0 -> 1 -> 2 -> ? -> ?
9	Next unvisited node is 3, start BFS	3	[3]	{0,1,2}	{}	0 -> 1 -> 2 -> 3 -> ?
10	Dequeue 3, visit	3	[]	{0,1,2,3}	{3}	0 -> 1 -> 2 -> 3 -> ?
11	Add neighbors of 3 (4) to queue	3	[4]	{0,1,2,3}	{3}	0 -> 1 -> 2 -> 3 -> 4
12	Dequeue 4, visit	4	[]	{0,1,2,3,4}	{3,4}	0 -> 1 -> 2 -> 3 -> 4
13	Add neighbors of 4 (3) to queue; 3 visited, no add	4	[]	{0,1,2,3,4}	{3,4}	0 -> 1 -> 2 -> 3 -> 4
14	Queue empty, component 2 complete	-	[]	{0,1,2,3,4}	{3,4}	0 -> 1 -> 2 -> 3 -> 4
15	All nodes visited, total components = 2	-	-	{0,1,2,3,4}	-	0 -> 1 -> 2 -> 3 -> 4

💡 All nodes visited, BFS completed for all connected components.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 8	After Step 10	After Step 12	After Step 14	Final
visited	{}	{0}	{0,1}	{0,1,2}	{0,1,2}	{0,1,2,3}	{0,1,2,3,4}	{0,1,2,3,4}	{0,1,2,3,4}
queue	[]	[]	[]	[]	[]	[]	[]	[]	[]
components	0	0	0	0	1	1	1	2	2

Key Moments - 3 Insights

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

Because adding visited nodes again would cause repeated visits and infinite loops. See execution_table rows 5 and 7 where neighbors already visited are skipped.

How do we know when one connected component is fully explored?

When the BFS queue becomes empty, meaning no more reachable nodes from the starting node. See execution_table rows 7 and 13 where queue empties mark component completion.

Why do we start BFS again from another unvisited node?

Because unvisited nodes belong to different connected components. BFS from one node only covers its component. See execution_table row 9 where BFS restarts at node 3.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the queue state?

A [2]

B [0,2]

C [1,2]

D []

💡 Hint

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

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

A Step 6

B Step 7

C Step 8

D Step 9

💡 Hint

Look for the step where the queue becomes empty and component 1 is complete.

If node 4 had an extra neighbor 5 (unconnected before), how would the visited set change after step 12?

A {0,1,2,3,4,5}

B {0,1,2,3,4}

C {0,1,2,3}

D {0,1,2,3,5}

💡 Hint

At step 12, only node 4 is visited; neighbor 5 would be added to queue but not visited yet.

Concept Snapshot

Connected Components Using BFS:
- Start BFS from any unvisited node.
- Visit all reachable nodes marking them visited.
- When BFS queue empties, one component is found.
- Repeat for all unvisited nodes.
- Total BFS runs = number of connected components.

Full Transcript

This visualization shows how BFS finds connected components in an undirected graph. We start BFS from an unvisited node, add it to a queue, and visit nodes by dequeuing and adding their unvisited neighbors. We mark nodes visited to avoid repeats. When the queue empties, one connected component is fully explored. We then pick another unvisited node and repeat until all nodes are visited. The number of BFS runs equals the number of connected components. The execution table tracks queue state, visited nodes, and component nodes step-by-step. Key moments clarify why we skip visited neighbors, how we detect component completion, and why BFS restarts for new components.

Practice

1. What does the BFS algorithm help find in an undirected graph when used for 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 maximum degree of any node in the graph

D. The total number of edges in the graph

Solution

1. Step 1: Understand BFS in graph context

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

2. Step 2: Connect BFS to connected components

   Using BFS from an unvisited node finds 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 explores all nodes connected to start node [OK]

Common Mistakes:

• Confusing BFS with shortest path only
• Thinking BFS counts edges
• Mixing BFS with node degree calculation

2. Which of the following is the correct way to initialize a queue for BFS in Python?

easy

A. queue = []

B. queue = dict()

C. queue = set()

D. queue = collections.deque()

Solution

1. Step 1: Identify BFS queue requirements

   BFS requires a queue data structure to process nodes in FIFO order.

2. Step 2: Choose correct Python queue type

   collections.deque() is efficient for queue operations (append and popleft).

3. Final Answer:

   queue = collections.deque() -> Option D

4. Quick Check:

   Use deque for BFS queue in Python [OK]

Hint: Use deque for efficient FIFO queue in BFS [OK]

Common Mistakes:

• Using list which is inefficient for popping front
• Using set which is unordered
• Using dict which is key-value store

3. What is the output of the following code snippet that finds connected components using BFS?

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

for node in graph:
    if node not in visited:
        queue = collections.deque([node])
        comp = []
        while queue:
            current = queue.popleft()
            if current not in visited:
                visited.add(current)
                comp.append(current)
                queue.extend(n for n in graph[current] if n not in visited)
        components.append(sorted(comp))
print(components)

medium

A. [[0], [1], [2], [3]]

B. [[0, 1], [2, 3]]

C. [[0, 1, 2], [3]]

D. [[3], [0, 1, 2]]

Solution

1. Step 1: Analyze graph structure

   Nodes 0,1,2 are connected; node 3 is isolated.

2. Step 2: Trace BFS for each component

   Starting at 0, BFS visits 0,1,2; then 3 alone forms second component.

3. Final Answer:

   [[0, 1, 2], [3]] -> Option C

4. Quick Check:

   Connected components = [[0,1,2],[3]] [OK]

Hint: Group nodes reachable from each unvisited node [OK]

Common Mistakes:

• Not sorting component lists
• Mixing isolated node with others
• Forgetting to mark visited nodes

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

def bfs_components(graph):
    visited = set()
    components = []
    for node in graph:
        if node not in visited:
            queue = [node]
            comp = []
            while queue:
                current = queue.pop()
                if current not in visited:
                    visited.add(current)
                    comp.append(current)
                    for neighbor in graph[current]:
                        if neighbor not in visited:
                            queue.append(neighbor)
            components.append(comp)
    return components

medium

A. Using list pop() removes from end, not front, breaking BFS order

B. Visited set is not updated correctly

C. Neighbors are not checked for visited status

D. Components list is not returned

Solution

1. Step 1: Check queue operations

   Using list pop() removes last element, making it DFS, not BFS.

2. Step 2: Understand BFS queue behavior

   BFS requires FIFO, so pop(0) or deque.popleft() is needed.

3. Final Answer:

   Using list pop() removes from end, not front, breaking BFS order -> Option A

4. Quick Check:

   pop() removes last, use popleft() for BFS [OK]

Hint: Use popleft() or pop(0) for BFS queue [OK]

Common Mistakes:

• Using pop() instead of popleft()
• Not marking visited before enqueue
• Appending neighbors without check

5. Given a graph represented as adjacency list:

graph = {0: [1, 2], 1: [0, 3], 2: [0], 3: [1], 4: [5], 5: [4], 6: []}

Write a BFS-based approach to find the number of connected components and return the size of the largest component.

hard

A. Number of components = 4, Largest size = 2

B. Number of components = 3, Largest size = 4

C. Number of components = 2, Largest size = 4

D. Number of components = 3, Largest size = 2

Solution

1. Step 1: Identify connected components

   Components are: {0,1,2,3}, {4,5}, {6} totaling 3 components.

2. Step 2: Calculate sizes

   Sizes are 4, 2, and 1 respectively; largest is 4 nodes.

3. Step 3: Re-check sizes carefully

   Node 6 is isolated (size 1), so largest component size is 4.

4. Final Answer:

   Number of components = 3, Largest size = 4 -> Option B

5. Quick Check:

   3 components, largest has 4 nodes [OK]

Hint: Count components and track max size during BFS [OK]

Common Mistakes:

• Counting isolated nodes incorrectly
• Mixing component sizes
• Forgetting to update largest size