BFS (Graph Theory)

BFS stands for Breadth First Search, also called breadth-first search.

It is one of the most basic and important search algorithms on graphs.

Breadth-first search means that we try to visit vertices on the same level each time. Only after all vertices on the current level have been visited do we move to the next level.

As a result, the path found by BFS is the shortest valid path from the starting point; in other words, it contains the minimum number of edges.

When BFS ends, every vertex has been visited along a shortest path from the start to that vertex.

The process can be viewed as a fire spreading across a graph: initially only the starting point is on fire, and at each moment every burning vertex spreads the fire to all its neighbors.

Implementation

The C++ and Python implementations below use the forward-star representation for storing graphs; see the Graph Storage page for details.

Pseudocode

bfs(s) {
  q = new queue()
  q.push(s), visited[s] = true
  while (!q.empty()) {
    u = q.pop()
    for each edge(u, v) {
      if (!visited[v]) {
        q.push(v)
        visited[v] = true
      }
    }
  }
}

C++

void bfs(int u) {
  while (!Q.empty()) Q.pop();
  Q.push(u);
  vis[u] = 1;
  d[u] = 0;
  p[u] = -1;
  while (!Q.empty()) {
    u = Q.front();
    Q.pop();
    for (int i = head[u]; i; i = e[i].nxt) {
      if (!vis[e[i].to]) {
        Q.push(e[i].to);
        vis[e[i].to] = 1;
        d[e[i].to] = d[u] + 1;
        p[e[i].to] = u;
      }
    }
  }
}

void restore(int x) {
  vector<int> res;
  for (int v = x; v != -1; v = p[v]) {
    res.push_back(v);
  }
  std::reverse(res.begin(), res.end());
  for (int i = 0; i < res.size(); ++i) printf("%d", res[i]);
  puts("");
}

Python

from queue import Queue

def bfs(u):
    Q = Queue()
    Q.put(u)
    vis[u] = True
    d[u] = 0
    p[u] = -1
    while Q.qsize() != 0:
        u = Q.get()
        i = head[u]
        while i:
            if vis[e[i].to] == False:
                Q.put(e[i].to)
                vis[e[i].to] = True
                d[e[i].to] = d[u] + 1
                p[e[i].to] = u
            i = e[i].nxt

def restore(x):
    res = []
    v = x
    while v != -1:
        res.append(v)
        v = p[v]
    res.reverse()
    for i in range(0, len(res)):
        print(res[i])

More specifically, we use a queue Q to record the vertices to process and a Boolean array vis[] to mark whether each vertex has been visited.

Initially, set every value of vis to 0, indicating that no vertex has been visited; then put the starting point s into queue Q and set vis[s] to 1.

Next, we repeatedly take the front vertex u from queue Q, mark every vertex v adjacent to u as visited, and put it into queue Q.

Repeat until queue Q is empty, which means that BFS has ended.

During BFS, additional information can also be recorded. For example, in the code above, array d records the shortest distance from the start to each vertex (the minimum number of edges), while array p records the vertex from which the current vertex was reached.

With array d, the distance from the start to any vertex can be obtained easily.

With array p, the shortest path from the start to a vertex can be reconstructed easily. The restore function in the code above uses this array to output, in order, the vertices on the shortest path from the start to vertex x.

Time complexity: O(n+m)O(n + m)

Space complexity: O(n)O(n) (vis array and queue)

The open-closed table

When implementing BFS, we essentially put unvisited vertices into a container called open and visited vertices into a container called closed.

BFS on trees and graphs

BFS sequence

Like a DFS sequence, a BFS sequence is the sequence of vertex indices visited during BFS.

BFS on a general graph

If the original graph is disconnected, only the vertices reachable from the starting point can be visited.

A BFS sequence is generally not unique.

Similarly, we can define a BFS tree: by recording which vertex was used to visit each vertex during BFS, we can construct a tree structure, called a BFS tree.

Applications

  • Find shortest paths from a starting point to all other vertices in an unweighted graph.
  • Find all connected components in O(n+m)O(n+m) time. (Start BFS from each unvisited vertex; each BFS clearly traverses one connected component.)
  • If a game's actions are regarded as edges (transitions) in a state graph, BFS can find the minimum number of steps needed to reach one state from another.
  • Find the shortest cycle in a directed unweighted graph. (Start BFS from every vertex; when an edge is about to reach an already visited vertex, a cycle has been found. The shortest cycle is the minimum cycle found by all BFS runs.)
  • Find edges that must lie on a shortest path from (a,b)(a, b). (Run BFS from a and b to obtain two d arrays. For an edge (u,v)(u, v), if da[u]+1+db[v]=da[b]d_a[u]+1+d_b[v]=d_a[b], the edge lies on a shortest path.)
  • Find vertices that must lie on a shortest path from (a,b)(a, b). (Run BFS from a and b to obtain two d arrays. For a vertex v, if da[v]+db[v]=da[b]d_a[v]+d_b[v]=d_a[b], the vertex lies on a shortest path.)
  • Find a shortest path of even length. (Construct a new graph by splitting every vertex into two new vertices; replace an original edge (u,v)(u, v) with ((u,0),(v,1))((u, 0), (v, 1)) and ((u,1),(v,0))((u, 1), (v, 0)). Run BFS on the new graph; the shortest path between (s,0)(s, 0) and (t,0)(t, 0) is the answer.)
  • Find shortest paths in a graph whose edge weights are 0/1; see 0-1 BFS below.

