搜尋
通過一定的順序，枚舉每一個資料（經常會通過一些判斷條件去掉無意義的資料，即剪枝），找到想要的資料的過程。
深度優先搜尋（dfs）
深度優先搜尋屬于圖算法的一種，是一個針對圖和樹的算法，應為縮寫為dfs(Depth First Search)。深度優先搜尋是圖論中的經典算法，利用深度優先搜尋算法可以産生目标圖的相應拓撲排序表，利用拓撲排序表可以友善解決很多相關的圖論問題，如最短路徑問題等等。一般運用堆資料結構來輔助實作DFS算法。——百度百科
上面是百度百科關于深度優先搜尋的描述。其實，簡單來說，就是“不撞南牆不回頭”——按照一定的規則，先找一個方向上的資料，如果找到頭還沒找到想要的，那就找另一個方向上的資料。
迷宮
以迷宮為例：
如圖，左上角是起點，右下角是終點。如果給我們做，我們可以一眼看出答案，但是電腦卻很難“看”出來，因為電腦一次隻能看一個格。是以就需要一個一個格子去看是否能走，一直找到中間點。
如果我們規定隻能走上下左右，并且按照深搜的規定，每次選擇按照“上下左右”的順序走，這樣在起點就有下和右兩個方向可以走，先選擇向下走：
走完後，有上、下、右三個方向可以走，但是上已經走過了，是以還是隻有下、右可以走，繼續向下走………………
已經沒有路可以走了，這時就要進行回溯，即往回走，一直回溯到上一次有兩條路可以選擇的時候
也就是這個時候，繼續按照之前的方法走，遇到路口按照“上、下、左、右”的順序選擇方向、遇到死路就回溯，這樣可以一直找到終點。
僞代碼
dfs是以遞歸為基礎的
void dfs(){
//遞歸出口
if(結束條件){
return ;
}
//遞歸主體
for(……){
if(下一步有效){
book[] = 1;//标記已經走過的路
dfs();//進行下一步
book[] = 0;//回溯的時候一定要記住消除影響
}
}
}
廣度優先搜尋（BFS）
廣度優先搜尋是連通圖的一種周遊算法，這一算法也是很多重要的圖的算法的原型。Dijkstra單源最短路徑算法和Prim最小生成樹算法都采用了和廣度優先搜尋類似的思想，屬于一種盲目搜尋法，目的是系統的展開并檢查途中的所有節點，以找尋結果。換句話說，他并不考慮結果的可能位置，徹底的搜過整張圖，直到找到結果為止。基本過程，BFS是從根節點開始，沿着樹（圖）的寬度周遊樹（圖）的節點。如果所有算法均被通路，則算法終止。一般用隊列資料結構來輔助實作BFS算法。
與深度優先搜尋的不撞南牆不回頭不同，廣度優先搜尋更像是步步為營，每次把所有能走的點都存在隊列中，然後一一拿出來，看看拿出來的點所能走到的點，把能走到的點再存進隊列，這樣在迷宮中”鋪“出路來。
迷宮
還是那個迷宮
首先，起點能走的點有右和下，存進隊列
從隊列中取出點，尋找下一層能走的點。
依次往下找，直到找到終點。
僞代碼
q.push(起點);//将起點推入隊列
while(!q.empty()){//當隊列不為空，即：沒有搜完所有點時
temp = q.front();//取出隊列第一個點
q.pop();//将隊列第一個點推出隊列
if(temp是終點) break;
for(……){
q.push(下一步能走的點);//把下一步能走的點推入隊列
book[] = 1;//标記
}
}
例題
- 描述：一個迷宮有R行C列格子組成，有的格子裡有障礙物，不能走；有的格子是空地，可以走。給定一個迷宮，求從左上角走到右下角最少需要走多少步（資料保證一定能走到），隻能在水準方向或垂直方向走，不能斜着走。
- 輸入：第一行是兩個整數，R和C，代表迷宮的長和寬。（1<=R,C<=40）接下來是R行，每行C個字元，代表整個迷宮。空地格子有“.”表示，有障礙物的格子用“#”表示。迷宮左上角和右下角都是“.”。
- 輸出：輸出從左上角走到右下角至少要經過多少步（即至少需要經過多少個空地格子）。計算步數要包括起點和終點。
代碼
#include<bits/stdc++.h>
using namespace std;
//方向數組
int xx[4] = {1,-1,0,0};
int yy[4] = {0,0,1,-1};
//圖的長寬
int l,w;
//存圖的字元串數組
char _map[50][50];
//步數
int step = 1;
int minn = 2500;
//bfs用到的結構體，表示一個坐标
struct node{
int x;
int y;
int def;//第幾步
node(int xx,int yy){x = xx;y = yy;}
};
//深搜
void dfs(int x,int y){
if(x == l - 1&&y == w - 1){
minn = min(minn,step);
}
for(int i = 0;i < 4;i++){
int tx = x + xx[i];
int ty = y + yy[i];
if(tx >= 0&&ty >= 0&&tx < l&&ty < w&&_map[tx][ty] == '.'){
step++;
_map[tx][ty] = '#';
dfs(tx,ty);
_map[tx][ty] = '.';
step--;
}
}
}
//廣搜
void bfs(){
queue<node> q;
while(!q.empty()) q.pop();
node temp(0,0);
temp.def = step++;
q.push(temp);
while(!q.empty()){
temp = q.front();
q.pop();
if(temp.x == l - 1&&temp.y == w - 1){
printf("%d\n",temp.def);
return;
}
for(int i = 0;i < 4;i++){
node tt(temp.x + xx[i],temp.y + yy[i]);
tt.def = temp.def + 1;
if(tt.x >= 0&&tt.y >= 0&&tt.x < l&&tt.y < w&&_map[tt.x][tt.y] == '.'){
_map[tt.x][tt.y] = '#';
q.push(tt);
}
}
}
}
int main()
{
//讀入地圖
scanf("%d%d",&l,&w);
for(int i = 0;i < l;i++)
scanf("%s",_map[i]);
//深搜
/*
dfs(0,0);
printf("%d\n",minn);
*/
//廣搜
step = 1;
bfs();
return 0;
}
/*
5 5
..###
#....
#.#.#
#.#.#
#.#..
*/
題目
poj3984 迷宮問題
poj3278 Catch That Cow
hdu1241 Oil Deposits
poj3414 Pots
hdu 1180 詭異的樓梯
版權聲明：本文為CSDN部落客「w_xy999」的原創文章，遵循CC 4.0 BY-SA版權協定，轉載請附上原文出處連結及本聲明。
原文連結：https://blog.csdn.net/w_xy999/article/details/103017655