BFS Breadth First Search on Graph in DSA Javascript

Mental Model

BFS explores all neighbors of a node before moving to the next level of nodes. It visits nodes layer by layer.

Analogy: Imagine you are in a building and want to visit every room floor by floor. You first visit all rooms on the first floor, then all rooms on the second floor, and so on.

Graph:
  1
 / \
2   3
|    |
4    5

Queue starts with [1]
Visited set is empty

Dry Run Walkthrough

Input: Graph with nodes 1 to 5 and edges: 1-2, 1-3, 2-4, 3-5; start BFS from node 1

Goal: Visit all nodes reachable from node 1 in breadth-first order

Step 1: Start BFS by adding node 1 to the queue and mark it visited

Queue: [1]
Visited: {1}

Why: We start from node 1, so we add it to the queue to explore its neighbors

Step 2: Dequeue node 1, visit neighbors 2 and 3, add them to queue and mark visited

Queue: [2, 3]
Visited: {1, 2, 3}

Why: We explore all neighbors of node 1 before moving deeper

Step 3: Dequeue node 2, visit neighbor 4, add to queue and mark visited

Queue: [3, 4]
Visited: {1, 2, 3, 4}

Why: After finishing node 1's neighbors, we explore node 2's neighbors

Step 4: Dequeue node 3, visit neighbor 5, add to queue and mark visited

Queue: [4, 5]
Visited: {1, 2, 3, 4, 5}

Why: Next, we explore node 3's neighbors

Step 5: Dequeue node 4, no new neighbors to visit

Queue: [5]
Visited: {1, 2, 3, 4, 5}

Why: Node 4 has no unvisited neighbors

Step 6: Dequeue node 5, no new neighbors to visit

Queue: []
Visited: {1, 2, 3, 4, 5}

Why: Node 5 has no unvisited neighbors, BFS ends

Result:

Visited order: 1 -> 2 -> 3 -> 4 -> 5

Annotated Code

DSA Javascript

class Graph {
  constructor() {
    this.adjList = new Map();
  }

  addVertex(v) {
    if (!this.adjList.has(v)) {
      this.adjList.set(v, []);
    }
  }

  addEdge(v, w) {
    this.adjList.get(v).push(w);
    this.adjList.get(w).push(v); // undirected graph
  }

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

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

    while (queue.length > 0) {
      const vertex = queue.shift();
      order.push(vertex);

      for (const neighbor of this.adjList.get(vertex)) {
        if (!visited.has(neighbor)) {
          queue.push(neighbor);
          visited.add(neighbor);
        }
      }
    }

    return order;
  }
}

// Driver code
const g = new Graph();
[1, 2, 3, 4, 5].forEach(v => g.addVertex(v));
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(2, 4);
g.addEdge(3, 5);

const bfsOrder = g.bfs(1);
console.log(bfsOrder.join(' -> '));

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

Initialize BFS by adding start node to queue and mark visited

while (queue.length > 0) {

Continue BFS while there are nodes to explore

const vertex = queue.shift(); order.push(vertex);

Dequeue node and record visitation order

for (const neighbor of this.adjList.get(vertex)) { if (!visited.has(neighbor)) { queue.push(neighbor); visited.add(neighbor); } }

Add all unvisited neighbors to queue and mark visited

Output

1 -> 2 -> 3 -> 4 -> 5

Complexity Analysis

Time: O(V + E) because each vertex and edge is visited once during BFS

Space: O(V) for the queue and visited set storing vertices

vs Alternative: Compared to DFS which uses a stack or recursion, BFS uses a queue and explores level by level, which is better for shortest path in unweighted graphs

Edge Cases

Empty graph (no vertices)

BFS returns empty order as there is no start node

DSA Javascript

if (!this.adjList.has(start)) return [];

Graph with single node and no edges

BFS visits the single node and ends

DSA Javascript

while (queue.length > 0) {

Disconnected graph, start node isolated

BFS visits only the start node and no others

DSA Javascript

for (const neighbor of this.adjList.get(vertex)) {

When to Use This Pattern

When you need to explore nodes layer by layer or find shortest paths in unweighted graphs, BFS is the pattern to use because it visits neighbors first before going deeper.

Common Mistakes

Mistake: Not marking nodes as visited before adding to queue causes repeated visits and infinite loops
Fix: Mark nodes as visited immediately when adding to queue to prevent revisiting

Summary

BFS visits all nodes in a graph level by level starting from a given node.

Use BFS when you want to explore neighbors first or find shortest paths in unweighted graphs.

The key insight is to use a queue to explore nodes in the order they are discovered.

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