---
title: 廣度優先搜尋(BFS)
description: 本文介紹了BFS的實做，並提供了一個範例題目和程式碼實作，以及一些引導思考和參考資料。
tags: BFS, 演算法, C++
type: article
lang: zh-tw
---
[Toc]
# 目錄
- 何謂BFS
- 範例題目
- 解決方法
- 程式落地
# 何謂BFS
BFS，全稱Breadth-first search，廣度優先搜尋，常用於搜尋最佳解(例如最短路徑)，與DFS適合窮舉可能性不同。
特點為如水波般一圈圈擴散。優先搜尋最近的所有地點再慢慢擴大移動範圍。
# 範例題目
### 走迷宮問題
給一個 $n\times m$ 大小的迷宮，以「`#`」代表不可通行的障礙物，
「`.`」代表可通行的空間，「`S`」代表起點、「`E`」代表終點，
每花 $1$ 分鐘可走到「上、右、下、左」四個方向其中一個相鄰、且可通行的地方。
絕對不能走到地圖外面。
求從起點走到終點最少要花多少分鐘，如果不可能達成則輸出「$-1$」。
#### 範例輸入
```
5 6
S....#
##.##.
...#..
..#...
....#E
```
#### 範例輸出
```
13
```
#### 範例輸入
```
3 5
#...S
#.##.
.#.E#
```
#### 範例輸出
```
-1
```
# 概念
## Q1:目的:如何找到起終點間最小的路徑?
1. 一條路走到底，把所有的可能都走一次([[DFS]])
2. 找一個起點，慢慢往外擴散(BFS)
1. 這就像是水珠的漣漪一樣，只要測算漣漪靠岸的時間，就能得到離岸邊的距離
2. 或是把一團水丟進往四面八方的水管，這樣水會從起點慢慢蔓延到周圍
我們將地圖上每一個位置(無論是否可通行)稱為一個「點」。
因此，設起點為Sx,Sy，終點為Ex,Ey
另外更嚴謹的說法是：
我們假設某個位離起點dis遠，則我們需要從dis = 0 開始，先將dis < i 所有位置都找出來後，才開始找 dis = i 的位置。
所以我們能確定，第一個解若在第 i 步找到，則表示 dis < i 不存在任何解，故 dis = i 為最佳解。
## 特性
一圈圈擴散、不走相同點的特性同時也保證了每個點只須被考慮過一次，因此複雜度為O(nm)，o為節點數，m為某個節點搜尋周圍所花的計算輛。
不過也因為如此，不像 DFS 會保留到達同個地點的各自不同走法，BFS 只在乎花了幾步走到這個地點，會得到一個純量，不在乎怎麼走到的，也不在乎不同走法的差異。
## 實作目標
==選定一個起點，使其向水波一圈一圈擴散出去，若是碰到終點則停止==
這句話包含了幾個目標:
1. 選定起點
2. 一圈一圈擴散
3. 碰到終點停止
# 程式碼實作
## 總說
三部分:
1. 起點
2. 搜尋周圍，同時記錄，作為下一個待搜尋的點
3. 轉移到下一個待搜尋的點。
## 如何向外擴散?
用跟中心的距離來分辨在第幾圈，確保每一圈都完全記錄本身距離與周圍，再前往下一圈。
一樣，我們從想法提取要實作的部分
1. 以距離來判斷圈數
2. 一圈結束再前往下一圈
3. 紀錄本身距離
4. 搜尋周圍
## 以距離判斷圈數
起點為0。在可以走的路徑填上距離起點的最小距離，起點周圍是1、再周圍是2......。
因此，我們定義一個struct(一個能包含很多資料的東西)，讓struct能同時表達座標與距離起點距離。
```cpp
struct node{
int x,y,dis;//x座標, y座標, 與起點距離
};
```
## 如何保證一圈接著一圈而不錯亂?
就要保證一圈的所有點都被記錄再前往下一圈，並保證搜過的不再搜，使每一格的dis都是最小。
這是由於當後續展開相同時，從起點走到現在位置的步數越小，位還越好。這說明了只有當前最佳時會得到未來最佳。
而因為BFS一圈一圈的特性，初次抵達時的步數必定最小，因此第二次抵達必不為最佳，這與最佳解無關，則可忽略。
下面就要解決：
1. 搜過的不要再搜
2. 一圈所有點都被記錄才能往下一圈
## 搜過的不要再搜
建一個
```cpp
bool used[1024][1024];//判斷二維陣列上的某個點是否被紀錄過
```
並用[[memset]]
```cpp
memset(used,0,sizeof(used))
```
把used的每一格(used所佔的所有記憶體空間)都初始化為0
==起點也要初始化==
否則就會出現從起點往外找，發現起點本人沒used就往回走的情況。
```cpp
used[sx][sy] = true;
```
並且在丟進queue之前就令現在搜尋到的這格對應的used為true
```cpp
used[nxt.x][nxt.y] = true;
```
### 一圈所有點都被記錄才能往下一圈
可以用[[queue]]來解決。可以把他想成待辦清單，先發布的任務會先處理；同樣的，先儲存的點會先處理。(後進先出)
先令我現在所身在的點為cur(current)，搜尋的點為nxt(next)。
```cpp
node cur, nxt;//定義現在點與搜尋點
```
接下來我們要把步驟分成紀錄與搜尋。紀錄是指更新當前節點(cur)的資訊；而搜尋，則是向周圍尋找沒找過的，並放入代辦清單。當queue清空(沒有點需要搜尋)，搜尋就可以結束(代表地圖被填滿或沒找到)。
另外queue的長度也代表了可通行點的數量。
用陣列實作queue:
```cpp
node qq[1048576];//2^20
```
如果會的話，用vector也可以。
#### 如何紀錄
==把起點存進去queue!!!==這是我們第一個紀錄的點，並希望從這個點向四周搜尋。
```cpp
qq[0].x=Sx;
qq[0].y=Sy;
qq[0].dis=0;
```
維護兩個指針i,j，分別代表queue的head跟尾巴，重複直到i=j或i>j(等價於在i<j時執行)，也就是重複到queue空掉。
```cpp
for (i=0, j=1; i<j; i++)
{
cur=qq[i];
//...nxt初始化(與cur有關)與條件檢查
if(搜到新的點nxt){
qq[j] = nxt;
j++;
}
}
```
小結:
queue的性質(first in first out 排隊的感覺)可以保證會先把dis=n的所有點紀錄一遍，同時把搜到的丟進queue，再搜dis=n+1的所有點。qq[0]記得初始化。
### 如何搜尋?
1. 檢查是否為終點
2. 搜尋上下左右
1. nxt.dis = cur.dis + 1(要比上一個dir+1)
2. 檢查邊界條件
#### 1
直接跟終點比較就好
```cpp
if (cur.x == ex && cur.y == ey) {
return cur.dis;
}
```
#### 2-1
以本題而言，要搜尋上下左右可以建表(後面有宣告具體值就不用給陣列長度)，來表達上下左右的位移值，兩個陣列剛好會是sin跟cos的90\*n度的值相同。
```cpp
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
```
再用迴圈把四個方向都做一次，並且記得更新dis
```cpp
for (k=0; k<4; k++)
{
nxt = cur;
nxt.x += dx[k];
nxt.y += dy[k];
nxt.dis++;//important!!!這個沒做會直接暴死
//.....其他的東東
}
```
#### 2-2
##### 2-2-1 nxt是否在範圍內
n,m根據題意為二維陣列的大小。
```cpp
if(nxt.x >= 0 && nxt.x < n
&& nxt.y >= 0 && nxt.y < m)
```
很美的對齊。
##### 2-2-2 是否為牆壁&&是否使用過
```cpp
if( board[nxt.x][nxt.y] != '#'
&& !used[nxt.x][nxt.y] ) {
//...確認後加入點
}
```
## Q3:如何停下?
本題為有終點的題目，所以只要比較cur跟終點是否相同即可得知最短距離dis(上面有code了)。
找不到就
```cpp
return -1
```
## Q4:Init
### 全域
```cpp
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
//建表
int n, m;
string board[1024];
//io
struct node
{
int x, y;
int dis;
};
node qq[1048576];
bool used[1024][1024];
```
### BFS函數內
```cpp
int i, j, k;
node cur, nxt;
```
used要初始化為0
起點要對qq[0]跟used初始化
### 開始搜尋的時候
cur要對nxt初始化
cur要根據建表的位移量位移
dis++!!!
## Q5:IO
隨便做一做。(指input&output)
記得一邊檢查是否為起終點，用變數維護
### 檢查
沒有起、終點(Sx等，先設成-1)
另有一些細節需要前往[廣度優先搜尋 - HackMD](https://hackmd.io/@sa072686/cp/%2FVXHUmlgOTPGNxV9FWbdukA)收看
# 程式碼結構
## init
```cpp
#include<bits/stdc++.h>
using namespace std;
//
int n,m;
string board[1024];
//io
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
//方向位移
struct node{
int x,y,dis;
};
node qq[1048576];
bool used[1024][1024];
//搜尋要用的東西 可以背起來
```
## bfs
#### 參數
```cpp
(int_sx, int _sy, int _ex, int _ey, int n, int m)
```
#### init
##### 宣告
```cpp
int i, j, k;
node cur, nxt;
```
##### qq
```cpp
// 將所有起點放進 queue 中
qq[0].x = _sx;
qq[0].y = _sy;
qq[0].dis = 0;
```
##### used
```cpp
//把所有的used設為0
memset(used,0,sizeof(used));
// 先將所有起點標記為「已探索」
used[_sx][_sy] = true;
```
#### queue
```cpp
for(i=0,j=1;i<j;i++){
//...
}
```
##### init
```cpp
cur=qq[i];
```
##### 檢查終點
```cpp
if(cur.x == _ex && cur.y == _ey){
return cur.dis;
}
```
##### 向四個方向搜尋
###### init
```cpp
nxt=cur;
nxt.x+=dx[k];
nxt.y+=dy[k];
nxt.dis++;//important
```
###### 條件檢查+紀錄
```cpp
if(nxt.x >= 0 && nxt.x <n
&& nxt.y >= 0 && nxt.y <m){
if(board[nxt.x][nxt.y]!='#'
&& !used[nxt.x][nxt.y]){
used[nxt.x][nxt.y]=true;
qq[j] = nxt;
j++;
}
}
```
## main
```cpp
int main(){
cin>>n>>m;//n直m橫
int i,j;
int Sx=-1,Sy=-1,Ex=-1,Ey=-1;//條件檢查
for(i=0;i<n;i++){
for(j=0;j<m;j++){
cin>>board[i][j];
if(board[i][j]=='S'){
Sx=i;
Sy=j;
}
else if(board[i][j]=='E'){
Ex=i;
Ey=j;
}
}
}
if(Sx==-1||Ex==-1){//條件檢查
cout<<-1;
}
else cout<<bfs(Sx,Sy,Ex,Ey,n,m);
}
```
![[BFS_Code]]
# 參考資料
- [Ch19 BFS 廣度優先搜尋 - HackMD](https://hackmd.io/@CLKO/BkxmExS8J4?type=view)
- 圖很讚
- [搜尋 - HackMD](https://hackmd.io/@tw20000807/search#/12/19)
- [廣度優先搜尋 - HackMD](https://hackmd.io/@sa072686/cp/%2FVXHUmlgOTPGNxV9FWbdukA)
## 原本講義裡的code(含註解)
```cpp
int n, m;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
string board[1024];
struct node
{
int x, y;
int dis;
};
node qq[1048576];
bool used[1024][1024];
int bfs(int sx, int sy, int ex, int ey)
{
int i, j, k;
node cur, nxt;
memset(used, 0, sizeof(used));//將used陣列填滿false
// 將所有起點放進 queue 中
qq[0].x = sx;
qq[0].y = sy;
qq[0].dis = 0;
// 先將所有起點標記為「已探索」
used[sx][sy] = true;
// 依序看過 queue 中所有的點
// i 為目前要看的點；j 為新的點進來時要放的空白位置
for (i=0, j=1; i<j; i++)
{
cur = qq[i];
// 檢查是否為終點
if (cur.x == ex && cur.y == ey)
{
// 如果是，回報最小步數
return cur.dis;
}
// 窮舉上下左右四個方向，尋找可通行地點
for (k=0; k<4; k++)
{
nxt = cur;
nxt.x += dx[k];
nxt.y += dy[k];
nxt.dis++;
// 最優先檢查是否在範圍內，以防存取到不正常的陣列 index
if (nxt.x >= 0 && nxt.x < n
&& nxt.y >= 0 && nxt.y < m)
{
// 確定在範圍內，才檢查是否可通行和是否已探索
if (board[nxt.x][nxt.y] != '#'
&& !used[nxt.x][nxt.y])
{
// 設為已探索並加入 queue 中
used[nxt.x][nxt.y] = true;
qq[j] = nxt;
j++;
}
}
}
}
// 如果找過所有可探索範圍，未能發現終點，即為無解
return -1;
}
```
{%hackmd @sa072686/__style %}
Sign in with Wallet
Connect another wallet