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.

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