Breadth-first search宽度优先遍历

Breadth-first search (BFS) visits the nodes in increasing order of their distance from the starting node. Thus, we can calculate the distance from the starting node to all other nodes using breadth-first search.
image.png
Like in depth-first search, the time complexity of breadth-first search is O(n + m), where n is the number of nodes and m is the number of edges.

  1. queue<int> q;
  2. bool visited[N];
  3. int distance[N];
  5. visited[x] = true;
  6. distance[x] = 0;
  7. q.push(x);
  9. while (!q.empty()) {
  10.     int s = q.front(); q.pop();
  12.     for (auto u : adj[s]) {
  13.        if (visited[u]) continue;
  15.        visited[u] = true;
  16.        distance[u] = distance[s]+1;
  17.        q.push(u);
  18.     } 
  19. }

例题，【例8.3】最少步数

  1. //棋盘问题，最短路

例题，Dungeon Master

  1. //棋盘问题，最短路

例题，仙岛求药

  1. //棋盘问题，最短路，多组测试数据