BFS Breadth First Search on Graph in DSA Typescript

Mental Model

BFS explores all neighbors of a node before moving to the next level of nodes.

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

Graph:
  1
 / \
2   3
|    |
4    5

Queue starts with [1] ↑

Dry Run Walkthrough

Input: Graph edges: 1->2, 1->3, 2->4, 3->5; start BFS from node 1

Goal: Visit all nodes in order of their distance from node 1

Step 1: Start BFS by enqueueing node 1

Queue: [1↑]
Visited: {}

Why: We begin from the start node 1

Step 2: Dequeue 1, visit it, enqueue neighbors 2 and 3

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

Why: Visit node 1 and add its neighbors to queue for next visits

Step 3: Dequeue 2, visit it, enqueue neighbor 4

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

Why: Visit node 2 and add its neighbor 4

Step 4: Dequeue 3, visit it, enqueue neighbor 5

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

Why: Visit node 3 and add its neighbor 5

Step 5: Dequeue 4, visit it, no new neighbors

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

Why: Visit node 4; no new nodes to add

Step 6: Dequeue 5, visit it, no new neighbors

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

Why: Visit node 5; BFS complete as queue is empty

Result:

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

Annotated Code

DSA Typescript

class Graph {
  adjacencyList: Map<number, number[]>;

  constructor() {
    this.adjacencyList = new Map();
  }

  addEdge(u: number, v: number) {
    if (!this.adjacencyList.has(u)) this.adjacencyList.set(u, []);
    this.adjacencyList.get(u)!.push(v);
  }

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

    visited.add(start); // mark start node as visited
    queue.push(start); // enqueue start node

    while (queue.length > 0) {
      const node = queue.shift()!; // dequeue front node
      order.push(node); // record visit order

      const neighbors = this.adjacencyList.get(node) || [];
      for (const neighbor of neighbors) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor); // mark neighbor visited when enqueueing
          queue.push(neighbor); // enqueue unvisited neighbors
        }
      }
    }

    return order;
  }
}

// Driver code
const graph = new Graph();
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 4);
graph.addEdge(3, 5);

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

visited.add(start); // mark start node as visited

mark start node visited before enqueueing to avoid duplicates

queue.push(start); // enqueue start node

initialize queue with start node to begin BFS

const node = queue.shift()!; // dequeue front node

remove front node from queue to visit it

order.push(node); // record visit order

save node in BFS visit order

const neighbors = this.adjacencyList.get(node) || [];

get neighbors of current node or empty if none

if (!visited.has(neighbor)) { visited.add(neighbor); queue.push(neighbor); }

mark neighbor visited and enqueue unvisited neighbors for future visits

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 nodes

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 with no nodes

BFS returns empty list as there is no start node

DSA Typescript

queue.push(start); // enqueue start node

Graph with single node and no edges

BFS visits the single node and returns it

DSA Typescript

const neighbors = this.adjacencyList.get(node) || [];

Graph with disconnected nodes

BFS visits only nodes reachable from start node

DSA Typescript

if (!visited.has(neighbor)) { visited.add(neighbor); queue.push(neighbor); }

When to Use This Pattern

When you need to explore nodes in order of their distance from a start node or find shortest paths in unweighted graphs, reach for BFS because it visits nodes level by level.

Common Mistakes

Mistake: Not marking nodes as visited before enqueueing, causing duplicates in queue
Fix: Mark nodes as visited when enqueueing or check before enqueueing to avoid repeats

Mistake: Using stack instead of queue, which changes BFS to DFS
Fix: Use a queue data structure to maintain correct BFS order

Summary

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

Use BFS when you want to find shortest paths or explore nodes by distance from start.

The key insight is BFS uses a queue to explore neighbors before moving deeper.

Practice

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

easy

A. A priority queue to select nodes by weight

B. A stack to process nodes in depth order

C. A hash map to store visited nodes only

D. A queue to process nodes level by level

Solution

1. Step 1: Understand BFS traversal method

   BFS explores nodes level by level, so it needs a structure that processes nodes in the order they are discovered.

2. Step 2: Identify the data structure used

   A queue follows First-In-First-Out (FIFO) order, which matches BFS's level order traversal.

