Connected Components Using BFS in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the visited set before BFS.

DSA Typescript

const visited = new Set[1]();

Drag options to blanks, or click blank then click option'

A<string>

B()

C[]

D{}

Attempts:

3 left

💡 Hint

Common Mistakes

Using brackets [] instead of parentheses () to create a Set.

Trying to initialize Set with curly braces {} which is an object literal.

We create a new Set by calling new Set() with parentheses.

2fill in blank

medium

Complete the code to add the starting node to the queue in BFS.

DSA Typescript

queue.push[1](startNode);

Drag options to blanks, or click blank then click option'

A.add

B.enqueue

C.push

D()

Attempts:

3 left

💡 Hint

Common Mistakes

Using .add which is for Sets, not arrays.

Writing queue.push without parentheses, which is a function reference, not a call.

We call the push method with parentheses and the node as argument: push(startNode).

3fill in blank

hard

Fix the error in the BFS loop condition to process nodes while queue is not empty.

DSA Typescript

while (queue[1] 0) {

Drag options to blanks, or click blank then click option'

A>

B==

C!==

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using == 0 which stops immediately.

Using < 0 which is never true for length.

We check if queue length is greater than 0 to continue processing nodes.

4fill in blank

hard

Fill both blanks to check if a neighbor is unvisited and add it to the queue.

DSA Typescript

if (!visited.has(neighbor) && !queue[1].includes(neighbor)) {
  queue[2](neighbor);
}

Drag options to blanks, or click blank then click option'

A.push

B.pop

D.shift

Attempts:

3 left

💡 Hint

Common Mistakes

Using pop or shift to add elements instead of push.

Checking queue with wrong method instead of includes.

We check if neighbor is not in queue using includes, then add it with push.

5fill in blank

hard

Fill all three blanks to complete the BFS function that finds connected components.

DSA Typescript

function bfs(graph: Map<string, string[]>): string[][] {
  const visited = new Set<string>();
  const components: string[][] = [];
  for (const node of graph.keys()) {
    if (!visited.has(node)) {
      const queue = [node];
      const component: string[] = [];
      while (queue.length [1] 0) {
        const current = queue[2]();
        if (!visited.has(current)) {
          visited.add(current);
          component.push(current);
          for (const neighbor of graph.get(current) || []) {
            if (!visited.has(neighbor)) {
              queue.push(neighbor);
            }
          }
        }
      }
      components.push(component);
    }
  }
  return components;
}

Drag options to blanks, or click blank then click option'

A>

Bshift

Cpop

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using pop() removes last element, which is DFS behavior.

Using < 0 or == 0 in loop condition stops loop incorrectly.

We loop while queue length > 0, remove the first element with shift. pop is a distractor here.

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