BFS Breadth First Search on Graph in DSA Javascript - Build from Scratch

BFS Breadth First Search on Graph

📖 Scenario: You are working with a simple map of connected places. Each place is linked to others. You want to explore all places starting from one place, visiting neighbors first before going deeper.

🎯 Goal: Build a program that uses BFS (Breadth First Search) to visit all connected places in order, starting from a given place.

📋 What You'll Learn

Create a graph as an adjacency list with exact connections

Create a queue to help with BFS traversal

Implement BFS using a loop and queue

Print the order of places visited by BFS

💡 Why This Matters

🌍 Real World

BFS is used in social networks to find friends at different levels, in GPS to find shortest paths, and in web crawlers to explore websites layer by layer.

💼 Career

Understanding BFS is essential for software engineers working on search algorithms, network analysis, and game development.

1

Create the graph as an adjacency list

Create a constant called graph as an object with these exact entries: 'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], 'D': ['B'], 'E': ['B', 'F'], 'F': ['C', 'E']

DSA Javascript

# Your code here

Hint

Use an object where keys are place names and values are arrays of connected places.

2

Create a queue for BFS

Create a constant called queue and set it to an array containing only the string 'A'. Also create a constant called visited and set it to a new Set containing 'A'.

DSA Javascript

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

// Your code here

Hint

Start BFS from 'A' by putting it in the queue and marking it visited.

3

Implement BFS traversal loop

Create an empty array called order. Use a while loop that runs while queue.length > 0. Inside the loop, remove the first element from queue into a variable called current. Push current into order. Then, use a for loop with variable neighbor to iterate over graph[current]. Inside this loop, if neighbor is not in visited, add it to visited and push it into queue.

DSA Javascript

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

const queue = ['A'];
const visited = new Set(['A']);

// Your code here

Hint

Use a queue to visit nodes level by level. Mark neighbors visited when you add them to the queue.

4

Print the BFS order

Write a console.log statement to print the order array.

DSA Javascript

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

const queue = ['A'];
const visited = new Set(['A']);
const order = [];

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

// Your code here

Hint

Print the array order to see the BFS visiting sequence.

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