Connected Components Using BFS in DSA Java - Build from Scratch

Connected Components Using BFS

📖 Scenario: Imagine you have a group of friends and their connections. You want to find how many separate friend groups exist where everyone in a group is connected directly or indirectly.

🎯 Goal: Build a Java program that finds the number of connected friend groups using Breadth-First Search (BFS) on an undirected graph.

📋 What You'll Learn

Create an adjacency list to represent the graph

Use a boolean array to track visited nodes

Implement BFS to explore each connected component

Count and print the total number of connected components

💡 Why This Matters

🌍 Real World

Finding connected groups in social networks, computer networks, or clusters in data analysis.

💼 Career

Understanding graph traversal and connected components is essential for roles in software development, data science, and network engineering.

1

Create the graph adjacency list

Create a Java Map<Integer, List<Integer>> called graph representing the following undirected graph edges: 1-2, 2-3, 4-5. Initialize the adjacency list with these exact connections.

DSA Java

// Your code here

Hint

Use a HashMap with Integer keys and List<Integer> values. Use Arrays.asList() to add neighbors.

2

Create the visited array

Add a boolean array called visited of size 6 (index 0 unused) to track visited nodes. Initialize all values to false.

DSA Java

import java.util.*;

public class ConnectedComponents {
    public static void main(String[] args) {
        Map> graph = new HashMap();
        graph.put(1, Arrays.asList(2));
        graph.put(2, Arrays.asList(1, 3));
        graph.put(3, Arrays.asList(2));
        graph.put(4, Arrays.asList(5));
        graph.put(5, Arrays.asList(4));

        // Your code here
    }
}

Hint

Create a boolean array with size 6 to cover nodes 1 to 5. Index 0 will not be used.

3

Implement BFS and count connected components

Write a for loop from 1 to 5. For each node not visited, call a bfs method passing graph, visited, and the node. Increase an integer count by 1 for each BFS call. Implement the bfs method using a Queue<Integer> to visit all connected nodes.

DSA Java

import java.util.*;

public class ConnectedComponents {
    public static void main(String[] args) {
        Map> graph = new HashMap();
        graph.put(1, Arrays.asList(2));
        graph.put(2, Arrays.asList(1, 3));
        graph.put(3, Arrays.asList(2));
        graph.put(4, Arrays.asList(5));
        graph.put(5, Arrays.asList(4));

        boolean[] visited = new boolean[6];

        // Your code here
    }

    // Your bfs method here
}

Hint

Use a for loop to check each node. If not visited, run BFS and increase count. BFS uses a queue to visit neighbors.

4

Print the number of connected components

Add a System.out.println statement to print the integer count which holds the number of connected components.

DSA Java

import java.util.*;

public class ConnectedComponents {
    public static void main(String[] args) {
        Map> graph = new HashMap();
        graph.put(1, Arrays.asList(2));
        graph.put(2, Arrays.asList(1, 3));
        graph.put(3, Arrays.asList(2));
        graph.put(4, Arrays.asList(5));
        graph.put(5, Arrays.asList(4));

        boolean[] visited = new boolean[6];
        int count = 0;
        for (int node = 1; node > graph, boolean[] visited, int start) {
        Queue queue = new LinkedList();
        queue.add(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            int current = queue.poll();
            List neighbors = graph.getOrDefault(current, Collections.emptyList());
            for (int neighbor : neighbors) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.add(neighbor);
                }
            }
        }
    }
}

Hint

Use System.out.println(count); to print the number of connected 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