Breadth-First Search (BFS) is a fundamental algorithm used to explore nodes in a graph or tree level by level. Unlike Depth-First Search (DFS), which dives deep along a branch before backtracking, BFS starts from a source node and visits all neighboring nodes before moving to the next level. This makes BFS ideal for finding the shortest path in unweighted graphs, exploring networks, and solving problems where proximity matters. For beginners learning TypeScript, BFS is a great way to understand queues, loops, and systematic graph traversal.
with hands-on learning.
get the skills and confidence to land your next move.
BFS is widely used in applications such as social networks to find connections, routing algorithms in maps, and even in artificial intelligence for shortest path calculations. By learning BFS, beginners can grasp how structured exploration of data works and how to implement efficient search mechanisms in TypeScript. The algorithm’s clarity and practical applications make it an essential tool for anyone interested in programming and data structures.
Program 1: BFS Using a Queue
This program demonstrates the standard BFS approach using a queue to traverse a graph from a starting node.
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, []);
if (!this.adjacencyList.has(v)) this.adjacencyList.set(v, []);
this.adjacencyList.get(u)!.push(v);
this.adjacencyList.get(v)!.push(u); // For undirected graph
}
bfs(start: number) {
let visited = new Set<number>();
let queue: number[] = [start];
visited.add(start);
while (queue.length > 0) {
let node = queue.shift()!;
console.log(node);
for (let neighbor of this.adjacencyList.get(node) || []) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push(neighbor);
}
}
}
}
}
let graph = new Graph();
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 4);
graph.addEdge(3, 5);
console.log("BFS Traversal:");
graph.bfs(1);In this program, the queue ensures nodes are processed in the order they are discovered. Beginners can observe how BFS explores nodes level by level, which is especially useful for finding shortest paths.
Program 2: BFS for Weighted Graphs (Ignoring Weights)
BFS can traverse weighted graphs when the goal is to visit nodes rather than compute shortest paths by weight.
let weightedGraph: Map<number, [number, number][]> = new Map([
[1, [[2, 5], [3, 3]]],
[2, [[1, 5], [4, 2]]],
[3, [[1, 3], [5, 7]]],
[4, [[2, 2]]],
[5, [[3, 7]]]
]);
function bfsWeighted(graph: Map<number, [number, number][]>, start: number) {
let visited = new Set<number>();
let queue: number[] = [start];
visited.add(start);
while (queue.length > 0) {
let node = queue.shift()!;
console.log(node);
for (let [neighbor, weight] of graph.get(node) || []) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push(neighbor);
}
}
}
}
console.log("BFS Weighted Graph Traversal:");
bfsWeighted(weightedGraph, 1);This shows that BFS traversal logic is similar regardless of weights, which helps beginners understand BFS as a general exploration technique.
Program 3: BFS on a 2D Grid
BFS can be applied to grids for pathfinding and maze solving by exploring all neighbors level by level.
let maze: number[][] = [
[0, 1, 0, 0],
[0, 0, 0, 1],
[1, 0, 1, 0],
[0, 0, 0, 0]
];
function bfsGrid(grid: number[][], startX: number, startY: number) {
let rows = grid.length;
let cols = grid[0].length;
let visited: boolean[][] = Array.from({ length: rows }, () => Array(cols).fill(false));
let queue: [number, number][] = [[startX, startY]];
visited[startX][startY] = true;
let directions = [
[0, 1], [0, -1], [1, 0], [-1, 0]
];
while (queue.length > 0) {
let [x, y] = queue.shift()!;
console.log(`Visited cell: (${x}, ${y})`);
for (let [dx, dy] of directions) {
let newX = x + dx;
let newY = y + dy;
if (
newX >= 0 && newY >= 0 && newX < rows && newY < cols &&
grid[newX][newY] === 0 && !visited[newX][newY]
) {
visited[newX][newY] = true;
queue.push([newX, newY]);
}
}
}
}
console.log("BFS Grid Traversal:");
bfsGrid(maze, 0, 0);This example illustrates BFS in practical grid-based problems, showing how it can systematically explore all reachable cells.
Program 4: BFS for Finding Shortest Path in Unweighted Graph
BFS is often used to find the shortest path because it explores neighbors level by level.
function shortestPathBFS(graph: Map<number, number[]>, start: number, target: number) {
let visited = new Set<number>();
let queue: [number, number[]][] = [[start, [start]]];
visited.add(start);
while (queue.length > 0) {
let [node, path] = queue.shift()!;
if (node === target) return path;
for (let neighbor of graph.get(node) || []) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push([neighbor, [...path, neighbor]]);
}
}
}
return null;
}
let simpleGraph: Map<number, number[]> = new Map([
[1, [2, 3]],
[2, [1, 4]],
[3, [1, 5]],
[4, [2, 6]],
[5, [3, 6]],
[6, [4, 5]]
]);
console.log("Shortest Path from 1 to 6:", shortestPathBFS(simpleGraph, 1, 6));Beginners can learn how BFS naturally finds the shortest path in unweighted graphs by expanding nodes in order of distance from the start.
Program 5: BFS for Detecting Connected Components
BFS can identify all connected components in an undirected graph by running BFS from unvisited nodes.
function connectedComponents(graph: Map<number, number[]>) {
let visited = new Set<number>();
let components: number[][] = [];
for (let node of graph.keys()) {
if (!visited.has(node)) {
let component: number[] = [];
let queue: number[] = [node];
visited.add(node);
while (queue.length > 0) {
let current = queue.shift()!;
component.push(current);
for (let neighbor of graph.get(current) || []) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push(neighbor);
}
}
}
components.push(component);
}
}
return components;
}
let simpleGraph: Map<number, number[]> = new Map([
[1, [2, 3]],
[2, [1, 4]],
[3, [1, 5]],
[4, [2, 6]],
[5, [3, 6]],
[6, [4, 5]]
]);
console.log("Connected Components:", connectedComponents(simpleGraph));This application demonstrates BFS’s use beyond traversal—helping analyze graph structure and connectivity.
Frequently Asked Questions (FAQ)
Beginners often have questions about BFS:
Q1. Can BFS work on both directed and undirected graphs?
Yes, BFS works for both types; only adjacency relationships change.
Q2. How is BFS different from DFS?
BFS explores nodes level by level, while DFS goes deep along a branch first.
Q3. Can BFS find the shortest path?
Yes, in unweighted graphs, BFS naturally finds the shortest path from the start node.
Q4. Can BFS be applied to grids or mazes?
Absolutely, BFS is perfect for exploring grids systematically and finding paths.
Q5. Is BFS safe for very large graphs?
Yes, but memory usage grows with the number of nodes in the queue; iterative BFS avoids recursion depth issues.
Conclusion
Breadth-First Search is a versatile and widely used algorithm for exploring graphs, trees, and grids. In this article, we explored BFS in TypeScript using queues for standard traversal, weighted graphs, 2D grids, shortest path finding, and detecting connected components. Beginners can practice these examples to understand BFS logic, queue management, and practical applications in real-world problems like pathfinding, network analysis, and structure exploration.
Mastering BFS in TypeScript strengthens your understanding of graph algorithms and prepares you for advanced topics such as Dijkstra’s algorithm, A* search, and network flow analysis. By exploring BFS through these examples, beginners can develop both conceptual understanding and hands-on programming skills.
