快速了解寬度優先搜尋并用c++實作
1，廣度優先搜尋
q：什麼是廣度優先搜尋？
a：我們以走迷宮為例：
迷宮問題
一個迷宮
00010
01000
00100
11010
01110
其中1為障礙，0為無障礙，入口為（1,1），出口為（m,n),每次移動隻能從一個無障礙單元移動到其周圍4個方向的另外一個無障礙單元
輸入：第一行為兩個整數，m，n，保證1<m,n<100
以下m行，每行n個整數
表示n行m列的0-1矩陣
輸出：輸出路徑坐标，如果沒有路，輸出-1
【輸入樣例】
1 2
0 0
【輸出樣例】
1 1
1 2
利用隊列的特點，一層一層向外尋找拓展可以走的點，直到找到出口為止 （當然，這裡的隊列也可以用其他東西代替）
q：具體實作方法？
a：假設目前位置是（x，y），為了避免回頭重新搜尋上一步，我們将上一步位置設為-1，這樣就可以保證不會回頭。
緊接着，當我們到達目的地的時候，理論上就會找到“最快”的路徑了 。
另外，我們需要用兩個一維數組來實作存儲各個方向的取值 ，可以參考下面代碼
q：我還是看不懂怎麼辦？
a：舉個例子吧
比如地圖
000
101
010
第一步：我們在左上角1,1位置
第二步：存在兩種走法：1,2和2,2
第三步，存在3種走法（不走已經走過的地方）：1,3、3,3和3,1
此時，由于3,3滿足題設，是以得到了最短路徑1,1。2,2。3,3。
事實上，當我們實作的時候，往往是倒着來的：3,3的上一步是2,2.而2,2的上一步是1,1
具體代碼
注：該代碼輸出結果為倒序
注2：該代碼所有的具體解釋請下移
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define N 1000
int m,n;
struct Map
{
int x;
int y;
}
pre[N][N];
bool vist[N][N];
int map[N][N];
int a[4][2]={{-1,0},{0,-1},{1,0},{0,1}};
bool in(int x,int y)
{
if(x<0||x>m||y<0||y>n)return false;
return true;
}
void bfs()
{
queue<Map>q;
while(!q.empty())q.pop();
vist[0][0]=true;
Map cu;
cu.x=0;
cu.y=0;
q.push(cu);
while(!q.empty())
{
cu=q.front();
q.pop();
for(int i=0;i<4;i++)
{
int x=a[i][0]+cu.x;
int y=a[i][1]+cu.y;
if(in(x,y) && !vist[x][y] && !map[x][y])
{
Map temp;
vist[x][y]=true;
temp.x=x;
temp.y=y;
q.push(temp);
pre[x][y].x=cu.x;
pre[x][y].y=cu.y;
}
}
}
}
void PrintWay(int x,int y)
{
if(x==0 && y==0)
{
printf("%d %d\n",x+1,y+1);
return;
}
printf("%d %d\n",x+1,y+1);
PrintWay(pre[x][y].x,pre[x][y].y);
}
int main()
{
cin >> m >> n;
for(int i=0;i<m;i++)
{
getchar();
for(int j=0;j<n;j++)
{
char a;
a=getchar();
map[i][j]=(int)a -48;
}
}
memset(vist,false,sizeof(vist));
bfs();
PrintWay(m-1,n-1);
return 0;
}
對于代碼的具體解釋
1，前設
struct Map
{
int x;
int y;
}
pre[N][N];
bool vist[N][N];
int map[N][N];
int a[4][2]={{-1,0},{0,-1},{1,0},{0,1}};
Map結構：用來記錄x，y坐标
這裡我們設定了三個表，第一個pre，代表的是記錄，記錄該位置之前應該在什麼位置，比如1,2的上一步在1,1 ，那麼
pre[1][2].x = 1;
pre[1][2].y = 1;
這樣的話，我們就可以根據“終點”得到它“上一步”所在的位置，然後不停上一步，最終得到一條反向的路了。（你隻要把終點和起點變化一下，就可以獲得正向的路了）
緊接着，vist用來儲存的是“這條路是否被走過”，如果被走過，則為true，否則為false。目的是為了防止我們在一個地方繞一輩子圈圈。
最後，map用來儲存地圖情況，1是障礙，0是路。
2，确認是否脫離邊界
bool in(int x,int y)
{
if(x<0||x>m||y<0||y>n)return false;
return true;
}
我們每走一步，都要首先确定一件事情：我是不是跑出地圖外面了，是以在這裡要設定一個判斷脫離邊界的函數
3，隊列
隊列是一種特殊的線性表，隻允許在前端删除，後端插入。
進行插入操作的叫做隊尾，删除的叫做隊頭。隊列沒有元素的時候，稱為空隊列。往隊列中加入元素叫做入隊，删除元素叫做出隊
聲明方式 queue<資料類型>名稱; 見上，這裡的Map是我們之前設定的用來記錄坐标的xy
基本方法：
q.push(x);入隊，将x接到隊列末端
q.pop();出隊，将隊列第一個元素删除。
q.front();通路隊頭元素
q.back(); 通路隊尾元素
q.empty();判斷隊列是否為空，是的話傳回true
q.size();獲得隊列中元素個數
4，bfs函數（廣度搜尋函數）
第一部分：
首先清零我們剛剛設定的隊列，并且在隊列内加入第一個坐标：（0,0），并且将判斷已走過的vist的0,0坐标改為true（來表示它已經被走過了）
while(!q.empty())q.pop();
vist[0][0]=true;
Map cu;
cu.x=0;
cu.y=0;
q.push(cu);
第二部分：
将隊列内的資料提取出來進行運算
while(!q.empty())
{
cu=q.front();
q.pop();
接上一步，我們将隊列裡的第一個數的資料提取出來到cu，并且删除這個資料（現在隊列中就為空了）。這樣的話，我們才可以對這個資料進行檢測和運算
第三部分
for(int i=0;i<4;i++)
{
int x=a[i][0]+cu.x;
int y=a[i][1]+cu.y;
if(in(x,y) && !vist[x][y] && !map[x][y])
{
Map temp;
vist[x][y]=true;
temp.x=x;
temp.y=y;
q.push(temp);
pre[x][y].x=cu.x;
pre[x][y].y=cu.y;
}
}
我們判斷向每一個方向前進，是以循環四次，分别嘗試向四個方向前進。
如果出現：
1，不超出邊界（ in(x,y) ）
2，路沒走過（ !vist[x][y] ）
3，路可以走（ !map[x][y] )
那麼我們就執行我們的内容：将“下一步的上一步”設定為“這一步”的坐标
簡單來說，就是我們從（1,1）走到（1,2），就将（1,2）的上一步設為（1,1）
這樣，我們的pre組中，每一步的上一步就都有了。
4，遞歸輸出
在已經知道每一步的上一步後，我們就可以通過遞歸來從終點找到回到起點的路了。
我們隻要建立一個簡單的遞歸，就可以完成這個目的：
void PrintWay(int x,int y)
{
if(x==0 && y==0)//遞歸出口
{
printf("%d %d\n",x+1,y+1);
return;
}
printf("%d %d\n",x+1,y+1);
PrintWay(pre[x][y].x,pre[x][y].y);
}
不懂遞歸請自行百度。
5，主函數，輸入内容，輸出結果
最簡單的一步，将你的所做的一切穿起來
int main()
{
cin >> m >> n;
for(int i=0;i<m;i++)
{
getchar();//用來儲存Enter鍵防止影響正常輸入
for(int j=0;j<n;j++)//建立一個循環，将整個地圖錄入map中
{
char a;
a=getchar();//這裡使用getchar的原因是我們每次隻錄入一個字元
map[i][j]=(int)a -48;
}
}
memset(vist,false,sizeof(vist));//把vist全部化為false,意思是開始的時候哪裡都沒走過
bfs();//搜尋！
PrintWay(m-1,n-1);//列印結果
return 0;
}
![swmm與lisflood-fp源碼如何一起編譯 CMake指令[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)