BFS Breadth First Search on Graph in DSA Javascript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the queue with the starting node for BFS.

DSA Javascript

const bfs = (graph, start) => {
  const queue = [[1]];
  const visited = new Set();
  visited.add(start);
  while (queue.length > 0) {
    const node = queue.shift();
    console.log(node);
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
};

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

Astart

Bgraph

Cvisited

Dqueue

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing the queue with the entire graph or an empty array.

Forgetting to add the start node to the queue.

The BFS queue must start with the starting node to begin traversal from there.

2fill in blank

medium

Complete the code to check if a neighbor node has been visited before adding it to the queue.

DSA Javascript

for (const neighbor of graph[node]) {
  if (![1].has(neighbor)) {
    visited.add(neighbor);
    queue.push(neighbor);
  }
}

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

Aqueue

Bvisited

Cgraph

Dnode

Attempts:

3 left

💡 Hint

Common Mistakes

Checking the queue instead of the visited set.

Checking the graph or node variable incorrectly.

We check the 'visited' set to avoid revisiting nodes and prevent infinite loops.

3fill in blank

hard

Fix the error in the code to correctly remove the first element from the queue.

DSA Javascript

const node = queue.[1]();

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

Ashift

Bpop

Cpush

Dunshift

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'pop()' which removes the last element, breaking BFS order.

Using 'push()' or 'unshift()' which add elements instead of removing.

In BFS, we remove the first element from the queue using 'shift()' to process nodes in FIFO order.

4fill in blank

hard

Fill both blanks to add neighbors to the queue and mark them visited during BFS.

DSA Javascript

if (!visited.[1](neighbor)) {
  visited.[2](neighbor);
  queue.push(neighbor);
}

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

Ahas

Badd

Cdelete

Dclear

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'delete' or 'clear' instead of 'add' to mark visited.

Using 'has' incorrectly as a method to add elements.

We check if 'visited' has the neighbor, then add it to 'visited' before pushing to the queue.

5fill in blank

hard

Fill all three blanks to create a BFS function that prints nodes in correct order.

DSA Javascript

const bfs = (graph, start) => {
  const queue = [[1]];
  const visited = new Set();
  visited.[2](start);
  while (queue.length > 0) {
    const node = queue.[3]();
    console.log(node);
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
};

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

Astart

Badd

Cshift

Dpop

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'pop()' instead of 'shift()' breaks BFS order.

Forgetting to add start node to visited set.

Start the queue with 'start', add 'start' to visited, and remove nodes from queue with 'shift()' for BFS order.

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