Breadth-First Search

graphlevel-ordershortest-path

Press play to start

1function bfs(graph: Record<string, string[]>, start: string): string[] {
const visited = new Set<string>();
const queue = [start];
const order: string[] = [];
while (queue.length > 0) {
  const node = queue.shift()!;
  if (visited.has(node)) continue;
  visited.add(node);
  order.push(node);
  for (const nb of graph[node] ?? []) {
    if (!visited.has(nb)) queue.push(nb);
  }
}
return order;
15}

Step 1/0

Complexity

Best:O(V+E)
Average:O(V+E)
Worst:O(V+E)
Space:O(V)

Description

Explores a graph level by level, visiting all neighbors before moving deeper. Uses a queue to track the next node to visit.

When to use

Finding shortest paths in unweighted graphs. Level-order traversal. Useful in social networks, GPS navigation, web crawlers.