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.