Connected Components Using BFS in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a connected component in an undirected graph?

A connected component is a group of nodes where each node is reachable from any other node in the same group through edges.

beginner

What does BFS stand for and what is its role in finding connected components?

BFS stands for Breadth-First Search. It explores all neighbors of a node before moving to the next level, helping to find all nodes in a connected component.

beginner

In BFS for connected components, why do we mark nodes as visited?

Marking nodes as visited prevents revisiting the same node multiple times, avoiding infinite loops and ensuring each node is counted once.

intermediate

How do you count the number of connected components using BFS?

Start BFS from each unvisited node. Each BFS call explores one connected component. Count how many times BFS is called on unvisited nodes.

beginner

What data structure is commonly used to implement BFS and why?

A queue is used because BFS explores nodes level by level, and a queue maintains the order of nodes to visit next.

What is the first step when using BFS to find connected components in a graph?

A Start BFS from an unvisited node

B Mark all nodes as visited

C Add all nodes to the queue at once

D Remove edges from the graph

We start BFS from an unvisited node to explore its connected component.

Which data structure is essential for BFS traversal?

A Set

B Stack

C Queue

D Map

A queue is used to explore nodes in the order they are discovered.

How do you know when you have found all connected components in a graph using BFS?

A When BFS is called once

B When the queue is empty

C When all edges are removed

D When all nodes are visited

All connected components are found when every node has been visited.

What happens if you do not mark nodes as visited in BFS?

A You may revisit nodes and get stuck in loops

B The graph will change

C The BFS will run faster

D You will find fewer connected components

Without marking visited nodes, BFS can revisit nodes repeatedly causing infinite loops.

In BFS, what does the queue store?

A Connected components

B Nodes to be visited next

C Edges of the graph

D All visited nodes

The queue stores nodes that are discovered but not yet explored.

Explain how BFS helps in finding connected components in an undirected graph.

Think about how BFS explores nodes level by level and how that relates to connected groups.

Describe the steps to count the number of connected components using BFS.

Focus on how BFS and visited tracking work together to find components.

Practice

1. What does the BFS algorithm help find in an undirected graph when used for connected components?

easy

A. The shortest path between two nodes only

B. The degree of each node

C. The total number of edges in the graph

D. All nodes reachable from a starting node forming one connected component

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

   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 D

4. Quick Check:

   BFS finds connected components by exploring reachable nodes [OK]

Hint: BFS visits all nodes in one connected group [OK]

Common Mistakes:

• Thinking BFS only finds shortest paths
• Confusing connected components with edge count
• Assuming BFS finds node degrees

2. Which of the following is the correct Java syntax to initialize a queue for BFS traversal?

easy

A. Queue<Integer> queue = new LinkedList<>();

B. Queue<Integer> queue = new ArrayList<>();

C. Queue<Integer> queue = new Stack<>();

D. Queue<Integer> queue = new HashSet<>();

Solution

1. Step 1: Identify correct Queue implementation

   Java's Queue interface is commonly implemented by LinkedList for BFS.

2. Step 2: Check other options

   ArrayList is not a Queue, Stack is LIFO not FIFO, HashSet is a Set, not a Queue.

3. Final Answer:

   Queue<Integer> queue = new LinkedList<>(); -> Option A

4. Quick Check:

   LinkedList implements Queue for BFS [OK]

Hint: Use LinkedList for Queue in BFS [OK]

Common Mistakes:

• Using ArrayList instead of Queue
• Using Stack which is LIFO, not FIFO
• Using HashSet which is unordered

3. What is the output of the following code snippet that uses BFS to count connected components in a graph?

int n = 5;
List graph = new ArrayList<>();
for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
graph.get(0).add(1);
graph.get(1).add(0);
graph.get(2).add(3);
graph.get(3).add(2);
boolean[] visited = new boolean[n];
int count = 0;
for (int i = 0; i < n; i++) {
  if (!visited[i]) {
    Queue<Integer> queue = new LinkedList<>();
    queue.add(i);
    visited[i] = true;
    while (!queue.isEmpty()) {
      int node = queue.poll();
      for (int nei : graph.get(node)) {
        if (!visited[nei]) {
          visited[nei] = true;
          queue.add(nei);
        }
      }
    }
    count++;
  }
}
System.out.println(count);

medium

A. 3

B. 2

C. 1

D. 4

Solution

1. Step 1: Analyze graph edges

   Edges connect nodes 0-1 and 2-3. Node 4 is isolated.

2. Step 2: Count connected components

   Components are {0,1}, {2,3}, and {4} -> total 3 components.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   3 connected groups found [OK]

Hint: Count isolated and connected groups carefully [OK]

Common Mistakes:

• Ignoring isolated nodes
• Counting edges instead of components
• Misreading graph connections

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

for (int i = 0; i < n; i++) {
  if (!visited[i]) {
    Queue<Integer> queue = new LinkedList<>();
    queue.add(i);
    while (!queue.isEmpty()) {
      int node = queue.poll();
      for (int nei : graph.get(node)) {
        if (!visited[nei]) {
          queue.add(nei);
          visited[nei] = true;
        }
      }
    }
    count++;
  }
}

medium

A. Graph adjacency list is empty

B. visited[i] is not set to true before BFS

C. count++ is inside the inner loop

D. Queue is not initialized properly

Solution

1. Step 1: Check visited marking

   visited[i] should be set true when node i is added to queue to avoid revisiting.

2. Step 2: Identify missing visited update

   Code adds i to queue but does not mark visited[i] true before BFS loop.

3. Final Answer:

   visited[i] is not set to true before BFS -> Option B

4. Quick Check:

   Mark visited when adding to queue [OK]

Hint: Always mark visited when enqueueing nodes [OK]

Common Mistakes:

• Marking visited after dequeueing
• Not initializing queue correctly
• Incrementing count inside BFS loop

5. Given a graph with 7 nodes and edges: (0-1), (1-2), (3-4), (5-6), how many connected components will BFS find if run on all nodes? Also, which nodes belong to the largest component?

hard

A. 2 connected components; largest component nodes: [0, 1, 2, 3, 4]

B. 3 connected components; largest component nodes: [3, 4, 5, 6]

C. 3 connected components; largest component nodes: [0, 1, 2]

D. 5 connected components; largest component nodes: [5, 6]

Solution

1. Step 1: Identify connected groups

   Edges form groups: {0,1,2}, {3,4}, {5,6} -- total 3 components (nodes 0-6).

2. Step 2: Count components and largest group

   3 components total. Largest is {0,1,2} with 3 nodes.

3. Final Answer:

   3 connected components; largest component nodes: [0, 1, 2] -> Option C

4. Quick Check:

   3 components, largest size 3 [OK]

Hint: Group nodes by edges; largest group has most nodes [OK]

Common Mistakes:

• Counting nodes incorrectly
• Missing isolated nodes
• Mixing node indices