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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of BFS Connected Components Count

What is the output of the following Java code that counts connected components using BFS on an undirected graph?

DSA Java

import java.util.*;

public class GraphComponents {
    public static int countComponents(int n, int[][] edges) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }
        boolean[] visited = new boolean[n];
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                bfs(i, graph, visited);
                count++;
            }
        }
        return count;
    }

    private static void bfs(int start, List<List<Integer>> graph, boolean[] visited) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        visited[start] = true;
        while (!queue.isEmpty()) {
            int node = queue.poll();
            for (int neighbor : graph.get(node)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.offer(neighbor);
                }
            }
        }
    }

    public static void main(String[] args) {
        int n = 5;
        int[][] edges = {{0,1},{1,2},{3,4}};
        System.out.println(countComponents(n, edges));
    }
}

A 4

B 2

C 1

D 3

💡 Hint

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

The graph has 5 nodes and edges connecting 0-1, 1-2, and 3-4. This forms two connected groups: {0,1,2} and {3,4}. So the output is 2.

🧠 Conceptual

intermediate

Understanding BFS Role in Connected Components

Why is BFS used to find connected components in an undirected graph?

A BFS removes edges to isolate connected components.

B BFS sorts nodes in ascending order to find connected components.

C BFS counts the number of edges in the graph.

D BFS explores all nodes reachable from a start node, marking one connected component completely before moving to the next.

💡 Hint

Think about how BFS visits nodes layer by layer.

BFS starts from a node and visits all nodes reachable from it, marking them visited. This fully explores one connected component before moving to another unvisited node.

🔧 Debug

advanced

Identify the Bug in BFS Connected Components Code

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

DSA Java

import java.util.*;

public class BuggyGraph {
    public static int countComponents(int n, int[][] edges) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) graph.add(new ArrayList<>());
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }
        boolean[] visited = new boolean[n];
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                bfs(i, graph, visited);
                count++;
            }
        }
        return count;
    }

    private static void bfs(int start, List<List<Integer>> graph, boolean[] visited) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        visited[start] = true;
        while (!queue.isEmpty()) {
            int node = queue.poll();
            for (int neighbor : graph.get(node)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.offer(neighbor);
                }
            }
        }
    }

A IndexOutOfBoundsException due to graph list size mismatch

B NullPointerException when accessing graph neighbors

C ArrayIndexOutOfBoundsException when marking visited nodes

D No error, code runs correctly

💡 Hint

Check how the graph list is initialized compared to the number of nodes.

The graph list is initialized with n+1 lists but visited array has size n. This mismatch can cause IndexOutOfBoundsException when accessing visited[neighbor] for neighbor == n.

📝 Syntax

advanced

Identify Syntax Error in BFS Connected Components Code

Which option contains a syntax error in the BFS connected components Java code?

DSA Java

import java.util.*;

public class SyntaxGraph {
    public static int countComponents(int n, int[][] edges) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }
        boolean[] visited = new boolean[n];
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                bfs(i, graph, visited);
                count++;
            }
        }
        return count;
    }

    private static void bfs(int start, List<List<Integer>> graph, boolean[] visited) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        visited[start] = true;
        while (!queue.isEmpty()) {
            int node = queue.poll();
            for (int neighbor : graph.get(node)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.offer(neighbor);
                }
            }
        }
    }

A Replace 'boolean[] visited = new boolean[n];' with 'boolean visited[] = new boolean[n];'

B Remove semicolon after 'queue.offer(start);' line

C Change 'for (int[] edge : edges)' to 'for int[] edge : edges)'

D Add missing semicolon after 'count++' line

💡 Hint

Check the syntax of the enhanced for loop.

Option C has a syntax error: the enhanced for loop must have parentheses around the variable declaration. Missing '(' causes syntax error.

🚀 Application

expert

Number of Connected Components After Adding Edges

Given a graph with 6 nodes and edges {{0,1},{1,2},{3,4}}, after adding the edge {2,3}, what is the number of connected components?

A 2

B 1

C 3

D 4

💡 Hint

Adding edge {2,3} connects two previously separate components.

Initially, components are {0,1,2}, {3,4}, and {5}. Adding edge {2,3} connects {0,1,2} and {3,4} into one component. Node 5 remains isolated. So total components = 2.

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