Deque BFS

If you are unfamiliar with the deque deque, see the section on deque.

Deque BFS is also called 0-1 BFS.

Applicability

It applies to shortest-path problems whose edge weights may or may not be present (because ordinary BFS applies to graphs with edge weight 1, the usual weights are 0 or 1), or that can be transformed into such a problem.

For example, in a maze, if one coin lets you walk five steps while walking one step costs nothing, the problem can be solved with 0-1 BFS.

Implementation

In general, put the vertices reached through zero-weight edges at the front of the deque and those reached through weighted edges at the back. This ensures that, as in ordinary BFS, weights are nondecreasing from the front to the back of the deque.

The pseudocode is as follows:

while (the queue is not empty) {
  int u = queue_front;
  pop_front();
  for (each neighbor of u) {
    update_data();
    if (...)
      push_front();;
    else
      push_back();;
  }
}

Examples

Codeforces 173B

Consider an n×mn \times m grid. A laser starts at the upper-left corner and travels right. Whenever it encounters '#', you may shoot the beam in any of the four directions or do nothing. What is the minimum number of '#' cells from which the beam must be redirected so that it exits to the right on row nn?

The intended solution is not 0-1 BFS, but 0-1 BFS applies and reduces the conceptual difficulty; many contestants used it during the contest.

The idea is simple: continuing in the current direction costs (0), while shooting in one of the four directions costs (1), and then we can run 0-1 BFS directly.

Code

#include <deque>
#include <iostream>
using namespace std;

constexpr int INF = 1 << 29;
int n, m;
char grid[1001][1001];
int dist[1001][1001][4];
int fx[] = {1, -1, 0, 0};
int fy[] = {0, 0, 1, -1};
deque<int> q;  // deque

void add_front(int x, int y, int dir, int d) {  // add to the front
  if (d < dist[x][y][dir]) {
    dist[x][y][dir] = d;
    q.push_front(dir);
    q.push_front(y);
    q.push_front(x);
  }
}

void add_back(int x, int y, int dir, int d) {  // add to the back
  if (d < dist[x][y][dir]) {
    dist[x][y][dir] = d;
    q.push_back(x);
    q.push_back(y);
    q.push_back(dir);
  }
}

int main() {
  cin >> n >> m;
  for (int i = 0; i < n; i++) cin >> grid[i];

  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
      for (int k = 0; k < 4; k++) dist[i][j][k] = INF;

  add_front(n - 1, m - 1, 3, 0);

  while (!q.empty()) {  // See the explanation above for the detailed search process.
    int x = q[0], y = q[1], dir = q[2];
    q.pop_front();
    q.pop_front();
    q.pop_front();
    int d = dist[x][y][dir];
    int nx = x + fx[dir], ny = y + fy[dir];
    if (nx >= 0 && nx < n && ny >= 0 && ny < m)
      add_front(nx, ny, dir, d);  // check the condition
    if (grid[x][y] == '#')
      for (int i = 0; i < 4; i++)
        if (i != dir) add_back(x, y, i, d + 1);
  }
  if (dist[0][0][3] == INF)
    cout << -1 << endl;
  else
    cout << dist[0][0][3] << endl;
  return 0;
}

Priority-queue BFS

A priority queue is essentially a binary heap. The STL provides std::priority_queue, which makes priority queues convenient to use.

In priority-queue BFS, we take the vertex with the smallest cost from the front each time and continue the search from it. This greedy idea is correct: expanding from this vertex cannot update vertices whose current costs are higher. In other words, there is no need to reconsider updates for those higher-cost vertices.

Of course, a vertex may be inserted into the queue multiple times, with a different cost each time. Once the vertex is removed from the priority queue for the first time, there is no need to search from it again; simply ignore later occurrences. Thus, in priority-queue BFS, each vertex is processed only once.

Compared with ordinary queue-based BFS, the time complexity gains a factor of log⁡n\log n because the priority queue must be maintained. However, ordinary BFS may enqueue and dequeue each vertex multiple times, reaching O(n2)O(n^2) rather than O(n)O(n). Priority-queue BFS is therefore often faster in practice.

Does this sound a lot like heap-optimized Dijkstra? In fact, heap-optimized Dijkstra is priority-queue BFS.

Exercises

Deque BFS:

References

https://cp-algorithms.com/graph/breadth-first-search.html

Previous section
330 DFS (Graph Theory)
Next section
332 Tree Basics

This content comes from OI Wiki: BFS (Graph Theory). See the original for authors and revision history. AIOJ has adapted the formatting, in-site links, and resource paths.

Content is shared under CC BY-SA 4.0 and SATA license; additional terms are governed by the original notice. Thanks to the OI Wiki authors and contributors; per the SATA terms, please visit the OI Wiki repository and star it to show your support.