Breadth-First Search (BFS)

Introduction

The breadth-first search (BFS) algorithm works on an unweighted graph and starts from a source vertex $s$.

The graph may be either directed or undirected — BFS works in both cases.

A good way to imagine BFS is as the spread of fire through the graph:

• at step $0$, only the source vertex $s$ is “burning”;
• at each next step, the fire spreads from all currently burning vertices to their neighbors.

So in one iteration, the “ring of fire” expands by one edge. This is exactly why BFS visits vertices in order of increasing distance from the source.

Idea

To implement BFS, we use:

• a queue q, which stores the vertices to be processed;
• an array used[x], which shows whether vertex x has already been visited.

Initially:

• we put the source vertex s into the queue;
• mark it as visited;
• mark all other vertices as unvisited.

Then, while the queue is not empty:

1. take the vertex at the front of the queue;
2. go through all of its neighbors;
3. if a neighbor has not been visited yet, mark it as visited and push it into the queue.

By the end of the algorithm, all vertices reachable from s will be visited.

Shortest Paths

One of the most important properties of BFS is that in an unweighted graph, it finds the shortest path from the source to every reachable vertex.

To do this, we can store: