Breadth-First Search

Breadth-First Search

Breadth-First Search (BFS) explores a graph level by level. Starting from a source node, it visits all neighbors first, then their neighbors, and so on. BFS uses a queue.

Graph Representation

We represent a graph as an adjacency list — an object mapping each node to its array of neighbors:

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

Algorithm

function bfs(graph, start) {
  const visited = new Set();
  const queue = [start];
  const result = [];
  visited.add(start);

  while (queue.length > 0) {
    const node = queue.shift();
    result.push(node);
    for (const neighbor of (graph[node] || [])) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
  return result;
}

Properties

• Finds the shortest path (by number of edges) in an unweighted graph.
• Level-order traversal: visits nodes by their distance from the start.
• Time complexity: O(V + E) where V = vertices, E = edges.
• Space complexity: O(V) for the visited set and queue.

Real-World Uses

• Shortest path in maps, social networks (degrees of separation).
• Web crawlers (crawl pages breadth-first to avoid deep rabbit holes).
• Level-order traversal of binary trees.
• Finding all nodes within k hops of a source.

Your Task

Implement bfs(graph, start) that returns an array of nodes visited in BFS order.