Connected Components Using BFS in DSA Javascript - Execution Trace

Concept Flow - Connected Components Using BFS

Start with all nodes unvisited

↓

Pick an unvisited node

↓

Initialize queue with this node

↓

While queue not empty

↓

Dequeue node

↓

Mark node visited

↓

Add unvisited neighbors to queue

↓

Repeat until queue empty

↓

One connected component found

↓

Repeat for next unvisited node

↓

All nodes visited, done

Start from an unvisited node, use BFS to find all nodes connected to it, mark them visited, then repeat for other unvisited nodes until all are covered.

Execution Sample

DSA Javascript

const graph = {
  0: [1],
  1: [0, 2],
  2: [1],
  3: [4],
  4: [3]
};

// BFS to find connected components

This code finds connected groups of nodes in a graph using BFS.

Execution Table

Step	Operation	Current Node	Queue	Visited Set	Connected Component	Graph State
1	Start BFS from node 0	-	[0]	{}	[]	Graph with nodes 0-4
2	Dequeue node	0	[]	{}	[]	Graph with nodes 0-4
3	Mark node visited	0	[]	{0}	[0]	Graph with nodes 0-4
4	Add neighbors of 0 to queue	0	[1]	{0}	[0]	Graph with nodes 0-4
5	Dequeue node	1	[]	{0}	[0]	Graph with nodes 0-4
6	Mark node visited	1	[]	{0,1}	[0,1]	Graph with nodes 0-4
7	Add neighbors of 1 to queue	1	[2]	{0,1}	[0,1]	Graph with nodes 0-4
8	Dequeue node	2	[]	{0,1}	[0,1]	Graph with nodes 0-4
9	Mark node visited	2	[]	{0,1,2}	[0,1,2]	Graph with nodes 0-4
10	Add neighbors of 2 to queue	2	[]	{0,1,2}	[0,1,2]	Graph with nodes 0-4
11	Queue empty, component complete	-	[]	{0,1,2}	[0,1,2]	Graph with nodes 0-4
12	Start BFS from next unvisited node 3	-	[3]	{0,1,2}	[]	Graph with nodes 0-4
13	Dequeue node	3	[]	{0,1,2}	[]	Graph with nodes 0-4
14	Mark node visited	3	[]	{0,1,2,3}	[3]	Graph with nodes 0-4
15	Add neighbors of 3 to queue	3	[4]	{0,1,2,3}	[3]	Graph with nodes 0-4
16	Dequeue node	4	[]	{0,1,2,3}	[3]	Graph with nodes 0-4
17	Mark node visited	4	[]	{0,1,2,3,4}	[3,4]	Graph with nodes 0-4
18	Add neighbors of 4 to queue	4	[]	{0,1,2,3,4}	[3,4]	Graph with nodes 0-4
19	Queue empty, component complete	-	[]	{0,1,2,3,4}	[3,4]	Graph with nodes 0-4
20	All nodes visited, BFS ends	-	[]	{0,1,2,3,4}	Components: [[0,1,2],[3,4]]	Graph with nodes 0-4

💡 All nodes visited, no unvisited nodes remain to start BFS

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 9	After Step 11	After Step 14	After Step 17	After Step 19	Final
Queue	[]	[]	[]	[]	[]	[]	[]	[]	[]
Visited Set	{}	{0}	{0,1}	{0,1,2}	{0,1,2}	{0,1,2,3}	{0,1,2,3,4}	{0,1,2,3,4}	{0,1,2,3,4}
Connected Component	[]	[0]	[0,1]	[0,1,2]	[0,1,2]	[3]	[3,4]	[3,4]	[[0,1,2],[3,4]]

Key Moments - 3 Insights

Why do we start BFS only from unvisited nodes?

Because BFS from a visited node would repeat work. The execution_table shows at Step 12 we pick node 3 only after nodes 0,1,2 are visited.

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

To avoid infinite loops and repeated visits. See Steps 4, 7, 10 where only unvisited neighbors are added to the queue.

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

When the queue becomes empty (Steps 11 and 19), BFS for that component ends, meaning all connected nodes are visited.

Visual Quiz - 3 Questions

Look at the execution_table at Step 9, what nodes are in the visited set?

A {0,1,2}

B {0,1}

C {0}

D {}

💡 Hint

Check the 'Visited Set' column at Step 9 in the execution_table.

At which step does BFS start for the second connected component?

A Step 11

B Step 14

C Step 12

D Step 20

💡 Hint

Look for the step where the queue is initialized with node 3 in the execution_table.

If node 4 had an extra neighbor 5 (unconnected to others), how would the final visited set change?

A {0,1,2,3,4}

B {0,1,2,3,4,5}

C {5}

D {}

💡 Hint

Adding neighbor 5 means BFS will visit it, so it will be added to the visited set.

Concept Snapshot

Connected Components Using BFS:
- Start BFS from any unvisited node.
- Use a queue to explore neighbors.
- Mark nodes visited when dequeued.
- Add only unvisited neighbors to queue.
- When queue empties, one component is found.
- Repeat until all nodes visited.

Full Transcript

Connected Components Using BFS means finding groups of nodes connected together in a graph. We start from an unvisited node, put it in a queue, and visit nodes by removing from the queue. Each visited node is marked so we don't visit again. We add neighbors to the queue only if they are not visited. When the queue is empty, we have found one connected group. Then we pick another unvisited node and repeat. This continues until all nodes are visited. The execution table shows step-by-step how nodes are visited, queues updated, and connected components formed.

