Connected Components Using BFS in DSA Typescript - 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

↓

Enqueue all unvisited neighbors

↓

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 Typescript

const graph = {
  0: [1],
  1: [0, 2],
  2: [1],
  3: [4],
  4: [3]
};
// Find connected components using BFS

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	N/A	[0]	{}	[]	{0:[1],1:[0,2],2:[1],3:[4],4:[3]}
2	Dequeue node	0	[]	{}	[]	{0:[1],1:[0,2],2:[1],3:[4],4:[3]}
3	Mark node visited	0	[]	{0}	[0]	{0:[1],1:[0,2],2:[1],3:[4],4:[3]}
4	Enqueue unvisited neighbors	0	[1]	{0}	[0]	{0:[1],1:[0,2],2:[1],3:[4],4:[3]}
5	Dequeue node	1	[]	{0}	[0]	{0:[1],1:[0,2],2:[1],3:[4],4:[3]}
6	Mark node visited	1	[]	{0,1}	[0,1]	{0:[1],1:[0,2],2:[1],3:[4],4:[3]}
7	Enqueue unvisited neighbors	1	[2]	{0,1}	[0,1]	{0:[1],1:[0,2],2:[1],3:[4],4:[3]}
8	Dequeue node	2	[]	{0,1}	[0,1]	{0:[1],1:[0,2],2:[1],3:[4],4:[3]}
9	Mark node visited	2	[]	{0,1,2}	[0,1,2]	{0:[1],1:[0,2],2:[1],3:[4],4:[3]}
10	Enqueue unvisited neighbors	2	[]	{0,1,2}	[0,1,2]	{0:[1],1:[0,2],2:[1],3:[4],4:[3]}
11	Queue empty, component complete	N/A	[]	{0,1,2}	[0,1,2]	{0:[1],1:[0,2],2:[1],3:[4],4:[3]}
12	Start BFS from next unvisited node 3	N/A	[3]	{0,1,2}	[]	{0:[1],1:[0,2],2:[1],3:[4],4:[3]}
13	Dequeue node	3	[]	{0,1,2}	[]	{0:[1],1:[0,2],2:[1],3:[4],4:[3]}
14	Mark node visited	3	[]	{0,1,2,3}	[3]	{0:[1],1:[0,2],2:[1],3:[4],4:[3]}
15	Enqueue unvisited neighbors	3	[4]	{0,1,2,3}	[3]	{0:[1],1:[0,2],2:[1],3:[4],4:[3]}
16	Dequeue node	4	[]	{0,1,2,3}	[3]	{0:[1],1:[0,2],2:[1],3:[4],4:[3]}
17	Mark node visited	4	[]	{0,1,2,3,4}	[3,4]	{0:[1],1:[0,2],2:[1],3:[4],4:[3]}
18	Enqueue unvisited neighbors	4	[]	{0,1,2,3,4}	[3,4]	{0:[1],1:[0,2],2:[1],3:[4],4:[3]}
19	Queue empty, component complete	N/A	[]	{0,1,2,3,4}	[3,4]	{0:[1],1:[0,2],2:[1],3:[4],4:[3]}
20	All nodes visited, done	N/A	[]	{0,1,2,3,4}	[[0,1,2],[3,4]]	{0:[1],1:[0,2],2:[1],3:[4],4:[3]}

💡 All nodes visited, BFS completed for all connected components

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 9	After Step 11	After Step 14	After Step 17	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}
Connected Component	[]	[0]	[0,1]	[0,1,2]	[0,1,2]	[3]	[3,4]	[[0,1,2],[3,4]]

Key Moments - 3 Insights

Why do we start BFS only from unvisited nodes?

Because nodes already visited belong to a connected component found earlier, starting BFS from them would repeat work. See steps 1 and 12 where BFS starts only from unvisited nodes.

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

To avoid revisiting nodes and infinite loops in cycles. This is shown in steps 4, 7, 15, and 18 where only unvisited neighbors are enqueued.

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

When the BFS queue becomes empty, meaning no more connected nodes to visit. This happens at steps 11 and 19.

Visual Quiz - 3 Questions

Look at the execution table at step 6. What is the visited set after marking node 1?

A {0,1}

B {1}

C {0}

D {}

💡 Hint

Check the 'Visited Set' column at step 6 in the execution table.

At which step does the BFS queue become empty for the first connected component?

A Step 9

B Step 11

C Step 7

D Step 5

💡 Hint

Look for when the 'Queue' column is empty and the component is complete in the execution table.

If node 3 had an additional neighbor 2, how would the visited set change after step 14?

A {0,1,2,3}

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

C {0,1,3}

D {3,4}

💡 Hint

Since node 2 is already visited before step 14, it won't be added again. Check variable_tracker for visited set progression.

Concept Snapshot

Connected Components Using BFS:
- Start BFS from any unvisited node
- Use a queue to explore neighbors
- Mark nodes visited when dequeued
- Enqueue only unvisited neighbors
- When queue empties, one component is found
- Repeat for all unvisited nodes
- Result: list of connected components

Full Transcript

Connected Components Using BFS means finding groups of nodes where each node can reach any other in the group. We start from an unvisited node, add it to a queue, and explore neighbors using BFS. Each visited node is marked to avoid repeats. When the queue empties, we have found one connected component. We then repeat for other unvisited nodes until all nodes are visited. The execution table shows each step: starting BFS, dequeuing nodes, marking visited, adding neighbors, and completing components. The variable tracker shows how the queue, visited set, and components change over time. Key moments clarify why we only start BFS from unvisited nodes, why neighbors are added only if unvisited, and how we know when a component is complete. The visual quiz tests understanding of visited sets, queue emptiness, and effects of graph changes.