00:00

Breadth First Search (BFS) Algorithm

Last updated:

To traverse a graph is to visit its vertices in a systematic order, for example to search for a vertex, to find out which vertices are reachable, or to measure distances. Because a graph can contain cycles, a traversal must remember which vertices it has already visited so it does not loop forever.

There are two standard graph traversals:

  1. Breadth First Search (BFS)

  2. Depth First Search (DFS)

This tutorial covers Breadth First Search.

What is Breadth First Search (BFS)?

Breadth First Search explores a graph in layers. It starts at a source vertex, visits all of the source's neighbours, then all vertices two edges away, then three, and so on. In the picture below, starting from A, BFS visits the first layer (B, C, D) before any vertex of the second layer (E, F, G, H, I).

BFS from source A: layer 1 is B, C, D and layer 2 is E, F, G, H, I; BFS output A B C D E F G H I

Because vertices are reached in order of their distance from the source, BFS finds a shortest path (fewest edges) from the source to every reachable vertex in an unweighted graph. The edges BFS uses to discover new vertices form a BFS tree, a spanning tree of the part of the graph that is reachable from the source.

The same layer-by-layer idea appears in other algorithms: Kahn's topological sort processes vertices with a queue in the same way, and Dijkstra's algorithm generalises BFS to weighted edges by replacing the queue with a priority queue.

How Breadth First Search (BFS) Works

  1. Start: choose the source vertex.

  2. Queue: create an empty FIFO queue for vertices that have been discovered but not yet processed.

  3. Mark and enqueue the source: mark it visited and add it to the queue.

  4. Process the front vertex:

    • Remove the vertex at the front of the queue and process it (for example, print it).
    • For each neighbour that is not yet visited, mark it visited and add it to the back of the queue.
  5. Repeat step 4 until the queue is empty (or until the target vertex is found, if you are searching for one).

Marking a vertex as visited when it is enqueued, not when it is dequeued, guarantees that no vertex enters the queue twice.

BFSExample.java
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

// Breadth-first search on an undirected graph stored as an adjacency list
public class BFSExample {

  // Prints the vertices reachable from start, nearest first
  static void bfs(List<List<Integer>> graph, int start) {
    boolean[] visited = new boolean[graph.size()];
    Queue<Integer> queue = new ArrayDeque<>();

    visited[start] = true;          // mark when a vertex is added to the queue,
    queue.offer(start);             // so it can never be added twice

    while (!queue.isEmpty()) {
      int vertex = queue.poll();    // the oldest waiting vertex comes out first
      System.out.print(vertex + " ");

      for (int next : graph.get(vertex)) {
        if (!visited[next]) {
          visited[next] = true;
          queue.offer(next);        // neighbours wait behind everything already queued
        }
      }
    }
    System.out.println();
  }

  static void addEdge(List<List<Integer>> graph, int u, int v) {
    graph.get(u).add(v);            // undirected: store the edge at both ends
    graph.get(v).add(u);
  }

  public static void main(String[] args) {
    int vertices = 5;
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < vertices; i++) {
      graph.add(new ArrayList<>());
    }

    //      0
    //     / \
    //    1   2
    //   / \ /
    //  3   4
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 4);

    System.out.println("BFS starting from node 0 : ");
    bfs(graph, 0);
  }
}
Output
BFS starting from node 0 :
0 1 2 3 4

Vertex 0 is processed first and queues its neighbours 1 and 2. Processing 1 queues 3 and 4; when 2 is processed, its neighbour 4 is already marked, so it is not queued again. The order is therefore 0, 1, 2, 3, 4: first distance 0, then distance 1, then distance 2.

Time Complexity: O(V + E) with an adjacency list, where V is the number of vertices and E the number of edges: every vertex is queued once and every adjacency list is scanned once.

Extra Space: O(V) for the visited array and the queue.