# DFS與BFS
## 一、Depth-first search 深度優先搜尋法 (DFS)
### 1.簡述
DFS是一種用來搜尋一個數或圖的演算法，每當走到一個節點，就會以那個節點為新起始點，往其中一邊搜尋到到底或下一個節點。當已經走遍節點其中一邊的所有可能，才會開始走節點的另外一邊。
### 2.圖例
從上面的樹狀圖可以看出來，DFS的搜尋方式是遇到節點時，會先選擇把某一邊的所有可能路徑走完，才會去走另外一邊。
## 二、Breadth-First Search 廣度優先搜尋 (BFS)
### 1.簡述
BFS也是一種用來搜尋一個數或圖的演算法，但不同於DFS的是遇到節點時，會同時往節點的各個方向走相同的單位搜尋，不像DFS會優先走完其中一邊才走另一邊。
### 2.圖例
從上面的樹狀圖及迷宮可以看出來，BFS的搜尋方式是遇到節點時，會同時往岔路的各個方向搜尋。
## 三、迷宮問題實作-程式碼
以下的C++程式碼將會利用DFS及BFS的方式走由0跟1組成的迷宮（迷宮的常跟寬小於100），0代表路，1代表牆，如下圖所示。
目標是從迷宮的左上角走到最右下角，走過的路不能重複走，並求出最短距離以及路徑。
### 1.DFS
#### (1)列出一條路徑
```c++
#include <iostream>
#include <utility>
#include <deque>
#define N 100
using namespace std;
int map[N][N], visited[N][N]={0};
typedef pair<int, int> p;
int n,m,found=0;
deque<p> path;
void dfs(int x, int y){
if (found==1) return;
visited[x][y]=1;
path.push_back(make_pair(x,y));
if (x==n-1 && y==m-1){
found=1;
cout<<"Path: ";
while(!path.empty()){
cout<<"("<<path.front().first<<","<<path.front().second<<")";
path.pop_front();
cout<<((path.empty())?"\n":"→");
}
cout<<endl;
return;
}
if (x+1<n && visited[x+1][y]==0 && map[x+1][y]==0){
dfs(x+1,y);
path.pop_back();
}
if (y+1<m && visited[x][y+1]==0 && map[x][y+1]==0){
dfs(x,y+1);
path.pop_back();
}
if (x-1>=0 && visited[x-1][y]==0 && map[x-1][y]==0){
dfs(x-1,y);
path.pop_back();
}
if (y-1>=0 && visited[x][y-1]==0 && map[x][y-1]==0){
dfs(x,y-1);
path.pop_back();
}
}
int main(){
cin>>n>>m;
for (int i=0; i<n; i++)
for (int j=0; j<m; j++)
cin>>map[i][j];
dfs(0,0);
if (found==0){
cout<<"No routes accessible.\n";
}
return 0;
}
```
#### (2)顯示最短距離
```c++
#include <iostream>
#include <utility>
#include <deque>
#define N 100
using namespace std;
int map[N][N], visited[N][N]={0};
typedef pair<int, int> p;
int n,m,dis=-2;
deque<p> path;
void dfs(int x, int y){
visited[x][y]=1;
path.push_back(make_pair(x,y));
if (x==n-1 && y==m-1){
if (dis==-1){
dis=path.size()-1;
}
else {
if (path.size()-1<dis) dis=path.size()-1;
}
}
if (x+1<n && visited[x+1][y]==0 && map[x+1][y]==0){
dfs(x+1,y);
visited[x+1][y]=0;
path.pop_back();
}
if (y+1<m && visited[x][y+1]==0 && map[x][y+1]==0){
dfs(x,y+1);
visited[x][y+1]=0;
path.pop_back();
}
if (x-1>=0 && visited[x-1][y]==0 && map[x-1][y]==0){
dfs(x-1,y);
visited[x-1][y]=0;
path.pop_back();
}
if (y-1>=0 && visited[x][y-1]==0 && map[x][y-1]==0){
dfs(x,y-1);
visited[x][y-1]=0;
path.pop_back();
}
}
int main(){
cin>>n>>m;
for (int i=0; i<n; i++)
for (int j=0; j<m; j++)
cin>>map[i][j];
dfs(0,0);
if (dis==-2)
cout<<"No routes accessible.\n";
else
cout<<"Shortest distance: "<<dis<<endl;
return 0;
}
```
#### (3)列出所有路徑
```c++
#include <iostream>
#include <utility>
#include <deque>
#define N 100
using namespace std;
int map[N][N], visited[N][N]={0};
typedef pair<int, int> p;
int n,m,idx=1,found=0;
deque<p> path;
void dfs(int x, int y){
visited[x][y]=1;
path.push_back(make_pair(x,y));
if (x==n-1 && y==m-1){
found=1;
cout<<"Path "<<idx<<":\n";
idx++;
int len=path.size();
for (int i=0; i<len; i++){
cout<<"("<<path[i].first<<","<<path[i].second<<")";
cout<<((i==len-1)?"\n":"→");
}
return;
}
if (x+1<n && visited[x+1][y]==0 && map[x+1][y]==0){
dfs(x+1,y);
visited[x+1][y]=0;
path.pop_back();
}
if (y+1<m && visited[x][y+1]==0 && map[x][y+1]==0){
dfs(x,y+1);
visited[x][y+1]=0;
path.pop_back();
}
if (x-1>=0 && visited[x-1][y]==0 && map[x-1][y]==0){
dfs(x-1,y);
visited[x-1][y]=0;
path.pop_back();
}
if (y-1>=0 && visited[x][y-1]==0 && map[x][y-1]==0){
dfs(x,y-1);
visited[x][y-1]=0;
path.pop_back();
}
}
int main(){
cin>>n>>m;
for (int i=0; i<n; i++)
for (int j=0; j<m; j++)
cin>>map[i][j];
dfs(0,0);
if (found==0){
cout<<"No routes accessible.\n";
}
return 0;
}
```
### 2.BFS
#### (1)列出一條路徑
```c++
#include <iostream>
#include <utility>
#include <deque>
#include <cstring>
#define N 100
using namespace std;
int map[N][N];
typedef pair<int, int> p;
int n,m,routes=1;
deque<p> path;
p pre[N][N];
int nxt[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
void bfs(int x, int y){
path.push_back(make_pair(x,y));
pre[x][y].first=x;
pre[x][y].second=y;
while (path.front().first!=n-1 || path.front().second!=m-1){
if (routes==0) return;
p from=path.front();
path.pop_front();
for (int i=0; i<4; i++){
p to;
to.first=from.first+nxt[i][0];
to.second=from.second+nxt[i][1];
if (to.first<0 || to.first>=n || to.second<0 || to.second>=m) continue;
if (map[to.first][to.second] || pre[to.first][to.second].first != -1) continue;
routes++;
path.push_back(to);
pre[to.first][to.second].first=from.first;
pre[to.first][to.second].second=from.second;
}
routes--;
}
}
void print(int x, int y){
if(pre[x][y].first != x || pre[x][y].second != y)
print(pre[x][y].first, pre[x][y].second);
cout<<"("<<x<<","<<y<<")";
cout<<((x==n-1&&y==m-1)?"\n":"→");
}
int main(){
cin>>n>>m;
for (int i=0; i<n; i++)
for (int j=0; j<m; j++)
cin>>map[i][j];
memset(pre,-1,sizeof(pre));
bfs(0,0);
if (routes==0)
cout<<"No routes accessible.\n";
else{
cout<<"Path: ";
print(n-1,m-1);
}
return 0;
}
```
#### (2)顯示最短距離
```c++
#include <iostream>
#include <utility>
#include <deque>
#include <cstring>
#define N 100
using namespace std;
int map[N][N];
typedef pair<int, int> p;
int n,m,dis=0,routes=1;
deque<p> path;
p pre[N][N];
int nxt[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
void bfs(int x, int y){
path.push_back(make_pair(x,y));
pre[x][y].first=x;
pre[x][y].second=y;
while (path.front().first!=n-1 || path.front().second!=m-1){
if (routes==0) return;
p from=path.front();
path.pop_front();
for (int i=0; i<4; i++){
p to;
to.first=from.first+nxt[i][0];
to.second=from.second+nxt[i][1];
if (to.first<0 || to.first>=n || to.second<0 || to.second>=m) continue;
if (map[to.first][to.second] || pre[to.first][to.second].first != -1) continue;
routes++;
path.push_back(to);
pre[to.first][to.second].first=from.first;
pre[to.first][to.second].second=from.second;
}
routes--;
}
}
void print(int x, int y){
if(pre[x][y].first != x || pre[x][y].second != y){
print(pre[x][y].first, pre[x][y].second);
dis++;
}
}
int main(){
cin>>n>>m;
for (int i=0; i<n; i++)
for (int j=0; j<m; j++)
cin>>map[i][j];
memset(pre,-1,sizeof(pre));
bfs(0,0);
print(n-1,m-1);
if (routes==0)
cout<<"No routes accessible.\n";
else
cout<<"Shortest distance: "<<dis<<endl;
return 0;
}
```
### 3.附註
實際上在測跑程式碼的時候我還讓它印出迷宮的圖及座標方便觀看。
印圖的程式碼如下：
```c++
#include <iomanip>
void show(){
cout<<endl<<" y";
for (int i=0; i<m; i++){
cout<<" "<<setfill('\0')<<setw(2)<<i;
}
cout<<endl<<" x ";
for (int i=0; i<3*m+1; i++){
cout<<"-";
}
cout<<endl;
for (int i=0; i<n; i++){
cout<<setfill('\0')<<setw(2)<<i<<" |";
for (int j=0; j<m; j++){
cout<<" "<<map[i][j];
}
cout<<endl;
}
cout<<endl;
}
```
有很多細節是為了美觀打的，像是setfill、setw是為了讓數字對齊。
## 四、迷宮問題實作-結果及說明
### 1.正常測資
```c++
6 8
0 0 0 0 0 0 1 1
1 0 1 0 1 0 0 0
0 0 1 1 1 0 1 0
0 1 1 0 0 0 0 0
0 0 0 0 1 1 0 1
1 0 1 0 0 0 0 0
```
以下結果將會為以上面的數值當作輸入
#### (1)列出一條路徑(DFS&BFS)
##### DFS：
##### BFS：
從以上可以看出兩者顯示的是不同到達終點的路徑。
DFS的作法中，遇到岔路的時候，會根據我設定優先行進的方向繼續走到底，走到終點馬上回傳，因此回傳的不一定是距離最短的路徑。
BFS的作法中，遇到岔路的時候，會同時往各個方向走相同的單位，當其中一邊走到終點時馬上回傳，因次回傳的路徑即是走完迷宮的最短路徑。
#### (2)顯示最短距離(DFS&BFS)
因為用DFS跟BFS印出來的結果長得一模一樣，因此就只放一張圖。
DFS的作法中，因為只印出一條路徑的結果不一定是最短距離，因此我讓它跑完所有可能的路徑，再找出其中得最短路徑算出最短距離。
BFS的作法中，因為回傳的路徑已經是最短距離，所以利用這條路徑算出最短距離即可。
#### (3)列出所有路徑(DFS)
利用DFS，我讓它用遞迴跑完走完迷宮的所有可能路徑。
至於BFS比較麻煩，在我能力範圍內還想不出來要怎麼做QAQ
### 2.走不出去的迷宮
```c++
6 8
0 0 0 0 0 0 1 1
1 0 1 0 1 0 0 0
0 0 1 1 1 0 1 0
0 1 1 0 0 1 0 1
0 0 1 0 1 1 0 1
1 0 1 0 0 0 0 0
```
這裡我對上面第一組測資做了一些改變，讓迷宮變成無解。
#### 結果
很顯然五個程式碼的結果印出來會長一模一樣，因此一樣省略其他圖。至於如何判斷無解兩種方法不太一樣。
DFS的作法中，必須把每一種路徑跑完，確定每一種路徑都無法到達終點，才可以確定無解。
BFS的作法中，我是讓它在走迷宮的同時記錄每一刻還有多少路能走，因此當某一刻判斷出來已經沒有路能走，且沒有回傳任何一條能走到終點的路徑，即代表這個迷宮無解。
### 3.超大迷宮
```
15 28
0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0
0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 0 1
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1
0 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 0 1
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 1 0 1 0 0 0 1 1 1 1 1 1 0 1 0 0 1 0 0 1 1 1 1
0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0
0 0 1 0 0 1 0 1 1 1 1 1 1 0 0 0 1 0 1 0 0 1 1 1 1 1 0 0
0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0
0 0 1 0 0 1 0 1 0 0 0 1 1 1 1 1 1 0 1 0 0 1 0 0 1 1 1 1
0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0
0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0
```
接下來這組測資是一條超大的迷宮，並且非常極端的測資，兩格寬的路根本折磨人。
#### (1)列出一條路徑(DFS&BFS)
##### DFS
##### BFS
這個測資對DFS跟BFS來說都還不算太困難，但如果測資設計的非常擊敗，DFS可能會跑稍微久一點，因為DFS一次只跑一邊，而BFS是每一邊都跑。
從上面的結果又可以再次驗證DFS回傳的路徑不一定是最短的，但BFS回傳的路徑即是最短路徑。
#### (2)顯示最短距離(DFS&BFS)
理論上兩個程式跑出來都要是同個結果，但對DFS來說，這個測資要跑太久了，因為DFS會先把所有路徑都跑完再找最短路徑。但其實會造成這個測資要跑太久的主要原因是兩格寬的路，會增加太多可能的路徑。如果有太多莫名其妙的岔路可能也會造成它跑比較久。
相反的，這個測資對BFS來說根本輕輕鬆鬆，因為它是每一邊同時跑，最先回傳的路徑即是最短路徑。
```c++
15 28
0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0
0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 0 1
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1
0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 0 1
0 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 0 1
0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 1
0 1 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0
0 0 1 1 0 1 0 1 0 1 0 1 1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 1
1 0 1 1 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 1 1 0 0 0 0 0 0
1 0 1 1 0 1 0 1 1 1 1 1 1 0 0 0 1 0 1 0 0 1 1 1 1 1 0 1
1 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 1 0 1 0 0 0 0 0 0
1 0 1 0 1 1 0 1 1 1 0 1 1 1 1 1 1 0 1 1 0 1 1 0 1 1 1 1
1 0 1 0 1 1 0 1 0 1 0 0 0 0 0 0 1 0 1 1 0 1 0 0 0 0 0 0
1 0 1 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 0 1
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0
```
基於好奇，我又改了一下測資的迷宮，把兩格寬的路變成一格寬，測出來DFS就還是可以在短時間跑完。
同時，測出來的最短距離一樣是47，因為改變的路寬不至於影響最短距離。
#### (3)列出所有路徑(DFS)
要用DFS跑完這個非常極端的測資真的要花太多時間，因為至少有幾萬條路徑，小弟我就附上正在跑結果的某一段畫面吧orz。
(我還很有耐心的等到一萬條路徑以上
這是用上面簡化過、把路壓縮過後的測資跑出來的結果，因為還是有不少可能的路徑，就只附上終止後的結果吧。
## 五、結論
經過以上的迷宮實作，我深刻地了解到DFS及BFS適合用在不一樣的功能。雖然對比較小或比較單純的測資來說，DFS跟BFS都能在短時間內跑完，但對比較大或複雜的測資就能看出差異。
1. 如果是要求出最短路徑，BFS效率高很多。因為BFS只要一直擴大範圍搜尋，先到終點回傳的路徑即是最短路徑；相反地，DFS需要跑完所有路徑才能求出最短路徑。
2. 如果是要求出其中一條路徑，BFS的穩定度稍微高一點。因為如果測資設計的非常複雜，DFS可能會跑稍微久一點，但BFS比較不會被測資的擊敗程度影響，因為它是同時往四面八方搜尋。
3. 如果是要窮舉出所有可能路徑，DFS則比較適合。雖然我自己也寫不出BFS的窮舉法，但我感覺BFS的演算法本來就不適合做這類的窮舉，DFS則比較適合暴力搜尋。
4. 其實BFS還有一個致命的缺點，那就是會耗費太多記憶體，原因出在BFS可能會花很多記憶體把各個分散開來的點的位置存進陣列。
#### 總結：DFS跟BFS各有優缺點，在一般的情況用DFS或BFS都可以。BFS耗記憶體，但如果DFS的樹過長，可以考慮用BFS；如果要求出最佳解，用BFS比較好；如果要窮舉，用DFS會比較好。遇到問題的時候，應該具體去分析，選擇要用哪種演算法。
Sign in with Wallet
Connect another wallet