Connected Components Using BFS in DSA Typescript - Build from Scratch

Connected Components Using BFS

📖 Scenario: Imagine you have a map of cities connected by roads. You want to find groups of cities where each city is reachable from any other city in the same group by traveling along these roads.

🎯 Goal: Build a program that finds all connected groups of cities using Breadth-First Search (BFS).

📋 What You'll Learn

Create a graph as an adjacency list with exact city connections

Create a visited set to track visited cities

Use BFS to find connected components

Print each connected component as a list of city names

💡 Why This Matters

🌍 Real World

Finding connected components helps in social networks to find friend groups, in maps to find reachable areas, and in biology to find connected molecules.

💼 Career

Understanding BFS and connected components is essential for software engineers working on graph problems, network analysis, and data clustering.

1

Create the graph as an adjacency list

Create a variable called graph as a Record<string, string[]> with these exact entries: 'A': ['B'], 'B': ['A', 'C'], 'C': ['B'], 'D': ['E'], 'E': ['D'], 'F': []

DSA Typescript

# Your code here

Hint

Use a TypeScript object where keys are city names and values are arrays of connected cities.

2

Create a visited set to track visited cities

Create a variable called visited as a Set<string> and initialize it as empty.

DSA Typescript

const graph: Record = {
  'A': ['B'],
  'B': ['A', 'C'],
  'C': ['B'],
  'D': ['E'],
  'E': ['D'],
  'F': []
};

// Your code here

Hint

Use new Set() to create an empty set for visited cities.

3

Implement BFS to find connected components

Create a function called bfs that takes a start city of type string and returns an array of strings representing the connected component. Use a queue and the visited set to track visited cities.

DSA Typescript

const graph: Record = {
  'A': ['B'],
  'B': ['A', 'C'],
  'C': ['B'],
  'D': ['E'],
  'E': ['D'],
  'F': []
};

const visited: Set = new Set();

// Your code here

Hint

Use a queue to explore neighbors and add unvisited cities to the queue and visited set.

4

Find and print all connected components

Create an array called components. Use a for loop with variable city over Object.keys(graph). If city is not in visited, call bfs(city) and push the result to components. Finally, print components.

DSA Typescript

const graph: Record = {
  'A': ['B'],
  'B': ['A', 'C'],
  'C': ['B'],
  'D': ['E'],
  'E': ['D'],
  'F': []
};

const visited: Set = new Set();

function bfs(start: string): string[] {
  const queue: string[] = [start];
  const component: string[] = [];
  visited.add(start);

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

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

  return component;
}

// Your code here

Hint

Loop over all cities, run BFS on unvisited ones, and collect the connected components.