bfs算法思想及实现

以老鼠走迷宫为例，如果说DFS是一只老鼠将整个图走到底，那么BFS就是一群老鼠走迷宫，也可以称作“并行处理”的模拟。假设老鼠是无穷多的，这群老鼠进去后，在每个路口派出部分老鼠探索没有走过的路。
停下有两种情况：

走某条路碰壁，无法前行。
到达的路口已被探索过。

显然，这将使得所有道路都走到，且不重复。
一般使用队列这种数据结构来具体实现BFS。

BFS是一个“扩散”的过程，如果把搜索空间当作一个池塘，丢一颗石头到起点位置，激起的波浪会一层层扩散到整个空间。扩散是从近到远的顺序进行，因此，每个被扩散到的点到起点的路径都是最短的。

算法实现：

设置一个队列Q，从顶点出发，遍历该顶点后让其进队；
出队一个顶点元素，求该顶点的所有邻接点，对于没有遍历过的邻接点遍历之，并让其进队；
若队空停止，队不空时继续第2步。

模拟BFS过程

有一个房间，铺着红黑两色瓷砖，黑色可以走，红色不可以，计算一个人通过上下左右移动（相邻瓷砖）之后可以到达的黑色瓷砖数量（包括起点）。
‘●’代表黑色，'＃'代表红色，‘＠’代表人。

要遍历所有可能的点，从起点1出发，走到它所有的邻居2、3；再处理邻居，例如在邻居2上，可以再走2的邻居4、5、6；继续这个过程，直到所有点都被走到。
以下用队列queue模拟过程：

（1）1进队，队列{1}。
在这里插入图片描述
（2）1出队，1的邻居2、3,进队。当前队列{2,3}。
（可以理解为上文的“扩散”，从1扩散2和3）

（3）2出队，2的邻居4、5、6进队。当前队列{3， 4， 5 ，6}。（从2扩散到4,5,6）

（4）3出队，7,8进队。当前队列{4，5，6，7，8}（3扩散到7，8）
在这里插入图片描述
（5）4出队，9进队（4的其他两个方向一个碰壁，一个已经被其他点扩散过，故4只可以扩散到9）。当前队列{5， 6， 7 ，8 ，9}。

（6）5出队，10进队。队列{6， 7， 8 ，9 ，10}。
（7）6出队，11进队。队列{7， 8 ， 9， 10， 11}。
（8）7出队，12、 13进队。队列{8， 9， 10， 11， 12， 13}。
（9）8、 9出队，10出队，14进队。队列{11， 12， 13， 14}。
（10）11出队，15进队。队列{12， 13， 14， 15}。
（11）12,13,14,15出队。队列为空{}，结束。
在这里插入图片描述

bfs例题及模板

例题一：洛谷 p1443-马的遍历：模板题，注意格式和走法即可。
“马走日 ”走法图（以m点为中心向八个方向移动）
0 1 0 1 0
1 0 0 0 1
0 0 m 0 0
1 0 0 0 1
0 1 0 1 0

#include<bits/stdc++.h>
using namespace std;
#define check(n,m) (t2.x>=1&&t2.x<=n&&t2.y>=1&&t2.y<=m)
int dx[8] = {2,1,-1,-2,-2,-1,1,2};
int dy[8] = {1,2,2,1,-1,-2,-2,-1};
struct node{
  int x, y, step;
}t1,t2;
int n, m, qx, qy;
int mp[405][405];
bool vis[405][405];
void bfs(int qx, int qy) {
  queue<node> q;
  t1.x = qx, t1.y = qy, t1.step = 0;
  vis[qx][qy] = 1;
  q.push(t1);
  while (!q.empty()) {
    t1 = q.front();q.pop();
    mp[t1.x][t1.y] = t1.step;
    for (int i = 0; i < 8; i++) {
      t2.x = t1.x + dx[i];
      t2.y = t1.y + dy[i];
      if (check(n,m) && !vis[t2.x][t2.y]) {
        vis[t2.x][t2.y] = 1;
        t2.step = t1.step+1;
        mp[t2.x][t2.y] = t2.step;
        q.push(t2);
      }
    }
  }
}
int main() {
  cin >> n >> m >> qx >> qy;
  memset(mp, -1, sizeof(mp));
  memset(vis, false, sizeof(vis));
  bfs(qx, qy);
  int count = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      cout << mp[i][j];
      if (mp[i][j]/100 != 0) count = 3;
      else if (mp[i][j]/10 != 0 || mp[i][j] < 0) count = 2;
      else count = 1;
      for (int k = 0; k < 5-count; k++) 
        printf(" ");
    }
    cout << endl;
  }
}

例题二：洛谷 p1162-填涂颜色：找到闭合圈内任意一个为0的点作为起点扩散即可。

#include<bits/stdc++.h>
using namespace std;

struct node{
  int x, y;
}t1,t2;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,-1,0,1};
int n, qx, qy, flag;
int mp[35][35];
bool vis[35][35];

