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.