Connected Components Using BFS in DSA Java - Execution Trace

Concept Flow - Connected Components Using BFS

Start with graph

↓

Initialize visited set

↓

For each node in graph

↓

If node not visited?

No→Skip

Yes↓

Start BFS from node

↓

Add node to queue and visited

↓

While queue not empty

↓

Dequeue node

↓

For each neighbor

↓

If neighbor not visited

↓

Add neighbor to queue and visited

↓

Repeat until queue empty

↓

One connected component found

↓

Repeat for next unvisited node

↓

All nodes visited, done

We visit each node in the graph. If not visited, we run BFS to find all nodes in its connected component, marking them visited. Repeat until all nodes are visited.

Execution Sample

DSA Java

graph = {
  0: [1],
  1: [0, 2],
  2: [1],
  3: [4],
  4: [3]
}
visited = set()

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

for node in graph:
    if node not in visited:
        bfs(node)

This code finds connected components in a graph using BFS, marking nodes visited as it explores.

Execution Table

Step	Operation	Current Node	Queue	Visited Set	Connected Component	Visual State
1	Start BFS from node 0	0	[0]	{0}	{0}	Graph: 0--1--2 3--4 Visited: {0} Queue: [0]
2	Dequeue node	0	[]	{0}	{0}	Visited: {0} Queue: []
3	Check neighbors of 0	0	[]	{0}	{0}	Neighbors: [1]
4	Neighbor 1 not visited, add to queue	0	[1]	{0,1}	{0,1}	Queue: [1] Visited: {0,1}
5	Dequeue node	1	[]	{0,1}	{0,1}	Visited: {0,1} Queue: []
6	Check neighbors of 1	1	[]	{0,1}	{0,1}	Neighbors: [0,2]
7	Neighbor 0 visited, skip	1	[]	{0,1}	{0,1}	Skip 0
8	Neighbor 2 not visited, add to queue	1	[2]	{0,1,2}	{0,1,2}	Queue: [2] Visited: {0,1,2}
9	Dequeue node	2	[]	{0,1,2}	{0,1,2}	Visited: {0,1,2} Queue: []
10	Check neighbors of 2	2	[]	{0,1,2}	{0,1,2}	Neighbors: [1]
11	Neighbor 1 visited, skip	2	[]	{0,1,2}	{0,1,2}	Skip 1
12	Queue empty, connected component complete	-	[]	{0,1,2}	{0,1,2}	Component found: {0,1,2}
13	Next node 1 visited, skip BFS	1	[]	{0,1,2}	{0,1,2}	Skip node 1
14	Next node 2 visited, skip BFS	2	[]	{0,1,2}	{0,1,2}	Skip node 2
15	Next node 3 not visited, start BFS	3	[3]	{0,1,2,3}	{3}	Queue: [3] Visited: {0,1,2,3}
16	Dequeue node	3	[]	{0,1,2,3}	{3}	Visited: {0,1,2,3} Queue: []
17	Check neighbors of 3	3	[]	{0,1,2,3}	{3}	Neighbors: [4]
18	Neighbor 4 not visited, add to queue	3	[4]	{0,1,2,3,4}	{3,4}	Queue: [4] Visited: {0,1,2,3,4}
19	Dequeue node	4	[]	{0,1,2,3,4}	{3,4}	Visited: {0,1,2,3,4} Queue: []
20	Check neighbors of 4	4	[]	{0,1,2,3,4}	{3,4}	Neighbors: [3]
21	Neighbor 3 visited, skip	4	[]	{0,1,2,3,4}	{3,4}	Skip 3
22	Queue empty, connected component complete	-	[]	{0,1,2,3,4}	{3,4}	Component found: {3,4}
23	Next node 4 visited, skip BFS	4	[]	{0,1,2,3,4}	{3,4}	Skip node 4
24	All nodes visited, done	-	[]	{0,1,2,3,4}	{3,4}	All components found

💡 All nodes visited, BFS completed for each connected component

Variable Tracker

Variable	Start	After Step 1	After Step 5	After Step 12	After Step 15	After Step 22	Final
visited	{}	{0}	{0,1}	{0,1,2}	{0,1,2,3}	{0,1,2,3,4}	{0,1,2,3,4}
queue	[]	[0]	[]	[]	[3]	[]	[]
connected_component	{}	{0}	{0,1}	{0,1,2}	{3}	{3,4}	{3,4}

Key Moments - 3 Insights

Why do we skip nodes already in the visited set when starting BFS?

Because those nodes are already part of a connected component found earlier, as shown in steps 13 and 14 where nodes 1 and 2 are skipped.

Why do we add neighbors to the queue only if they are not visited?

To avoid revisiting nodes and infinite loops. This is shown in steps 4 and 8 where neighbors are added only if not visited.

How do we know when one connected component is fully explored?

When the BFS queue becomes empty, meaning no more nodes to visit in this component, as in steps 12 and 22.

Visual Quiz - 3 Questions

Look at the execution table at step 4, what is the state of the queue?

A [1]

B []

C [0,1]

D [2]

💡 Hint

Check the 'Queue' column at step 4 in the execution_table.

At which step does the BFS finish exploring the first connected component?

A Step 10

B Step 12

C Step 15

D Step 22

💡 Hint

Look for the step where the queue becomes empty and the component is marked complete.

If node 3 was already visited before step 15, what would happen?

A BFS would start again from node 3

B Node 3 would be skipped and no new BFS started

C Queue would contain node 3 twice

D Algorithm would fail

💡 Hint

Refer to steps 13 and 14 where visited nodes are skipped.

Concept Snapshot

Connected Components Using BFS:
- Visit each node in graph
- If unvisited, start BFS
- Use queue to explore neighbors
- Mark visited nodes
- BFS ends when queue empty
- Repeat for all nodes
- Each BFS finds one connected component

Full Transcript

This visualization shows how BFS finds connected components in a graph. We start from each unvisited node, add it to a queue, and explore all reachable nodes by visiting neighbors. Each visited node is marked to avoid repeats. When the queue empties, one connected component is fully found. We then move to the next unvisited node and repeat until all nodes are visited. The execution table tracks the queue, visited nodes, and connected components step-by-step, showing how BFS expands and completes each component.

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