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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of BFS Connected Components Count

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

DSA Javascript

function bfs(graph, start, visited) {
  let queue = [start];
  visited.add(start);
  while (queue.length > 0) {
    let node = queue.shift();
    for (let neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
}

function countConnectedComponents(graph) {
  let visited = new Set();
  let count = 0;
  for (let node in graph) {
    if (!visited.has(node)) {
      bfs(graph, node, visited);
      count++;
    }
  }
  return count;
}

const graph = {
  '0': ['1'],
  '1': ['0', '2'],
  '2': ['1'],
  '3': ['4'],
  '4': ['3'],
  '5': []
};

console.log(countConnectedComponents(graph));

A 2

B 1

C 4

D 3

💡 Hint

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

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

❓ Predict Output

intermediate

Output of BFS Traversal Order

What is the order of nodes visited by BFS starting from node '2' in the graph below?

DSA Javascript

function bfsOrder(graph, start) {
  let visited = new Set();
  let queue = [start];
  let order = [];
  visited.add(start);
  while (queue.length > 0) {
    let node = queue.shift();
    order.push(node);
    for (let neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
  return order;
}

const graph = {
  '0': ['1', '2'],
  '1': ['0', '3'],
  '2': ['0', '4'],
  '3': ['1'],
  '4': ['2']
};

console.log(bfsOrder(graph, '2'));

A ['2', '0', '1', '4', '3']

B ['2', '4', '0', '1', '3']

C ['2', '0', '4', '1', '3']

D ['2', '0', '1', '3', '4']

💡 Hint

BFS visits neighbors level by level, starting from the start node.

Starting at '2', neighbors are '0' and '4'. Then from '0', neighbors '1' is visited next, then from '1' neighbor '3'. So order is ['2', '0', '4', '1', '3'].

🔧 Debug

advanced

Identify the error in BFS connected components code

What error will this code produce when counting connected components using BFS?

DSA Javascript

function bfs(graph, start, visited) {
  let queue = [start];
  visited.add(start);
  while (queue.length > 0) {
    let node = queue.shift();
    for (let neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
}

function countConnectedComponents(graph) {
  let visited = new Set();
  let count = 0;
  for (let node in graph) {
    if (!visited.has(node)) {
      bfs(graph, node, visited);
      count++;
    }
  }
  return count;
}

const graph = {
  '0': ['1'],
  '1': ['0', '2'],
  '2': ['1'],
  '3': ['4'],
  '4': ['3'],
  '5': []
};

console.log(countConnectedComponents(graph));

A No error, output is 3

B TypeError: Cannot read property 'Symbol(Symbol.iterator)' of undefined

C SyntaxError: Unexpected token

D ReferenceError: visited is not defined

💡 Hint

Check how keys are used in the graph object and if they match the visited set keys.

The graph keys are numbers but JavaScript converts them to strings when used as object keys. The visited set stores strings, so the code works fine and outputs 3.

❓ Predict Output

advanced

Output of BFS on Disconnected Graph

What is the output of BFS traversal starting from node 'A' on this disconnected graph?

DSA Javascript

function bfsTraversal(graph, start) {
  let visited = new Set();
  let queue = [start];
  let result = [];
  visited.add(start);
  while (queue.length > 0) {
    let node = queue.shift();
    result.push(node);
    for (let neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
  return result;
}

const graph = {
  'A': ['B'],
  'B': ['A'],
  'C': ['D'],
  'D': ['C'],
  'E': []
};

console.log(bfsTraversal(graph, 'A'));

A ['A', 'B']

B ['A', 'B', 'C', 'D', 'E']

C ['A']

D ['B', 'A']

💡 Hint

BFS only visits nodes connected to the start node.

Starting at 'A', BFS visits 'B' next. Nodes 'C', 'D', and 'E' are disconnected and not visited.

🧠 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 Exactly M times, once for each edge

B Equal to the number of connected components in the graph

C Exactly N times, once for each node

D Always 1, BFS covers all nodes

💡 Hint

Think about how BFS explores nodes and when you need to start a new BFS.

Each BFS run explores one connected component fully. So the minimum BFS runs equal the number of connected components.

Practice

1. What does the BFS algorithm help find in an undirected graph when used for connected components?

easy

A. All nodes reachable from a starting node forming one connected component

B. The shortest path between two nodes only

C. The maximum degree of any node in the graph

D. The total number of edges in the graph

Solution

1. Step 1: Understand BFS purpose in connected components

   BFS explores all nodes reachable from a starting node, marking them as part of the same connected component.

2. Step 2: Differentiate BFS from other graph properties

   BFS does not directly find shortest paths between arbitrary nodes, maximum degree, or edge count in this context.

3. Final Answer:

   All nodes reachable from a starting node forming one connected component -> Option A

4. Quick Check:

   BFS finds connected components = D [OK]

Hint: BFS visits all nodes connected to start node [OK]

Common Mistakes:

• Confusing BFS with shortest path only
• Thinking BFS counts edges or degrees
• Mixing BFS with DFS concepts

2. Which of the following is the correct way to initialize a queue for BFS in JavaScript?

easy

A. const queue = new Set(); queue.add(startNode);

B. const queue = []; queue.push(startNode);

C. const queue = {}; queue.enqueue(startNode);

D. const queue = null; queue.push(startNode);

Solution

1. Step 1: Identify correct queue initialization

   In JavaScript, a queue for BFS is commonly implemented using an array with push() to add elements.

2. Step 2: Check other options for errors

   Set does not have push(), object {} has no enqueue method, and null cannot be used as a queue.

3. Final Answer:

   const queue = []; queue.push(startNode); -> Option B

4. Quick Check:

   Array with push() for queue = B [OK]

Hint: Use array with push/pop or shift for BFS queue [OK]

Common Mistakes:

• Using Set instead of array for queue
• Using object without queue methods
• Initializing queue as null

3. What will be the output of the following code snippet that finds connected components using BFS?

const graph = {
  0: [1],
  1: [0, 2],
  2: [1],
  3: [4],
  4: [3]
};

function bfs(start, visited) {
  const queue = [start];
  visited[start] = true;
  const component = [];
  while (queue.length) {
    const node = queue.shift();
    component.push(node);
    for (const neighbor of graph[node]) {
      if (!visited[neighbor]) {
        visited[neighbor] = true;
        queue.push(neighbor);
      }
    }
  }
  return component;
}

const visited = {};
const components = [];
for (const node in graph) {
  if (!visited[node]) {
    components.push(bfs(node, visited));
  }
}
console.log(components);

medium

A. [[0,1,2],[3,4]]

B. [[0,1],[2,3,4]]

C. [[0,1,2,3,4]]

D. [[1,0,2],[4,3]]

Solution

1. Step 1: Trace BFS from node 0

   BFS visits 0, then 1, then 2 forming component [0,1,2].

2. Step 2: Trace BFS from node 3

   Next unvisited node is 3, BFS visits 3 and 4 forming component [3,4].

3. Final Answer:

   [[0,1,2],[3,4]] -> Option A

4. Quick Check:

   Two connected components found = A [OK]

Hint: BFS groups connected nodes in order visited [OK]

Common Mistakes:

• Assuming all nodes in one component
• Mixing order of nodes in components
• Ignoring visited tracking

4. Identify the bug in this BFS connected components code snippet:

function bfs(start, visited, graph) {
  const queue = [start];
  visited[start] = true;
  const component = [];
  while (queue.length > 0) {
    const node = queue.pop();
    component.push(node);
    for (const neighbor of graph[node]) {
      if (!visited[neighbor]) {
        visited[neighbor] = true;
        queue.push(neighbor);
      }
    }
  }
  return component;
}

medium

A. For loop syntax is incorrect

B. Not marking start node as visited

C. Using queue.pop() instead of queue.shift() causes wrong BFS order

D. queue.push(neighbor) should be queue.unshift(neighbor)

Solution

1. Step 1: Check queue operation for BFS

   BFS requires removing from front (queue.shift()), but code uses pop() which removes from end, making it DFS behavior.

2. Step 2: Verify other parts

   Start node is marked visited, for loop syntax is correct, and push() is correct to add neighbors at end.

3. Final Answer:

   Using queue.pop() instead of queue.shift() causes wrong BFS order -> Option C

4. Quick Check:

   pop() breaks BFS order = A [OK]

Hint: Use shift() to dequeue in BFS, pop() is for DFS [OK]

Common Mistakes:

• Confusing pop() with shift() in queue
• Not marking visited nodes
• Incorrect loop syntax

5. Given a graph represented as an adjacency list, how would you modify the BFS connected components algorithm to count the number of connected components without storing the nodes in each component?

hard

A. Use DFS instead of BFS to count components

B. Store all nodes in a global array and count unique nodes after BFS

C. Count edges visited during BFS to find components

D. Increment a counter each time BFS starts from an unvisited node, without collecting nodes

Solution

1. Step 1: Understand BFS role in counting components

   Each BFS call from an unvisited node explores one connected component fully.

2. Step 2: Modify BFS to count components

   Instead of storing nodes, just increment a counter when BFS starts from an unvisited node.

3. Final Answer:

   Increment a counter each time BFS starts from an unvisited node, without collecting nodes -> Option D

4. Quick Check:

   Count BFS starts = connected components [OK]

Hint: Count BFS calls from unvisited nodes for components [OK]

Common Mistakes:

• Storing all nodes unnecessarily
• Confusing edge count with component count
• Switching BFS to DFS without reason