Breadth-First Search (BFS): A Complete Guide

Breadth-First Search, commonly abbreviated as BFS, is one of the most fundamental algorithms in computer science. It is used to traverse or search through graphs and trees. BFS explores a structure level by level, visiting all nodes at a given distance from the starting node before moving further away.

Because of its predictable exploration order, BFS is widely used in applications such as shortest path algorithms, network analysis, web crawling, recommendation systems, and many other areas.

What Problem Does BFS Solve?

In many situations we represent data as a graph. A graph consists of vertices (nodes) connected by edges (links). Examples include social networks, road maps, computer networks, and even game maps.

When working with graphs we often need to explore all reachable nodes from a starting point. For example, we may want to determine which users can be reached in a social network, which cities are reachable from a location, or how data propagates across a network.

Breadth-First Search solves this exploration problem by visiting nodes in increasing order of distance from the starting node.

The Core Idea Behind BFS

The key idea of BFS is simple: explore neighbors first before moving deeper into the graph.

Imagine dropping a stone into water. The ripples spread outward in circles. BFS works in a similar way: it expands outward from the starting node in layers.

• Start from a chosen node
• Visit all immediate neighbors
• Then visit neighbors of those neighbors
• Continue expanding outward layer by layer

Because nodes are explored in layers, BFS naturally discovers the shortest path in graphs where every edge has the same cost.

Why BFS Uses a Queue

BFS relies on a queue data structure. A queue follows the First-In, First-Out (FIFO) principle: the first element added is the first one removed.

This behavior ensures that nodes are processed in the exact order they are discovered. When we visit a node, we add all of its unvisited neighbors to the queue. Those neighbors will then be explored in the same order.

The queue guarantees that nodes closer to the starting point are processed before nodes that are further away.

Step-by-Step Example

Consider a graph where we start from node A. Node A is connected to nodes B and C. Node B is connected to D and E, while node C is connected to F.

BFS would explore the nodes in the following order:

1. Start at A
2. Visit neighbors B and C
3. Visit neighbors of B: D and E
4. Visit neighbor of C: F

The traversal order becomes: A → B → C → D → E → F. Notice how the algorithm completes one layer before moving to the next.

BFS Algorithm

The BFS algorithm can be described with the following steps:

1. Create an empty queue
2. Add the starting node to the queue
3. Mark the starting node as visited
4. While the queue is not empty:
5. Remove a node from the front of the queue
6. Process the node
7. Add all unvisited neighbors to the queue and mark them as visited

JavaScript Implementation

Below is a simple JavaScript implementation of BFS using an adjacency list representation of a graph.

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

  visited.add(start);

  while (queue.length > 0) {
    const node = queue.shift();

    console.log(node);

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

Time Complexity

The time complexity of BFS depends on the number of vertices and edges in the graph.

Each vertex is visited at most once, and each edge is examined at most once. Therefore, the overall time complexity is O(V + E), where V is the number of vertices and E is the number of edges.

Space Complexity

BFS requires additional memory to store visited nodes and the queue. In the worst case, the queue may contain an entire level of the graph.

The space complexity is therefore O(V), where V is the number of vertices.

Common Applications of BFS

Breadth-First Search is extremely useful in many practical problems. Some of the most common applications include:

• Finding the shortest path in unweighted graphs
• Web crawlers that explore links across the internet
• Social network analysis
• Level order traversal in trees
• Game pathfinding on grid maps
• Network broadcasting and routing

BFS vs DFS

Another important graph traversal algorithm is Depth-First Search (DFS). While BFS explores nodes level by level, DFS explores as deeply as possible before backtracking.

BFS is generally preferred when we need the shortest path in an unweighted graph, while DFS is often used for tasks like cycle detection, topological sorting, and solving puzzles with backtracking.

Conclusion

Breadth-First Search is one of the most important algorithms for working with graphs and trees. Its level-by-level exploration strategy makes it ideal for problems that involve distances, connectivity, and shortest paths.

By understanding BFS, you gain a powerful tool for solving a wide variety of algorithmic problems. Mastering this algorithm is an essential step for anyone studying data structures, algorithms, or preparing for technical interviews.