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.

Practice

1. What does the term connected components mean in an undirected graph when using BFS?

easy

A. Groups of nodes where each node is reachable from any other node in the same group

B. Nodes that have no edges connected to them

C. The shortest path between two nodes

D. A cycle in the graph

Solution

1. Step 1: Understand connected components in undirected graphs

   Connected components are sets of nodes where each node can be reached from any other node in the same set by following edges.

2. Step 2: Relate BFS to connected components

   BFS explores all nodes reachable from a starting node, thus identifying one connected component at a time.

3. Final Answer:

   Groups of nodes where each node is reachable from any other node in the same group -> Option A

4. Quick Check:

   Connected components = reachable groups [OK]

Hint: Connected components are reachable groups of nodes [OK]

Common Mistakes:

• Confusing connected components with shortest paths
• Thinking isolated nodes are connected components with edges
• Mixing cycles with connected components

2. Which of the following is the correct TypeScript syntax to initialize a queue for BFS traversal?

easy

A. queue = new ArrayQueue();

B. const queue: number[] = [];

C. var queue = []; queue.push(1);

D. let queue = new Queue();

Solution

1. Step 1: Identify correct TypeScript array initialization

   In TypeScript, a queue for BFS can be implemented using an array: const queue: number[] = []; initializes an empty number array.

2. Step 2: Check other options for correctness

   Options A and B use undefined classes ArrayQueue and Queue which are not built-in. var queue = []; queue.push(1); uses var which is discouraged and lacks type annotation.

3. Final Answer:

   const queue: number[] = []; -> Option B

4. Quick Check:

   Array queue initialization = const queue: number[] = [] [OK]

Hint: Use typed arrays for queues in TypeScript [OK]

Common Mistakes:

• Using undefined queue classes
• Using var instead of let/const
• Not typing the queue array

3. Given the following graph adjacency list and BFS-based connected components code, what is the output?

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

function bfsComponents(graph: {[key: number]: number[]}): number[][] {
  const visited = new Set<number>();
  const components: number[][] = [];

  for (const node in graph) {
    const n = Number(node);
    if (!visited.has(n)) {
      const queue: number[] = [n];
      const component: number[] = [];
      visited.add(n);

      while (queue.length > 0) {
        const current = queue.shift()!;
        component.push(current);

        for (const neighbor of graph[current]) {
          if (!visited.has(neighbor)) {
            visited.add(neighbor);
            queue.push(neighbor);
          }
        }
      }
      components.push(component);
    }
  }
  return components;
}

console.log(bfsComponents(graph));

medium

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

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

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

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

Solution

1. Step 1: Analyze graph structure

   The graph has two connected components: nodes 0,1,2 connected together and nodes 3,4 connected together.

2. Step 2: Trace BFS traversal

   Starting from node 0, BFS visits 0, then 1, then 2. Then from node 3, BFS visits 3 and 4. So components are [[0,1,2],[3,4]].

3. Final Answer:

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

4. Quick Check:

   Two connected groups = [[0,1,2],[3,4]] [OK]

Hint: BFS visits all nodes in one component before next [OK]

Common Mistakes:

• Assuming all nodes are one component
• Splitting connected nodes incorrectly
• Confusing node order in output

4. The following BFS code for connected components has a bug. What is the error?

function bfsComponents(graph: {[key: number]: number[]}): number[][] {
  const visited = new Set<number>();
  const components: number[][] = [];

  for (const node in graph) {
    const n = Number(node);
    if (!visited.has(n)) {
      const queue: number[] = [n];
      const component: number[] = [];

      while (queue.length > 0) {
        const current = queue.shift()!;
        component.push(current);

        for (const neighbor of graph[current]) {
          if (!visited.has(neighbor)) {
            queue.push(neighbor);
            visited.add(neighbor);
          }
        }
      }
      components.push(component);
    }
  }
  return components;
}

medium

A. Queue is not initialized properly

B. Visited nodes are never added, causing infinite loops

C. Visited nodes are added after pushing to queue, causing duplicates

D. Component array is not pushed to components

Solution

1. Step 1: Check visited node addition timing

   Visited nodes should be marked as visited before pushing to queue to avoid duplicates.

2. Step 2: Identify the bug in code

   In the code, queue.push(neighbor) happens before visited.add(neighbor), which can cause the same neighbor to be pushed multiple times if visited check is delayed.

3. Final Answer:

   Visited nodes are added after pushing to queue, causing duplicates -> Option C

4. Quick Check:

   Mark visited before queue push to avoid duplicates [OK]

Hint: Add to visited before queue push to prevent repeats [OK]

Common Mistakes:

• Adding visited after queue push
• Not adding visited at all
• Forgetting to push neighbors

5. You have a graph with nodes 0 to 5 and edges: 0-1, 1-2, 3-4. Using BFS to find connected components, what will be the output if the graph is represented as:

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

// BFS connected components function returns array of components

What is the correct connected components output?

hard

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

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

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

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

Solution

1. Step 1: Analyze graph edges and isolated nodes

   Nodes 0,1,2 form one connected component; nodes 3,4 form another; node 5 is isolated with no edges.

2. Step 2: Understand BFS output for connected components

   BFS will find three components: [0,1,2], [3,4], and [5] as a single-node component.

3. Final Answer:

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

4. Quick Check:

   Isolated nodes form their own components [OK]

Hint: Isolated nodes are separate components [OK]

Common Mistakes:

• Ignoring isolated nodes
• Merging all nodes into one component
• Misgrouping connected nodes