3. Final Answer:

   A queue to process nodes level by level -> Option D

4. Quick Check:

   BFS uses a queue = A [OK]

Hint: BFS uses FIFO order, so it needs a queue [OK]

Common Mistakes:

• Confusing BFS with DFS which uses a stack
• Thinking BFS uses a priority queue
• Assuming BFS only uses a visited set without a queue

2. Which of the following is the correct TypeScript syntax to initialize a queue for BFS using an array?

easy

A. const queue = new Queue<number>();

B. const queue: number[] = [];

C. let queue = {};

D. var queue = new ArrayQueue();

Solution

1. Step 1: Recognize TypeScript array initialization

   To create a queue using an array, declare an array with type annotation and initialize it empty.

2. Step 2: Check each option

   const queue: number[] = []; correctly declares an empty number array. const queue = new Queue<number>(); uses a class Queue which is not built-in. let queue = {}; initializes an object, not a queue. var queue = new ArrayQueue(); uses a non-existent ArrayQueue.

3. Final Answer:

   const queue: number[] = []; -> Option B

4. Quick Check:

   Array queue syntax = A [OK]

Hint: Use typed empty array for queue in TypeScript [OK]

Common Mistakes:

• Using undefined classes like Queue without import
• Initializing queue as an object {} instead of array
• Using var instead of const or let (less preferred)

3. Given the graph adjacency list below and BFS starting from node 0, what is the order of nodes visited?

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

medium

A. [0, 1, 2, 3]

B. [0, 2, 1, 3]

C. [0, 3, 1, 2]

D. [1, 2, 0, 3]

Solution

1. Step 1: Start BFS from node 0

   Visit node 0 first, then enqueue its neighbors 1 and 2.

2. Step 2: Visit neighbors in queue order

   Dequeue 1, visit it, enqueue its neighbor 3. Then dequeue 2, visit it, enqueue 3 again but already visited. Finally, dequeue 3.

3. Final Answer:

   [0, 1, 2, 3] -> Option A

4. Quick Check:

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

Hint: Visit nodes level by level, enqueue neighbors in order [OK]

Common Mistakes:

• Visiting neighbors in wrong order
• Visiting node 3 twice
• Starting BFS from wrong node

4. Consider this BFS code snippet in TypeScript. What is the error?

function bfs(graph: Record, start: number) {
  const queue: number[] = [start];
  const visited = new Set<number>();
  while (queue.length > 0) {
    const node = queue.shift();
    if (!visited.has(node)) {
      visited.add(node);
      for (const neighbor of graph[node]) {
        queue.push(neighbor);
      }
    }
  }
  return Array.from(visited);
}

medium

A. queue.shift() can return undefined, causing errors

B. visited set is not updated correctly

C. Neighbors are not added to queue

D. Function does not return anything

Solution

1. Step 1: Analyze queue.shift() usage

   queue.shift() returns number | undefined. If queue is empty, node can be undefined, causing errors when accessing graph[node].

2. Step 2: Identify missing check for undefined

   Code should check if node is undefined before using it. Without this, runtime error can occur.

3. Final Answer:

   queue.shift() can return undefined, causing errors -> Option A

4. Quick Check:

   Check for undefined after shift = B [OK]

Hint: Always check queue.shift() result for undefined [OK]

Common Mistakes:

• Ignoring possible undefined from shift()
• Assuming visited set is wrong when it is correct
• Thinking neighbors are not added when they are

5. You want to find the shortest path length from node 0 to node 4 in this graph using BFS:

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

Which BFS modification helps find the shortest path length correctly?

hard

A. Ignore visited set to explore all paths

B. Use a stack instead of a queue

C. Track distance for each node when first visited

D. Visit nodes multiple times to update distance

Solution

1. Step 1: Understand BFS for shortest path

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

2. Step 2: Track distance when visiting nodes

   Maintain a distance map or array to record the number of edges from start node to each node when first visited.

3. Final Answer:

   Track distance for each node when first visited -> Option C

4. Quick Check:

   Distance tracking in BFS = D [OK]

Hint: Store distance on first visit to each node [OK]

Common Mistakes:

• Using stack breaks BFS order
• Visiting nodes multiple times wastes time
• Ignoring visited set causes infinite loops