Connected Components Using BFS in DSA Typescript

Mental Model

We find groups of nodes where each node can reach every other node in the same group by walking through edges using BFS.

Analogy: Imagine islands connected by bridges. Each island group you can visit by walking over bridges without swimming is a connected component.

Graph:
0 -> 1
|
2

Components:
[0,1,2] and [3]

0 -> 1 -> null
|
2 -> null
3 -> null

Dry Run Walkthrough

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

Goal: Find all connected groups of nodes using BFS

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

Queue: [0]
Visited: {0}
Components: []

Why: We pick an unvisited node to find its connected group

Step 2: Dequeue 0, enqueue neighbors 1 and 2, mark visited

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

Why: Explore all nodes connected to 0

Step 3: Dequeue 1, no new neighbors to add

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

Why: 1's neighbors are already visited

Step 4: Dequeue 2, no new neighbors to add

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

Why: Finished exploring component containing 0

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

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

Why: Find next connected component

Step 6: Dequeue 3, no neighbors

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

Why: 3 is isolated, forms its own component

Result:

Components: [0 -> 1 -> 2 -> null], [3 -> null]

Annotated Code

DSA Typescript

class Graph {
  adjacencyList: Map<number, number[]>;

  constructor() {
    this.adjacencyList = new Map();
  }

  addEdge(u: number, v: number) {
    if (!this.adjacencyList.has(u)) this.adjacencyList.set(u, []);
    if (!this.adjacencyList.has(v)) this.adjacencyList.set(v, []);
    this.adjacencyList.get(u)!.push(v);
    this.adjacencyList.get(v)!.push(u);
  }

  bfs(start: number, visited: Set<number>): number[] {
    const queue: number[] = [];
    const component: number[] = [];
    queue.push(start);
    visited.add(start);

    while (queue.length > 0) {
      const node = queue.shift()!; // dequeue
      component.push(node);
      for (const neighbor of this.adjacencyList.get(node) || []) {
        if (!visited.has(neighbor)) {
          queue.push(neighbor); // enqueue
          visited.add(neighbor); // mark visited
        }
      }
    }
    return component;
  }

  connectedComponents(): number[][] {
    const visited = new Set<number>();
    const components: number[][] = [];

    for (const node of this.adjacencyList.keys()) {
      if (!visited.has(node)) {
        const comp = this.bfs(node, visited); // find component
        components.push(comp);
      }
    }
    return components;
  }
}

// Driver code
const graph = new Graph();
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.adjacencyList.set(3, []); // isolated node

const components = graph.connectedComponents();
for (const comp of components) {
  console.log(comp.join(' -> ') + ' -> null');
}

queue.push(start); visited.add(start);

Initialize BFS queue and mark start node visited

const node = queue.shift()!; component.push(node);

Dequeue node and add to current component

for (const neighbor of this.adjacencyList.get(node) || []) { if (!visited.has(neighbor)) { queue.push(neighbor); visited.add(neighbor); } }

Enqueue unvisited neighbors and mark them visited

for (const node of this.adjacencyList.keys()) { if (!visited.has(node)) { const comp = this.bfs(node, visited); components.push(comp); } }

Iterate all nodes to find all connected components

Output

0 -> 1 -> 2 -> null

3 -> null

Complexity Analysis

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

Space: O(V) for the visited set, queue, and components storage

vs Alternative: Compared to DFS, BFS has similar time and space complexity; BFS is often easier to implement for shortest path or level order traversal.

Edge Cases

Graph with isolated nodes

Each isolated node forms its own connected component

DSA Typescript

if (!visited.has(node)) {

Empty graph (no nodes)

Returns empty list of components

DSA Typescript

for (const node of this.adjacencyList.keys()) {

Graph with single node

Returns one component with that single node

DSA Typescript

queue.push(start);
visited.add(start);

When to Use This Pattern

When you need to find groups of connected nodes in a graph, use BFS to explore each group fully before moving to the next.

Common Mistakes

Mistake: Not marking nodes as visited before enqueueing causes repeated visits
Fix: Mark nodes visited immediately when enqueueing to avoid duplicates

Summary

Finds all groups of nodes connected by edges using BFS traversal.

Use when you want to identify separate connected parts in an undirected graph.

The key is to explore all reachable nodes from a start node before moving to the next unvisited node.

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