BFS Breadth First Search on Graph in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of BFS traversal on a simple graph

What is the output of the BFS traversal starting from node 0 in the given graph?

DSA Typescript

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

function bfs(start: number, graph: Map<number, number[]>): number[] {
  const visited = new Set<number>();
  const queue: number[] = [];
  const order: number[] = [];

  visited.add(start);
  queue.push(start);

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

  return order;
}

console.log(bfs(0, graph));

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

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

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

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

💡 Hint

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

BFS starts at node 0, visits neighbors 1 and 2 in order, then visits neighbors of 1 (which is 3), then neighbors of 2 (which is 4). So the order is 0, 1, 2, 3, 4.

🧠 Conceptual

intermediate

Number of nodes visited in BFS

Given a graph with 6 nodes (0 to 5) and edges: 0-1, 0-2, 1-3, 2-4, 4-5, how many nodes will BFS visit starting from node 0?

A 4

B 5

C 6

D 3

💡 Hint

BFS visits all nodes reachable from the start node.

All nodes 0,1,2,3,4,5 are reachable from 0, so BFS visits all 6 nodes.

❓ Predict Output

advanced

BFS traversal order with disconnected graph

What is the output of BFS starting from node 0 on this graph with disconnected components?

DSA Typescript

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

function bfs(start: number, graph: Map<number, number[]>): number[] {
  const visited = new Set<number>();
  const queue: number[] = [];
  const order: number[] = [];

  visited.add(start);
  queue.push(start);

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

  return order;
}

console.log(bfs(0, graph));

A [0, 1]

B [0, 1, 2, 3]

C [0]

D [1, 0]

💡 Hint

BFS only visits nodes reachable from the start node.

Nodes 2 and 3 are disconnected from 0, so BFS starting at 0 visits only 0 and 1.

🔧 Debug

advanced

Identify the error in BFS implementation

What error will this BFS code produce when run?

DSA Typescript

function bfs(start: number, graph: Map<number, number[]>): number[] {
  const visited = new Set<number>();
  const queue: number[] = [];
  const order: number[] = [];

  queue.push(start);

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

  return order;
}

console.log(bfs(0, new Map([[0, [1]], [1, [0]]])));

A Runtime error: Cannot read property 'get' of undefined

B Infinite loop because start node is never marked visited

C SyntaxError due to missing colon

D The code runs correctly and outputs [0, 1]

💡 Hint

Check if the start node is marked visited before adding to queue.

The start node is added to the queue but never marked visited, so it can be re-added repeatedly causing an infinite loop.

🚀 Application

expert

Shortest path length using BFS

Given the graph below, what is the shortest path length from node 0 to node 5 using BFS? Edges: 0-1, 0-2, 1-3, 2-4, 4-5

DSA Typescript

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

function bfsShortestPath(start: number, end: number, graph: Map<number, number[]>): number {
  const visited = new Set<number>();
  const queue: Array<{node: number; dist: number}> = [];

  visited.add(start);
  queue.push({node: start, dist: 0});

  while (queue.length > 0) {
    const {node, dist} = queue.shift()!;
    if (node === end) {
      return dist;
    }
    for (const neighbor of graph.get(node) ?? []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push({node: neighbor, dist: dist + 1});
      }
    }
  }

  return -1; // if no path found
}

console.log(bfsShortestPath(0, 5, graph));

A 2

B 4

C -1

D 3

💡 Hint

Trace the shortest path step by step from 0 to 5.

The shortest path is 0 -> 2 -> 4 -> 5, which has length 3 edges.