BFS Breadth First Search on Graph in DSA Javascript - 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 'A' in the given graph?

DSA Javascript

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

function bfs(graph, start) {
  const queue = [start];
  const visited = new Set();
  const result = [];

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

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

A ["A", "B", "C", "D", "E", "F"]

B ["A", "C", "B", "F", "D", "E"]

C ["A", "B", "C", "E", "D", "F"]

D ["A", "C", "B", "D", "E", "F"]

💡 Hint

Remember BFS visits nodes level by level, starting from the start node and exploring neighbors before going deeper.

BFS starts at 'A', visits neighbors 'B' and 'C' in order, then visits neighbors of 'B' ('D', 'E'), then neighbors of 'C' ('F'). The order is A, B, C, D, E, F.

❓ Predict Output

intermediate

BFS traversal output with disconnected graph

What is the output of BFS traversal starting from node '1' in this graph with disconnected components?

DSA Javascript

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

function bfs(graph, start) {
  const queue = [start];
  const visited = new Set();
  const result = [];

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

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

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

B [1, 2, 3]

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

D [1, 3, 2]

💡 Hint

BFS only visits nodes reachable from the start node.

Starting from node 1, BFS visits 1, then 2, then 3. Nodes 4 and 5 are disconnected and not visited.

🔧 Debug

advanced

Identify the error in BFS implementation

What error will this BFS code produce when run?

DSA Javascript

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

function bfs(graph, start) {
  const queue = [start];
  const visited = new Set();
  const result = [];

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

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

A The code runs correctly and outputs ["A", "B", "C"]

B The code throws a TypeError because queue.pop() is invalid

C The code outputs ["A", "B", "C"] but behaves like DFS

D The code outputs ["A", "B", "C"] but in reverse BFS order

💡 Hint

Check how queue.pop() affects the order of node processing.

Using queue.pop() removes the last element, making the traversal behave like DFS (stack), not BFS (queue). So output is DFS order, not BFS.

🧠 Conceptual

advanced

BFS traversal levels in a graph

Given the graph below, what is the list of nodes at level 2 starting BFS from node 'X'? Graph: X: [Y, Z] Y: [P, Q] Z: [R] P: [] Q: [] R: []

A [P, Q]

B [Y, Z]

C [X]

D [P, Q, R]

💡 Hint

Level 0 is the start node, level 1 is its neighbors, level 2 is neighbors of neighbors.

Level 0: X Level 1: Y, Z Level 2: P, Q, R So nodes at level 2 are P, Q, and R.

🚀 Application

expert

Shortest path length using BFS

What is the shortest path length from node 'S' to node 'G' in the graph below using BFS? Graph: S: [A, B] A: [C] B: [D, E] C: [F] D: [G] E: [] F: [G] G: []

DSA Javascript

function bfsShortestPath(graph, start, goal) {
  const queue = [{node: start, distance: 0}];
  const visited = new Set();

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

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

console.log(bfsShortestPath(graph, 'S', 'G'));

A 3

B 2

C 4

D -1

💡 Hint

BFS finds shortest path in unweighted graphs by exploring neighbors level by level.

Shortest paths from S to G are S->B->D->G or S->A->C->F->G. The shortest length is 3 edges.

Practice

1. What does BFS (Breadth First Search) primarily use to keep track of nodes to visit next in a graph?

easy

A. A stack to explore nodes deeply first

B. A hash map to store visited nodes only

C. A queue to explore nodes level by level

D. A priority queue to explore nodes by weight

Solution

1. Step 1: Understand BFS traversal method

   BFS explores nodes level by level, so it needs to remember nodes in the order they are discovered.

2. Step 2: Identify the data structure for order

   A queue follows First-In-First-Out (FIFO), perfect for level order traversal in BFS.

3. Final Answer:

   A queue to explore nodes level by level -> Option C

4. Quick Check:

   BFS uses queue = A [OK]

Hint: BFS uses queue, DFS uses stack [OK]

Common Mistakes:

• Confusing BFS with DFS and choosing stack
• Thinking BFS uses priority queue
• Ignoring the order of node visits

2. Which of the following is the correct syntax to enqueue a node `v` into a queue named `queue` in JavaScript?

easy

A. queue.push(v);

B. queue.enqueue(v);

C. queue.add(v);

D. queue.insert(v);

Solution

1. Step 1: Recall JavaScript array methods for queue

   JavaScript arrays use `push()` to add elements at the end, simulating enqueue.

2. Step 2: Verify other options

   Methods like `enqueue()`, `add()`, or `insert()` are not standard array methods in JavaScript.

3. Final Answer:

   queue.push(v); -> Option A

4. Quick Check:

   Enqueue in JS array = push() [OK]

Hint: Use push() to add at queue's end in JS [OK]

Common Mistakes:

• Using non-existent enqueue() method
• Confusing push() with pop()
• Trying to use add() or insert() which don't exist

3. Consider the following graph represented as adjacency list:

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

function bfs(start) {
  const queue = [start];
  const visited = new Set([start]);
  const order = [];

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

console.log(bfs(1));

What will be the output printed?

medium

A. [1, 3, 2, 4]

B. [1, 2, 3, 4]

C. [1, 4, 2, 3]

D. [4, 2, 3, 1]

Solution

1. Step 1: Start BFS from node 1

   Queue = [1], visited = {1}, order = []. Dequeue 1, order = [1]. Enqueue neighbors 2 and 3.

2. Step 2: Visit nodes in queue order

   Queue = [2,3]. Dequeue 2, order = [1,2]. Enqueue neighbor 4. Queue = [3,4]. Dequeue 3, order = [1,2,3]. Neighbor 4 already visited, skip. Dequeue 4, order = [1,2,3,4].

3. Final Answer:

   [1, 2, 3, 4] -> Option B

4. Quick Check:

   BFS order = [1, 2, 3, 4] [OK]

Hint: BFS visits neighbors in queue order [OK]

Common Mistakes:

• Mixing order of neighbors
• Not marking visited before enqueue
• Using stack behavior instead of queue

4. The following BFS code has a bug. What is the error?

function bfs(start, graph) {
  const queue = [start];
  const visited = new Set();
  const order = [];

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

medium

A. Visited nodes are not marked before enqueueing, causing duplicates

B. Visited set is never updated, causing infinite loop

C. Visited nodes are marked after enqueueing, causing duplicates

D. Queue is not initialized properly

Solution

1. Step 1: Check order of visited marking

   Visited nodes are marked after enqueueing neighbors, which can cause duplicates if neighbors appear multiple times.

2. Step 2: Correct approach

   Mark nodes as visited before enqueueing to avoid adding duplicates to the queue.

3. Final Answer:

   Visited nodes are not marked before enqueueing, causing duplicates -> Option A

4. Quick Check:

   Mark visited before enqueue = no duplicates [OK]

Hint: Mark visited before enqueue to avoid duplicates [OK]

Common Mistakes:

• Marking visited after enqueue
• Not marking visited at all
• Initializing queue incorrectly

5. Given a graph with nodes and edges, how can BFS be adapted to find the shortest path length from a start node to a target node? Choose the best approach.

hard

A. Use a stack to explore nodes and update shortest distance dynamically

B. Use DFS and record path length when target is found

C. Use BFS but do not track visited nodes to find all paths

D. Use BFS with a queue and track distance for each node when first visited

Solution

1. Step 1: Understand BFS property for shortest path

   BFS explores nodes level by level, so the first time we reach the target node is the shortest path.

2. Step 2: Track distance during BFS

   Maintain a distance map or array, updating distance when a node is first visited to record shortest path length.

3. Final Answer:

   Use BFS with a queue and track distance for each node when first visited -> Option D

4. Quick Check:

   BFS + distance tracking = shortest path [OK]

Hint: Track distance on first visit in BFS for shortest path [OK]

Common Mistakes:

• Using DFS which may not find shortest path
• Not tracking visited nodes causing infinite loops
• Using stack instead of queue for BFS