void bfs(int qx, int qy) {
  queue<node> q;
  t1.x = qx;t1.y = qy;
  vis[t1.x][t1.y] = 1;
  mp[t1.x][t1.y] = 2;
  q.push(t1);
  while (!q.empty()) {
    t1 = q.front();
    q.pop();
    for (int i = 0; i < 4; i++) {
      t2.x = t1.x + dx[i];
      t2.y = t1.y + dy[i];
      if (mp[t2.x][t2.y] == 0 && !vis[t2.x][t2.y]) {
        vis[t2.x][t2.y] = 1;
        mp[t2.x][t2.y] = 2;
        q.push(t2);
      }
    }
  }
}
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      scanf("%d", &mp[i][j]);
    }
  }
  //找到闭合圈内任意一个0点作为起点 
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (mp[i][j] == 1 && mp[i+1][j+1] == 0) {
        qx = i+1;
        qy = j+1;
        flag = 1;
        break;
      }
    }
    if (flag == 1) break;
  }
  bfs(qx,qy);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      printf("%d ", mp[i][j]);
    }
    if (i != n-1) printf("\n");
  }
}

例题三：洛谷 p1135-奇怪的电梯：注意可能多条线路到达终点，选取少按的方案数。

#include<bits/stdc++.h>
using namespace std;
struct node{
  int floor;
  int ans;
}t1,t2;
int n, a, b, flag = -1;
int k[205];
int dy[2] = {1,-1};
bool vis[205];
void bfs(int start, int end) {
  queue<node> q;
  t1.floor = start;
  t1.ans = 0;
  q.push(t1);
  vis[t1.floor] = 1;
  while (!q.empty()) {
    t1 = q.front();
    q.pop();
    if (t1.floor == end) {
      flag = 1;
      return;
    }
    for (int i = 0; i < 2; i++) {
      t2.floor = t1.floor + dy[i]*k[t1.floor];
      if ((t2.floor >= 1 && t2.floor <= n) && !vis[t2.floor]) {
        t2.ans = t1.ans+1;
        if (t2.floor == end) {
          flag = 1;
          return;
        }
        vis[t2.floor] = 1;
        q.push(t2);
      }
    }
  }
}
int main() {
  scanf("%d%d%d", &n, &a, &b);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &k[i]);
  }
  bfs(a, b);
  if (flag == 1) {
    printf("%d\n", t2.ans);
  } else {
    printf("-1\n");
  }
}
/*
#1
6 1 6
5 3 1 2 5 6

1
#2
6 1 6
1 1 1 1 1 1 

5

#3
6  2 5
4 1 1 1 1 2

2
*/

例题四：北京大学 poj3278-catch that cow：与例题三相似，有三个方向，注意特殊情况：农民如果在逃犯前面只能一步步往后退，可以直接算出来。

例题五：北京大学 poj 3126-Prime Path：将四位数拆分为四个数，每次替换一个数字后判断素数，戳我看具体思路与题解。

例题六：hdoj 1240-Asteroids!：三维BFS（戳此处：三维数组的理解），用三个分量表示三维，坑点是起点和终点的坐标输入顺序，看清题！

例题七：洛谷 p1141-01迷宫：记忆化搜索，找连通块。

#include<bits/stdc++.h>
using namespace std;
struct node{
  int x, y;
}t1,t2;
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
char mp[1001][1001];
int vis[1001][1001],block[1001][1001];
int n,m,sx,sy,ans;

void bfs(int x, int y) {
  queue<node> q;
  vector<node> pos; //用来存储连通块内各点坐标
  ans = 1;
  vis[x][y] = 1;
  q.push({x,y});
  while (!q.empty()) {
    t1 = q.front();q.pop();
    pos.push_back(t1);
    for (int i = 0; i < 4; i++) {
      t2.x = t1.x + dx[i];
      t2.y = t1.y + dy[i];
      if (t2.x<1||t2.x>n||t2.y<1||t2.y>n) continue;
      if (mp[t2.x][t2.y] != mp[t1.x][t1.y] && !vis[t2.x][t2.y]) {
        vis[t2.x][t2.y] = 1;
        ans++;
        q.push(t2);
      }
    } 
  }
  //c++11新特性(只适用于简单的遍历）
  for (auto v:pos) block[v.x][v.y] = ans;//把连通块的数量赋给在连通块内的每一点。
}
int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      cin >> mp[i][j];
    }
  }
  while (m--) {
    cin >> sx >> sy;
    if (block[sx][sy] != 0) {//已经搜过就直接输出点所处的连通块的数量
      cout << block[sx][sy] << endl;
    } else {
      bfs(sx, sy);
      cout << block[sx][sy] << endl;
    }
  }
}

暴力技术（一）——BFS广（宽）度优先搜索

bfs算法思想及实现

模拟BFS过程

bfs例题及模板