Connected Components Using BFS in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of BFS Connected Components Count

What is the output of the following Python code that counts connected components using BFS?

DSA Python

from collections import deque

def bfs(graph, start, visited):
    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)

def count_connected_components(graph):
    visited = set()
    count = 0
    for node in graph:
        if node not in visited:
            bfs(graph, node, visited)
            count += 1
    return count

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

print(count_connected_components(graph))

A 2

B 3

C 4

D 1

💡 Hint

Count how many groups of nodes are connected without crossing to other groups.

The graph has three connected components: {1,2,3}, {4,5}, and {6}. So the output is 3.

🧠 Conceptual

intermediate

Understanding BFS Role in Connected Components

Why do we use BFS to find connected components in an undirected graph?

A Because BFS deletes edges to separate components.

B Because BFS sorts the nodes in ascending order to find components.

C Because BFS explores all nodes reachable from a start node, marking one connected component completely before moving to another.

D Because BFS only visits nodes with even values.

💡 Hint

Think about how BFS visits nodes layer by layer.

BFS visits all nodes connected to the start node before moving on, so it identifies one whole connected component at a time.

❓ Predict Output

advanced

Output of BFS with Disconnected Graph

What is the output of this code that uses BFS to find connected components in a graph with isolated nodes?

DSA Python

from collections import deque

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

def count_connected_components(graph):
    visited = set()
    count = 0
    for node in graph:
        if node not in visited:
            bfs(graph, node, visited)
            count += 1
    return count

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

print(count_connected_components(graph))

A 5

B 3

C 4

D 2

💡 Hint

Count each isolated node and each connected group separately.

The connected components are {1,2}, {3}, {4,5}, {6}, and {7}, totaling 5 components.

🔧 Debug

advanced

Identify the Error in BFS Connected Components Code

What error will this code produce when counting connected components using BFS?

DSA Python

from collections import deque

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

def count_connected_components(graph):
    visited = set()
    count = 0
    for node in graph:
        if node not in visited:
            bfs(graph, node, visited)
            count += 1
    return count

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

print(count_connected_components(graph))

A The code runs correctly and outputs 1

B The code raises a KeyError

C The code outputs 3 instead of 1

D The BFS traversal order is incorrect but output is still 1

💡 Hint

Check how nodes are removed from the queue.

Using queue.pop() removes from the right end, making it DFS order instead of BFS, but connected components count remains correct.

🚀 Application

expert

Number of Connected Components After Edge Removal

Given the graph and the edges removed, what is the number of connected components after removal?

DSA Python

from collections import deque

def bfs(graph, start, visited):
    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)

def count_connected_components(graph):
    visited = set()
    count = 0
    for node in graph:
        if node not in visited:
            bfs(graph, node, visited)
            count += 1
    return count

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

# Remove edges (3,4) and (4,5)
graph[3].remove(4)
graph[4].remove(3)
graph[4].remove(5)
graph[5].remove(4)

print(count_connected_components(graph))

A 3

B 4

C 1

D 2

💡 Hint

Removing edges splits the graph into separate parts.

After removing edges, the graph splits into three connected components: {1,2,3}, {4}, and {5}.

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