Breadth-First Search
Explore all neighbors at the current depth before going deeper.
How it works
BFS uses a queue (FIFO) to explore nodes level by level — all nodes at distance 1 first, then distance 2, and so on. This guarantees that the first time you reach the destination, it's via the shortest path (in terms of number of edges).
The key data structure is the queue. When you visit a node, you add all its unvisited neighbors to the back of the queue. The next node processed is always the one that's been waiting the longest — so you always finish one "wave" before starting the next.
BFS is optimal for unweighted graphs. For weighted graphs, use Dijkstra's algorithm instead.
Complexity
Visualizer
Where it's used in the real world
Social networks (LinkedIn, Facebook)
Degrees of separation / friend suggestionsBFS finds all people within N connections. LinkedIn's 'People you may know' explores the graph level by level — 1st connections, then 2nd, then 3rd — which is exactly BFS.
Web crawlers (Googlebot)
Crawling pages level by levelGoogle's crawler starts from seed URLs and explores outgoing links breadth-first, ensuring pages close to the seed are indexed before deeper, less-authoritative pages.
Network routing (STP)
Spanning Tree ProtocolSTP uses BFS from the root bridge to compute the shortest path to every switch and block redundant links — preventing broadcast storms in Ethernet networks.
Game AI / Puzzle solvers
Shortest path in grid gamesPac-Man ghost AI and tile-based game pathfinding use BFS on the grid to find the minimum number of moves to reach the player. BFS guarantees optimal move count.
Implementation
function bfs(graph: Map<string, string[]>, start: string, end: string): string[] | null {
const queue: string[] = [start];
const visited = new Set<string>([start]);
const parent = new Map<string, string | null>([[start, null]]);
while (queue.length > 0) {
const node = queue.shift()!; // FIFO — dequeue from front
if (node === end) {
// Reconstruct path
const path: string[] = [];
let cur: string | null = end;
while (cur !== null) {
path.unshift(cur);
cur = parent.get(cur) ?? null;
}
return path;
}
for (const neighbor of graph.get(node) ?? []) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
parent.set(neighbor, node);
queue.push(neighbor); // enqueue to back
}
}
}
return null; // no path
}