Practice

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

easy

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

B. The shortest path between two nodes only

C. The maximum degree of any node in the graph

D. The total number of edges in the graph

Solution

1. Step 1: Understand BFS purpose in connected components

   BFS explores all nodes reachable from a starting node, marking them as part of the same connected component.

2. Step 2: Differentiate BFS from other graph properties

   BFS does not directly find shortest paths between arbitrary nodes, maximum degree, or edge count in this context.

3. Final Answer:

   All nodes reachable from a starting node forming one connected component -> Option A

4. Quick Check:

   BFS finds connected components = D [OK]

Hint: BFS visits all nodes connected to start node [OK]

Common Mistakes:

• Confusing BFS with shortest path only
• Thinking BFS counts edges or degrees
• Mixing BFS with DFS concepts

2. Which of the following is the correct way to initialize a queue for BFS in JavaScript?

easy

A. const queue = new Set(); queue.add(startNode);

B. const queue = []; queue.push(startNode);

C. const queue = {}; queue.enqueue(startNode);

D. const queue = null; queue.push(startNode);

Solution

1. Step 1: Identify correct queue initialization

   In JavaScript, a queue for BFS is commonly implemented using an array with push() to add elements.

2. Step 2: Check other options for errors

   Set does not have push(), object {} has no enqueue method, and null cannot be used as a queue.

3. Final Answer:

   const queue = []; queue.push(startNode); -> Option B

4. Quick Check:

   Array with push() for queue = B [OK]

Hint: Use array with push/pop or shift for BFS queue [OK]

Common Mistakes:

• Using Set instead of array for queue
• Using object without queue methods
• Initializing queue as null

3. What will be the output of the following code snippet that finds connected components using BFS?

const graph = {
  0: [1],
  1: [0, 2],
  2: [1],
  3: [4],
  4: [3]
};

function bfs(start, visited) {
  const queue = [start];
  visited[start] = true;
  const component = [];
  while (queue.length) {
    const node = queue.shift();
    component.push(node);
    for (const neighbor of graph[node]) {
      if (!visited[neighbor]) {
        visited[neighbor] = true;
        queue.push(neighbor);
      }
    }
  }
  return component;
}

const visited = {};
const components = [];
for (const node in graph) {
  if (!visited[node]) {
    components.push(bfs(node, visited));
  }
}
console.log(components);

medium

A. [[0,1,2],[3,4]]

B. [[0,1],[2,3,4]]

C. [[0,1,2,3,4]]

D. [[1,0,2],[4,3]]

Solution

1. Step 1: Trace BFS from node 0

   BFS visits 0, then 1, then 2 forming component [0,1,2].

2. Step 2: Trace BFS from node 3

   Next unvisited node is 3, BFS visits 3 and 4 forming component [3,4].

3. Final Answer:

   [[0,1,2],[3,4]] -> Option A

4. Quick Check:

   Two connected components found = A [OK]

Hint: BFS groups connected nodes in order visited [OK]

Common Mistakes:

• Assuming all nodes in one component
• Mixing order of nodes in components
• Ignoring visited tracking

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

function bfs(start, visited, graph) {
  const queue = [start];
  visited[start] = true;
  const component = [];
  while (queue.length > 0) {
    const node = queue.pop();
    component.push(node);
    for (const neighbor of graph[node]) {
      if (!visited[neighbor]) {
        visited[neighbor] = true;
        queue.push(neighbor);
      }
    }
  }
  return component;
}

medium

A. For loop syntax is incorrect

B. Not marking start node as visited

C. Using queue.pop() instead of queue.shift() causes wrong BFS order

D. queue.push(neighbor) should be queue.unshift(neighbor)

Solution

1. Step 1: Check queue operation for BFS

   BFS requires removing from front (queue.shift()), but code uses pop() which removes from end, making it DFS behavior.

2. Step 2: Verify other parts

   Start node is marked visited, for loop syntax is correct, and push() is correct to add neighbors at end.

3. Final Answer:

   Using queue.pop() instead of queue.shift() causes wrong BFS order -> Option C

4. Quick Check:

   pop() breaks BFS order = A [OK]

Hint: Use shift() to dequeue in BFS, pop() is for DFS [OK]

Common Mistakes:

• Confusing pop() with shift() in queue
• Not marking visited nodes
• Incorrect loop syntax

5. Given a graph represented as an adjacency list, how would you modify the BFS connected components algorithm to count the number of connected components without storing the nodes in each component?

hard

A. Use DFS instead of BFS to count components

B. Store all nodes in a global array and count unique nodes after BFS

C. Count edges visited during BFS to find components

D. Increment a counter each time BFS starts from an unvisited node, without collecting nodes

Solution

1. Step 1: Understand BFS role in counting components

   Each BFS call from an unvisited node explores one connected component fully.

2. Step 2: Modify BFS to count components

   Instead of storing nodes, just increment a counter when BFS starts from an unvisited node.

3. Final Answer:

   Increment a counter each time BFS starts from an unvisited node, without collecting nodes -> Option D

4. Quick Check:

   Count BFS starts = connected components [OK]

Hint: Count BFS calls from unvisited nodes for components [OK]

Common Mistakes:

• Storing all nodes unnecessarily
• Confusing edge count with component count
• Switching BFS to DFS without reason