Connected Components Using BFS in DSA Java

Mental Model

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

Analogy: Imagine a group of friends at a party where everyone in a group can talk to each other directly or through others; BFS helps us find each friend group by visiting one friend at a time and then their friends.

Graph:
0 -> 1 -> 2

3 -> 4

5 (isolated)

We want to find these groups: {0,1,2}, {3,4}, {5}

Dry Run Walkthrough

Input: Graph with edges: 0-1, 1-2, 3-4, and isolated node 5

Goal: Identify all connected groups of nodes using BFS

Step 1: Start BFS from node 0, mark it visited

Visited: {0}
Queue: [0]

Why: We begin exploring from node 0 to find its connected group

Step 2: Dequeue 0, enqueue its neighbor 1, mark 1 visited

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

Why: Node 1 is connected to 0, so we add it to the group

Step 3: Dequeue 1, enqueue neighbor 2, mark 2 visited

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

Why: Node 2 is connected to 1, so it belongs to the same group

Step 4: Dequeue 2, no new neighbors to visit

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

Why: All nodes connected to 0 are visited, group complete

Step 5: Start BFS from next unvisited node 3, mark visited

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

Why: Find next group starting from node 3

Step 6: Dequeue 3, enqueue neighbor 4, mark 4 visited

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

Why: Node 4 is connected to 3, same group

Step 7: Dequeue 4, no new neighbors

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

Why: Group {3,4} fully explored

Step 8: Start BFS from node 5, mark visited

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

Why: Node 5 is isolated, forms its own group

Step 9: Dequeue 5, no neighbors

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

Why: Isolated node group complete

Result:

Groups found:
Group 1: 0 -> 1 -> 2
Group 2: 3 -> 4
Group 3: 5

Annotated Code

DSA Java

import java.util.*;

public class ConnectedComponentsBFS {

    static class Graph {
        int vertices;
        List<List<Integer>> adjList;

        Graph(int v) {
            vertices = v;
            adjList = new ArrayList<>();
            for (int i = 0; i < v; i++) {
                adjList.add(new ArrayList<>());
            }
        }

        void addEdge(int src, int dest) {
            adjList.get(src).add(dest);
            adjList.get(dest).add(src); // undirected graph
        }
    }

    static List<List<Integer>> connectedComponents(Graph graph) {
        boolean[] visited = new boolean[graph.vertices];
        List<List<Integer>> components = new ArrayList<>();

        for (int i = 0; i < graph.vertices; i++) {
            if (!visited[i]) {
                List<Integer> component = new ArrayList<>();
                bfs(i, graph, visited, component);
                components.add(component);
            }
        }
        return components;
    }

    static void bfs(int start, Graph graph, boolean[] visited, List<Integer> component) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visited[start] = true; // mark start visited

        while (!queue.isEmpty()) {
            int node = queue.poll();
            component.add(node); // add node to current component

            for (int neighbor : graph.adjList.get(node)) {
                if (!visited[neighbor]) {
                    queue.add(neighbor);
                    visited[neighbor] = true; // mark neighbor visited
                }
            }
        }
    }

    public static void main(String[] args) {
        Graph graph = new Graph(6);
        graph.addEdge(0, 1);
        graph.addEdge(1, 2);
        graph.addEdge(3, 4);

        List<List<Integer>> components = connectedComponents(graph);

        int groupNum = 1;
        for (List<Integer> comp : components) {
            System.out.print("Group " + groupNum + ": ");
            for (int node : comp) {
                System.out.print(node + " -> ");
            }
            System.out.println("null");
            groupNum++;
        }
    }
}

if (!visited[i]) {

start BFS from unvisited node to find a new connected component

visited[start] = true; // mark start visited

mark the starting node as visited to avoid revisiting

int node = queue.poll();

dequeue node to explore its neighbors

component.add(node); // add node to current component

add current node to the connected component list

if (!visited[neighbor]) {

check if neighbor is unvisited before adding to queue

visited[neighbor] = true; // mark neighbor visited

mark neighbor visited to prevent reprocessing

Output

Group 1: 0 -> 1 -> 2 -> null

Group 2: 3 -> 4 -> null

Group 3: 5 -> null

Complexity Analysis

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

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

vs Alternative: Compared to DFS, BFS uses a queue but both have similar time and space complexity; BFS is often easier to implement for shortest path or level order traversal

Edge Cases

Graph with no edges (all isolated nodes)

Each node forms its own connected component

DSA Java

if (!visited[i]) {

Graph with a single node

One connected component containing that single node

DSA Java

if (!visited[i]) {

Graph with all nodes connected (one big component)

Only one connected component containing all nodes

DSA Java

if (!visited[i]) {

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 when enqueued, causing repeated visits
Fix: Mark nodes as visited immediately when adding to the queue to avoid duplicates

Mistake: Forgetting to check if a node is visited before starting BFS
Fix: Always check visited array before starting BFS from a node

Summary

Finds all connected groups of nodes in an undirected graph using BFS.

Use when you want to identify separate clusters or connected components in a graph.

The key is to explore all neighbors of a node before moving to the next group.

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