BFS (Graph Theory)

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

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

The idea of breadth-first search is to always try to visit nodes at the same level first. If all nodes at the current level have been visited, then proceed to the next level.

As a result, the path found by the BFS algorithm is the shortest valid path from the starting point. In other words, this path contains the minimum number of edges.

When BFS finishes, each node is visited via the shortest path from the starting point to that node.

The algorithm process can be visualized as the spread of fire on a graph: initially, only the starting point is on fire. At each moment, every node that is on fire spreads the flame to all its adjacent nodes.

Implementation

The C++ and Python code implementations below are based on the linked forward star graph storage method. For its implementation, refer to the Graph Storage page.

PseudocodeC++Python

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
      }
    }
  }
}

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("");
}

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])

Specifically, we use a queue Q to record the nodes to be processed, and a boolean array vis[] to mark whether a node has been visited.

Initially, we set the vis value of all nodes to 0, indicating they have not been visited; then we place the starting point s into queue Q and set vis[s] to 1.

After that, each time we take the front node u from queue Q, then mark all nodes v adjacent to u as visited and place them into queue Q.

The loop continues until queue Q is empty, indicating the end of BFS.

During BFS, additional information can also be recorded. For example, in the above code, the d array records the shortest distance (minimum number of edges) from the starting point to a node, and the p array records which node we came from to reach the current node.

With the d array, we can easily obtain the distance from the starting point to any node.

With the p array, we can easily reconstruct the shortest path from the starting point to a node. The restore function in the above code uses this array to output the nodes along the shortest path from the starting point to node x in order.

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

Space complexity: \(O(n)\) (for the vis array and the queue)

Open-Closed Table

When implementing BFS, essentially we place unvisited nodes in a container called open, and visited nodes in a container called closed.

BFS on Trees/Graphs

BFS Sequence

Similar to the DFS sequence, the BFS sequence refers to the sequence of node IDs visited during the BFS process.

BFS on General Graphs

If the original graph is not connected, BFS can only visit nodes reachable from the starting point.

The BFS sequence is usually not unique.

Similarly, we can define a BFS tree: during BFS, by recording which node each node was visited from, we can build a tree structure, which is the BFS tree.

Applications

• Finding the shortest paths from a starting point to all other nodes in an unweighted graph.
• Finding all connected components in \(O(n+m)\) time. (We just need to start BFS from each unvisited node; each BFS will obviously traverse one connected component.)
• If the actions in a game are viewed as edges (transitions) on a state graph, then BFS can be used to find the minimum number of steps required to go from one state to another in the game.
• Finding the minimum cycle in a directed unweighted graph. (Start BFS from each node; when we are about to reach a previously visited node, we know we have encountered a cycle. The minimum cycle of the graph is the average of the minimum cycles obtained from each BFS.)
• Finding edges that must lie on the shortest path between \((a, b)\). (Perform BFS from a and b separately to get two d arrays. Then for each edge \((u, v)\), if \(d_a[u]+1+d_b[v]=d_a[b]\), then this edge lies on a shortest path.)
• Finding nodes that must lie on the shortest path between \((a, b)\). (Perform BFS from a and b separately to get two d arrays. Then for each node v, if \(d_a[v]+d_b[v]=d_a[b]\), then this node lies on some shortest path.)
• Finding a shortest path of even length. (We need to construct a new graph by splitting each node into two new nodes. An original edge \((u, v)\) becomes \(((u, 0), (v, 1))\) and \(((u, 1), (v, 0))\). Perform BFS on the new graph; the shortest path between \((s, 0)\) and \((t, 0)\) is the desired path.)
• Finding the shortest path on a graph with edge weights 0/1, see the Double-ended Queue BFS section below.

Double-ended Queue BFS

If you are not familiar with the double-ended queue deque, please refer to the deque related section.

Double-ended queue BFS is also known as 0-1 BFS.

Applicability

Applicable to shortest path problems where edge weights may be 0 or 1 (or can be transformed into such), or where edges may have no weight (since BFS applies to graphs with weight 1, typically weights are 0 or 1).

For example, in a maze problem where you can spend 1 gold coin to move 5 steps, or move 1 step without spending a coin, this can be solved with 0-1 BFS.

Implementation

Generally, we place nodes reached via edges with weight 0 at the front of the queue, and nodes reached via edges with weight 1 at the back of the queue. This ensures that the queue remains monotonically non-decreasing in weight from front to back, just like in ordinary BFS.

Below is the pseudocode:

while (queue is not empty) {
  int u = queue front;
  pop front;
  for (each neighbor of u) {
    update data
    if (...)
      add to front of queue;
    else
      add to back of queue;
  }
}

Example

Codeforces 173B

Given an \(n \times m\) grid, a laser beam shoots from the top-left corner to the right. Whenever it encounters a '#', you can choose to let the beam shoot in any of the four directions, or do nothing. Find the minimum number of '#' that need to shoot in four directions so that the beam exits from the right side of the \(n\)-th row.

The official solution to this problem is not 0-1 BFS, but 0-1 BFS is applicable, reducing the thinking difficulty. Many contestants used this approach during the competition.

The approach is simple: shooting in the current direction costs 0, while shooting in the four directions costs 1. Then proceed 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;  // Double-ended queue

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()) {  // The specific search process, refer to the solution above
    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);  // Condition check
    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, making it convenient to use priority queues.

In priority queue-based BFS, each time we take the node with the smallest cost from the front of the queue for further exploration. It is easy to prove that this greedy approach is correct, because searches starting from this node will never update nodes that originally had higher costs. In other words, we will not consider updating those higher-cost nodes.

Of course, each node may be enqueued multiple times, but with different costs each time. When a node is first taken out of the priority queue, there is no need to search from that node again in the future; it can be ignored directly. Therefore, in priority queue BFS, each node is processed only once.

Compared to ordinary queue BFS, the time complexity increases by a factor of \(\log n\), due to maintaining the priority queue. However, ordinary BFS might enqueue and dequeue each node multiple times, leading to a time complexity of \(O(n^2)\), not \(O(n)\). So priority queue BFS is usually still faster.

Hmm? Doesn't this sound a lot like the heap-optimized Dijkstra algorithm? In fact, heap-optimized Dijkstra is exactly priority queue BFS.

Exercises

• 「NOIP2017」Cheese

Double-ended Queue BFS:

• CF1063B. Labyrinth
• CF173B. Chamber of Secrets
• 「BalticOI 2011 Day1」Switch the Lamp On

References

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

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用