Engineering Fluency OS

Why This Matters

Imagine you are looking for someone at a party. You could wander randomly through the crowd, or you could start by checking everyone in the room you are in, then move to adjacent rooms, then the rooms beyond those. That second strategy is breadth-first search (BFS) — explore all nearby nodes before moving to distant ones.

BFS is the go-to algorithm for finding the shortest path in an unweighted graph. When you need the fewest hops between two points — fewest clicks between web pages, fewest friend connections between two people, fewest moves in a puzzle — BFS gives you the answer. It also powers level-order traversal of trees, which processes nodes row by row from top to bottom.

Define Terms

Visual Model

Astart (1)

B(2)

C(3)

D(4)

E(5)

F(6)

The full process at a glance. Click Start tour to walk through each step.

BFS explores level by level using a queue. It finds shortest paths in unweighted graphs.

Code Example

Code

// BFS on an adjacency list
function bfs(graph, start) {
  const visited = new Set([start]);
  const queue = [start];
  const order = [];

  while (queue.length > 0) {
    const node = queue.shift(); // dequeue front
    order.push(node);

    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }

  return order;
}

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

console.log(bfs(graph, "A")); // ["A","B","C","D","E","F"]

// SHORTEST PATH (unweighted)
function shortestPath(graph, start, end) {
  const visited = new Set([start]);
  const queue = [[start, [start]]]; // [node, path]

  while (queue.length > 0) {
    const [node, path] = queue.shift();

    if (node === end) return path;

    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push([neighbor, [...path, neighbor]]);
      }
    }
  }

  return null; // no path exists
}

console.log(shortestPath(graph, "A", "F")); // ["A","C","F"]
console.log(shortestPath(graph, "D", "F")); // ["D","B","E","F"]

Interactive Experiment

Try these exercises:

Trace BFS on the example graph starting from node "D". Write out the order nodes are visited and verify it matches the code output.
Modify the BFS to return the distance (number of edges) from start to each reachable node instead of the path.
What happens if you replace the queue with a stack (use pop() instead of shift())? Does it still find the shortest path?
Create a graph that has no path between two nodes and verify shortestPath returns null.

Quick Quiz

Coding Challenge

Shortest Path Length

Write a function called `shortestPathLength` that takes an adjacency list (object), a source vertex, and a destination vertex. Return the length of the shortest path (number of edges) from source to destination. If no path exists, return -1. If source equals destination, return 0.

Loading editor...

Real-World Usage

BFS is used in many systems you interact with daily:

Social networks: LinkedIn's "degrees of connection" feature uses BFS to measure how many hops separate two people. "2nd degree connection" means BFS found a path of length 2.
Web crawlers: Search engine crawlers discover pages by BFS — start from seed URLs, visit all linked pages, then visit pages linked from those, expanding outward layer by layer.
GPS navigation: Finding routes with the fewest turns or stops (unweighted) uses BFS. Weighted shortest path (by distance or time) uses Dijkstra's, which extends BFS.
Puzzle solving: BFS finds the minimum number of moves to solve puzzles like Rubik's cubes, sliding tile puzzles, or word ladders (change one letter at a time).
Network broadcasting: Data packets in a network spread via BFS-like flooding — each router forwards to its neighbors, who forward to theirs.

Breadth-First Search