Why Connected Components Using BFS in DSA Typescript?

The Big Idea

Discover how a simple search method can untangle complex networks effortlessly!

The Scenario

Imagine you have a map of cities connected by roads. You want to find groups of cities where you can travel between any two cities without leaving the group. Doing this by checking every possible path manually is like trying to find all friend groups in a large party by asking everyone individually.

The Problem

Manually checking connections is slow and confusing. You might miss some cities or count the same group multiple times. It's easy to get lost in the details and make mistakes, especially when the map is big.

The Solution

Using Breadth-First Search (BFS) helps you explore each group step-by-step, visiting all connected cities before moving to the next group. This method is organized and ensures you find every group exactly once, saving time and avoiding errors.

Before vs After

✗ Before

for each city:
  for each other city:
    check if connected
  mark group
repeat for all cities

✓ After

for each city:
  if not visited:
    BFS(city)
    mark connected component

What It Enables

This lets you quickly find all connected groups in a network, enabling tasks like social network analysis, cluster detection, and network reliability checks.

Real Life Example

Social media platforms use this to find friend circles where everyone is connected, helping suggest new friends or communities.

Key Takeaways

Manual checking is slow and error-prone.

BFS explores connected groups efficiently and clearly.

Finding connected components helps analyze networks and clusters.

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