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.

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