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

BFS Breadth First Search on Graph

📖 Scenario: Imagine you have a map of cities connected by roads. You want to visit all cities starting from one city, exploring neighbors first before going deeper. This is like spreading out in waves, visiting all nearby cities before moving further.

🎯 Goal: You will build a program that uses BFS (Breadth First Search) to visit all nodes in a graph starting from a given node, and print the order of visited nodes.

📋 What You'll Learn

Create a graph using an adjacency list representation

Use a queue to manage nodes to visit in BFS order

Keep track of visited nodes to avoid repeats

Print the order of nodes visited by BFS

💡 Why This Matters

🌍 Real World

BFS is used in social networks to find friends within certain distances, in GPS navigation 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 where exploring connected components efficiently is needed.

1

Create the graph as an adjacency list

Create a constant called graph as a Record<string, string[]> with these exact entries: 'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], 'D': ['B'], 'E': ['B', 'F'], 'F': ['C', 'E'].

DSA Typescript

// Your code here

Hint

Use a TypeScript object where keys are city names and values are arrays of connected cities.

2

Set up BFS helper variables

Create a constant startNode and set it to 'A'. Create a variable visited as a Set<string> and add startNode to it. Create a variable queue as an array of strings initialized with startNode. Create a variable order as an empty array of strings to store the visit order.

DSA Typescript

const graph: Record = {
  'A': ['B', 'C'],
  'B': ['A', 'D', 'E'],
  'C': ['A', 'F'],
  'D': ['B'],
  'E': ['B', 'F'],
  'F': ['C', 'E']
};
// Your code here

Hint

Initialize visited as a Set and add the start node. Use an array queue starting with the start node. Prepare an empty array order to record the visit sequence.

3

Implement BFS loop to visit nodes

Write a while loop that runs while queue.length > 0. Inside the loop, remove the first element from queue into a variable current. Add current to the order array. 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 to queue.

DSA Typescript

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

const startNode = 'A';
const visited = new Set();
visited.add(startNode);
const queue: string[] = [startNode];
const order: string[] = [];

// Your code here

Hint

Use queue.shift() to get the current node. Add it to order. Check neighbors and add unvisited ones to visited and queue.

4

Print the BFS visit order

Write console.log(order.join(' -> ')) to print the order of nodes visited by BFS separated by arrows.

DSA Typescript

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

const startNode = 'A';
const visited = new Set();
visited.add(startNode);
const queue: string[] = [startNode];
const order: string[] = [];

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

Use console.log(order.join(' -> ')) to show the BFS visit order clearly.

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