BFS

廣度優先搜尋 (Breadth-first Search/BFS)：走訪為每拜訪一節點就將其全部鄰點拜訪過。

按照上圖，走訪順序為最小的數字 1 依照自然數列開始走訪到 15。

當然，與 DFS 同樣，因為走訪中途碰到曾走過的點不往下繼續走，所以 BFS 走完後也會有個 BFS 樹(?

當要 BFS 搜索地圖起點到終點的最短路，當走訪到終點時的深度就是最短步數
例如地圖上 * 代表牆(不能走)，$ 代表路，% 是起點，@是終點：

*  *  *  *  *  *  *  *  *  *  
*  *  *  *  $  %  $  $  *  *  
*  $  $  $  $  *  *  $  *  *  
*  $  *  $  *  *  *  $  *  *  
*  $  *  $  $  $  *  $  *  *  
*  $  *  $  *  $  $  $  *  *  
*  $  $  *  *  $  *  $  $  *  
*  *  $  $  $  *  *  *  $  *  
*  @  *  *  $  *  $  $  $  *  
*  $  *  *  $  *  $  *  $  *  
*  $  $  $  $  $  $  *  *  *  
*  *  *  *  *  *  *  *  *  *  

而一次只能走上下左右一格

用 BFS 去搜尋起點到終點的最短步數：

*  *  *  *  *  *  *  *  *  *  
*  *  *  *  1  0  1  2  *  *  
*  5  4  3  2  *  *  3  *  *  
*  6  *  4  *  *  *  4  *  *  
*  7  *  5  6  7  *  5  *  *  
*  8  *  6  *  8  7  6  *  *  
*  9  10 *  *  9  *  7  8  *  
*  *  11 12 13 *  *  *  9  *  
*  21 *  *  14 *  12 11 10 *  
*  20 *  *  15 *  13 *  11 *  
*  19 18 17 16 15 14 *  *  *  
*  *  *  *  *  *  *  *  *  *  

其中上面數字代表深度。
這個走法就跟粘菌走迷宮同樣

下方給出實作程式碼，可以配合上面例子來理解：

queue<int> Q;
Q.push(root); //root 代表走訪此圖的起點
vis[root] = true;

while (!Q.empty()) {
  int u = Q.front(); Q.pop();
  
  for (auto v: E[u]) {
    if (vis[v]) continue;
    vis[v] = true;
    Q.push(v);
  }
}

根據條件應將不合法的走法濾掉，在 Q.push() 之前可判斷一下。

讀者可能會發現，這根本就把 stack 實作的 DFS，換成用 queue 實作嘛(
但為什麼是這樣？建議花點時間去思考。

範題：
UVa OJ 11624 Fire!

一開始先將 Joe 與各火點放進 queue 中，以便讓 BFS 以此為起點走訪：

for(int r = 0; r < R; r++) {
  scanf("%s", input);
  for(int c = 0; c < C; c++) {
    if(input[c] == '#') maze[r][c] = 0;
    if(input[c] == '.') maze[r][c] = INF;
    if(input[c] == 'J') J.push((point){r, c, 0}), vis[r][c] = true;
    if(input[c] == 'F') F.push((point){r, c, 0});
  }
}

(其中 INF 為一個非常大的數字，例如 int 的上限，這將成慣例)

Joe 不能被火燒到，所以 Joe 一定要走得比火快
由此，算出各點何時火會燒過來就能判斷 Joe 是否能比火先到

搜尋火到各點的最短路：

while(!F.empty()) {
  point f = F.front(); F.pop();

  for(int d = 0; d < 4; d++) {
    int nr = f.r+dr[d], nc = f.c+dc[d];
    if(nr == R || nc == C || nr < 0 || nc < 0 || maze[nr][nc] != INF) continue;
    
    maze[nr][nc] = f.t + 1;
    F.push((point){nr, nc, f.t+1});
  }
}

其中 point 結構三個變數為 row, column 與 time
並利用 dr 與 dc 以當前所在點走遍四個方向：

int const dr[] = {0, 0, -1, 1};
int const dc[] = {-1, 1, 0, 0};

現在 maze (也就是地圖) 上有紀錄火到的時間了。
接下來讓 Joe 去尋找最短路：

int escape = -1;
while(!J.empty()) {
  point j = J.front(); J.pop();
  if(j.r == R-1 || j.c == C-1 || j.r == 0 || j.c == 0) {
    escape = j.t + 1;
    break;
  }

  for(int d = 0; d < 4; d++) {
    int nr = j.r+dr[d], nc = j.c+dc[d];
    if(vis[nr][nc] || j.t + 1 >= maze[nr][nc]) continue;
    
    vis[nr][nc] = true;
    J.push((point){nr, nc, j.t+1});
  }
}

j.t + 1 >= maze[nr][nc] 就能看 Joe 走這點是不是會被火燒
最後判斷走到邊界，就成功逃脫了！

練習：
UVa OJ 532 Dungeon Master
STEP5 0127 攻略妹妹
UVa OJ 11234 Expressions
UVa OJ 1599 Ideal Path

下次一樣會討論搜尋，各位改天見。