Connected Components Using BFS in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of BFS Connected Components Count

What is the output of the following TypeScript code that counts connected components using BFS?

DSA Typescript

function countConnectedComponents(graph: Map<number, number[]>): number {
  const visited = new Set<number>();
  let count = 0;

  for (const node of graph.keys()) {
    if (!visited.has(node)) {
      count++;
      const queue: number[] = [node];
      visited.add(node);

      while (queue.length > 0) {
        const current = queue.shift()!;
        for (const neighbor of graph.get(current) || []) {
          if (!visited.has(neighbor)) {
            visited.add(neighbor);
            queue.push(neighbor);
          }
        }
      }
    }
  }

  return count;
}

const graph = new Map<number, number[]>([
  [1, [2]],
  [2, [1, 3]],
  [3, [2]],
  [4, [5]],
  [5, [4]],
  [6, []]
]);

console.log(countConnectedComponents(graph));

A 3

B 2

C 4

D 1

💡 Hint

Count how many groups of nodes are connected without crossing to other groups.

The graph has three connected components: {1,2,3}, {4,5}, and {6}. So the output is 3.

❓ Predict Output

intermediate

Output of BFS Traversal Order in Connected Components

What is the output array printed by this BFS traversal over all connected components?

DSA Typescript

function bfsTraversal(graph: Map<number, number[]>): number[] {
  const visited = new Set<number>();
  const result: number[] = [];

  for (const node of graph.keys()) {
    if (!visited.has(node)) {
      const queue: number[] = [node];
      visited.add(node);

      while (queue.length > 0) {
        const current = queue.shift()!;
        result.push(current);
        for (const neighbor of graph.get(current) || []) {
          if (!visited.has(neighbor)) {
            visited.add(neighbor);
            queue.push(neighbor);
          }
        }
      }
    }
  }

  return result;
}

const graph = new Map<number, number[]>([
  [1, [2]],
  [2, [1, 3]],
  [3, [2]],
  [4, [5]],
  [5, [4]],
  [6, []]
]);

console.log(bfsTraversal(graph));

A [1, 2, 3, 4, 5, 6]

B [1, 3, 2, 4, 5, 6]

C [1, 2, 3, 5, 4, 6]

D [6, 4, 5, 1, 2, 3]

💡 Hint

BFS visits neighbors level by level starting from the smallest node key.

The BFS starts at node 1, visits 2 and 3, then moves to node 4's component (4,5), then node 6 alone.

🔧 Debug

advanced

Identify the error in BFS connected components code

What error will this TypeScript code produce when run?

DSA Typescript

function countComponents(graph: Map<number, number[]>): number {
  const visited = new Set<number>();
  let count = 0;

  for (const node of graph.keys()) {
    if (!visited.has(node)) {
      count++;
      const queue: number[] = [node];

      while (queue.length > 0) {
        const current = queue.pop()!;
        visited.add(current);
        for (const neighbor of graph.get(current) || []) {
          if (!visited.has(neighbor)) {
            queue.push(neighbor);
          }
        }
      }
    }
  }

  return count;
}

const graph = new Map<number, number[]>([
  [1, [2]],
  [2, [1, 3]],
  [3, [2]],
  [4, [5]],
  [5, [4]],
  [6, []]
]);

console.log(countComponents(graph));

A The code outputs 0 because visited nodes are never added

B The code throws a runtime error due to empty queue access

C The code runs correctly and outputs 3

D The code outputs 1 because BFS is replaced by DFS using pop()

💡 Hint

Check how queue.pop() changes the traversal order compared to queue.shift(). Does it affect the count?

Using pop() turns the traversal into DFS (stack behavior), but the logic still correctly marks nodes visited when dequeued and only enqueues unvisited neighbors. For this graph, all components are properly identified, outputting 3. No runtime error or incorrect count.

❓ Predict Output

advanced

Output of BFS with disconnected nodes and empty adjacency

What is the output of this code that counts connected components in a graph with isolated nodes?

DSA Typescript

function countComponents(graph: Map<number, number[]>): number {
  const visited = new Set<number>();
  let count = 0;

  for (const node of graph.keys()) {
    if (!visited.has(node)) {
      count++;
      const queue: number[] = [node];
      visited.add(node);

      while (queue.length > 0) {
        const current = queue.shift()!;
        for (const neighbor of graph.get(current) || []) {
          if (!visited.has(neighbor)) {
            visited.add(neighbor);
            queue.push(neighbor);
          }
        }
      }
    }
  }

  return count;
}

const graph = new Map<number, number[]>([
  [1, []],
  [2, []],
  [3, []],
  [4, []]
]);

console.log(countComponents(graph));

A 1

B Error: Cannot read property of undefined

C 0

D 4

💡 Hint

Each node is isolated, so each is its own component.

Since no nodes are connected, each node forms a separate connected component. There are 4 nodes, so output is 4.

🧠 Conceptual

expert

Minimum BFS Runs to Find All Connected Components

Given an undirected graph with N nodes and M edges, what is the minimum number of BFS runs needed to find all connected components?

A Equal to the number of nodes N

B Equal to the number of connected components

C Always 1, since BFS covers all nodes

D Equal to the number of edges M

💡 Hint

Each BFS run starts from an unvisited node and covers one connected component.

Each BFS run explores one connected component fully. To cover all components, BFS must run once per component.