Connected Components Using BFS in DSA Python

Mental Model

We find groups of nodes where each node can reach every other node in the same group by walking through neighbors step-by-step.

Analogy: Imagine a group of friends at a party where everyone in a group can talk to each other by passing messages through mutual friends. BFS helps us find each friend group by exploring neighbors one by one.

Graph:
0 -> 1 -> 2
3 -> 4
5

Groups:
[0,1,2]  [3,4]  [5]

Dry Run Walkthrough

Input: Graph with edges: 0-1, 1-2, 3-4, nodes: 0 to 5

Goal: Identify all connected groups of nodes using BFS

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

Queue: [0]
Visited: {0}
Component: [0]

Why: We begin exploring from the first unvisited node to find its connected group

Step 2: Dequeue 0, enqueue its neighbor 1, mark 1 visited and add to component

Queue: [1]
Visited: {0,1}
Component: [0,1]

Why: Explore neighbors of 0 to find all connected nodes

Step 3: Dequeue 1, enqueue its neighbor 2, mark 2 visited and add to component

Queue: [2]
Visited: {0,1,2}
Component: [0,1,2]

Why: Continue exploring neighbors to complete the connected group

Step 4: Dequeue 2, no new neighbors to add

Queue: []
Visited: {0,1,2}
Component: [0,1,2]

Why: No more nodes connected to this group

Step 5: Start BFS from next unvisited node 3, mark 3 visited and add to new component

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

Why: Find next connected group starting from unvisited node

Step 6: Dequeue 3, enqueue neighbor 4, mark 4 visited and add to component

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

Why: Explore neighbors of 3 to find all connected nodes

Step 7: Dequeue 4, no new neighbors to add

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

Why: No more nodes connected to this group

Step 8: Start BFS from last unvisited node 5, mark 5 visited and add to new component

Queue: [5]
Visited: {0,1,2,3,4,5}
Component: [5]

Why: Single node forms its own connected group

Step 9: Dequeue 5, no neighbors to add

Queue: []
Visited: {0,1,2,3,4,5}
Component: [5]

Why: No more nodes connected to this group

Result:

Connected Components:
[0, 1, 2]
[3, 4]
[5]

Annotated Code

DSA Python

from collections import deque

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.adj = [[] for _ in range(vertices)]

    def add_edge(self, u, v):
        self.adj[u].append(v)
        self.adj[v].append(u)  # undirected graph

    def bfs_component(self, start, visited):
        queue = deque([start])
        visited[start] = True
        component = [start]
        while queue:
            node = queue.popleft()  # dequeue node to explore neighbors
            for neighbor in self.adj[node]:
                if not visited[neighbor]:
                    visited[neighbor] = True  # mark neighbor visited
                    queue.append(neighbor)  # enqueue neighbor
                    component.append(neighbor)  # add to current component
        return component

    def connected_components(self):
        visited = [False] * self.V
        components = []
        for v in range(self.V):
            if not visited[v]:
                comp = self.bfs_component(v, visited)  # find component using BFS
                components.append(comp)
        return components

# Driver code
if __name__ == '__main__':
    g = Graph(6)
    g.add_edge(0, 1)
    g.add_edge(1, 2)
    g.add_edge(3, 4)

    comps = g.connected_components()
    for c in comps:
        print(c)

queue = deque([start]) visited[start] = True component = [start]

initialize BFS queue, mark start visited, add start to component

node = queue.popleft()

dequeue node to explore neighbors

if not visited[neighbor]: visited[neighbor] = True queue.append(neighbor) component.append(neighbor)

visit unvisited neighbors, enqueue them, add to component

for v in range(self.V): if not visited[v]: comp = self.bfs_component(v, visited) components.append(comp)

for each unvisited node, find its connected component using BFS

Output

[0, 1, 2]

[3, 4]

[5]

Complexity Analysis

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

Space: O(V) for the visited list, queue, and storing components

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

Edge Cases

Empty graph (0 nodes)

Returns empty list of components

DSA Python

for v in range(self.V):

Graph with isolated nodes (no edges)

Each node forms its own component

DSA Python

if not visited[v]:

Graph with all nodes connected

Returns single component containing all nodes

DSA Python

component.append(neighbor)

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, causing repeated visits
Fix: Mark nodes visited immediately when enqueueing to avoid duplicates

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 neighbors level by level, marking visited nodes to avoid repeats.

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