深度優(yōu)先搜索
DFS基本思想
基本步驟：
1.從圖中某個(gè)頂點(diǎn)v0出發(fā)，首先訪問v0;?
2.訪問結(jié)點(diǎn)v0的第一個(gè)鄰接點(diǎn)竞思，以這個(gè)鄰接點(diǎn)vt作為一個(gè)新節(jié)點(diǎn)表谊，訪問vt所有鄰接點(diǎn)。直到以vt出發(fā)的所有節(jié)點(diǎn)都被訪問到衙四，回溯到v0的下一個(gè)未被訪問過的鄰接點(diǎn)，以這個(gè)鄰結(jié)點(diǎn)為新節(jié)點(diǎn)患亿，重復(fù)上述步驟传蹈。直到圖中所有與v0相通的所有節(jié)點(diǎn)都被訪問到。
3.若此時(shí)圖中仍有未被訪問的結(jié)點(diǎn)步藕，則另選圖中的一個(gè)未被訪問的頂點(diǎn)作為起始點(diǎn)惦界。重復(fù)深度優(yōu)先搜索過程，直到圖中的所有節(jié)點(diǎn)均被訪問過咙冗。
基本代碼結(jié)構(gòu)
void DFS( Point P ){
? ? ? ? for(所有P的鄰接點(diǎn)K){
? ? ? ? ? ? ? ? if(K未被訪問){
? ? ? ? ? ? if(k == e)
? ? ? ? ? ? ? ? ? ? ? return true;
? ? ? ? ? ? ? ? ? ? ? 標(biāo)記K;
? ? ? ? ? ? ? ? ? dfs(k);
? ? ? ? ? ? ? ? }
? ? ? ? }
}
廣度優(yōu)先搜索
BFS基本思想
基本步驟：
1.從圖中某個(gè)頂點(diǎn)v0出發(fā)沾歪，首先訪問v0;
2.依次訪問v0的各個(gè)未被訪問的鄰接點(diǎn)；
3.依次從上述鄰接點(diǎn)出發(fā)雾消，訪問它們的各個(gè)未被訪問的鄰接點(diǎn)灾搏。
4.若此時(shí)圖中仍有未被訪問的結(jié)點(diǎn)，則另選圖中的一個(gè)未被訪問的頂點(diǎn)作為起始點(diǎn)立润。重復(fù)廣度優(yōu)先搜索過程狂窑，直到圖中的所有節(jié)點(diǎn)均被訪問過。
基本代碼結(jié)構(gòu)
通常用隊(duì)列(先進(jìn)先出,FIFO)實(shí)現(xiàn)
初始化隊(duì)列Q.
Q={起點(diǎn)s};
? ? ? 標(biāo)記s為己訪問;
while (Q非空) {
取Q隊(duì)首元素u; u出隊(duì);
if (u == 目標(biāo)狀態(tài)) {…}
所有與u相鄰且未被訪問的點(diǎn)進(jìn)入隊(duì)列;
標(biāo)記與u相鄰的點(diǎn)為已訪問;
}
DFS/BFS是競(jìng)賽中最常見的基礎(chǔ)算法桑腮。雖然題目多種多樣泉哈，但無外乎就是套用上文的程序片段，最主要的還是結(jié)合習(xí)題多練習(xí)達(dá)到熟能生巧破讨。
這里呢丛晦，我想多講一點(diǎn)。上面的BFS是使用C++庫(kù)里封裝的隊(duì)列的提陶，這里額外寫一個(gè)不使用封裝隊(duì)列的方法烫沙，就是自己使用一個(gè)數(shù)組來模擬操作，見下方代碼：
#include<bits/stdc++.h>
using namespace std;
int a[105][105],vis[105],n,m;
//a是鄰接矩陣 vis是標(biāo)記 點(diǎn)是否被訪問過
void bfs(int k){ //k是當(dāng)前點(diǎn)的名字
int q[105];
int f,r,i,j;//r表示當(dāng)前BFS路過的點(diǎn)是第r個(gè)點(diǎn)
q[1]=k;
vis[k]=1;
f=1;r=1;
while(f<=r){
i=q[f];
for(j=1;j<=n;j++){
if(a[i][j]>0&&!vis[j]){ //鄰接矩陣中a[i][j]>0 表示 i和j連通
r++;
q[r]=j;
vis[j]=1;
}
}
f++;
}
for(i=1;i<=r;i++) cout<<q[i]<<" ";//輸出當(dāng)前BFS層的點(diǎn)的序號(hào)
}
int main(){
int h,v1,v2;
cin>>m;//點(diǎn)的數(shù)量
cin>>n;//邊的數(shù)量
memset(a,0,sizeof(a));
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++){
cin>>v1>>v2>>h;//每條邊的? 起點(diǎn) 終點(diǎn) 邊長(zhǎng)
a[v1][v2]=a[v2][v1]=h;//無向圖正反對(duì)接
}
for(int i=1;i<=n;i++)if(!vis[i])bfs(i);
return 0;
}
下面給出一些例題和代碼 及時(shí)練習(xí)效果更佳
出棧次序
X星球特別講究秩序隙笆，所有道路都是單行線斧吐。一個(gè)甲殼蟲車隊(duì)又固，共16輛車，按照編號(hào)先后發(fā)車煤率，夾在其它車流中仰冠，緩緩前行。
? ? 路邊有個(gè)死胡同蝶糯，只能容一輛車通過洋只，是臨時(shí)的檢查站，如圖【p1.png】所示昼捍。
? ? X星球太死板识虚，要求每輛路過的車必須進(jìn)入檢查站，也可能不檢查就放行妒茬，也可能仔細(xì)檢查担锤。
? ? 如果車輛進(jìn)入檢查站和離開的次序可以任意交錯(cuò)。那么乍钻，該車隊(duì)再次上路后肛循，可能的次序有多少種？
? ? 為了方便起見银择，假設(shè)檢查站可容納任意數(shù)量的汽車多糠。
? ? 顯然，如果車隊(duì)只有1輛車浩考，可能次序1種夹孔；2輛車可能次序2種；3輛車可能次序5種析孽。
? ? 現(xiàn)在足足有16輛車啊搭伤，親！需要你計(jì)算出可能次序的數(shù)目
這是一個(gè)整數(shù)袜瞬，請(qǐng)通過瀏覽器提交答案闷畸，不要填寫任何多余的內(nèi)容（比如說明性文字）。?
#include<iostream>
using namespace std;
long long count=0;
void dfs(int a,int b,int k){
if(a==16&&b==16&&k==32){
count++;
return;
}
if(a<=16&&b<=16&&a>=b&&k<32){
dfs(a+1,b,k+1);
dfs(a,b+1,k+1);
}
return ;
}
int main(){
dfs(1,0,1);
cout<<count;
return 0;
}
油田
輸入一個(gè)m行n列的字符矩陣吞滞，統(tǒng)計(jì)字符“@”組成多少個(gè)八連塊佑菩。如果兩個(gè)字符“@”所在的格子相鄰（八個(gè)方向），就說明他們屬于同一個(gè)八連塊裁赠。如圖嫂拴，有兩個(gè)八連塊
? *? *? *? * @
? * @ @? * @
? * @? *? * @
@ @ @? * @
@ @? *? * @
方法一：用DFS解決
#include<cstdio>
#include<cstring>
const int maxn=105;
char pic[maxn][maxn];
int m,n,idx[maxn][maxn];
void dfs(int r,int c,int id){
if(r<0||r>=m||c<0||c>=n) return;
if(idx[r][c]>0||pic[r][c]!='@') return;
idx[r][c]=id;
for(int dr=-1;dr<=1;dr++)
for(int dc=-1;dc<=1;dc++)
if(dr!=0||dc!=0)dfs(r+dr,c+dc,id);
}
int main(){
while(scanf("%d%d",&m,&n)==2&&m&&n){
for(int i=0;i<m;i++) scanf("%s",pic[i]);
memset(idx,0,sizeof(idx));
int cnt=0;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
if(idx[i][j]==0&&pic[i][j]=='@') dfs(i,j,++cnt);
printf("%d\n",cnt);
}
return 0;
}
方法二：用BFS解決
#include<bits/stdc++.h>
using namespace std;
const int maxn=105;
int m,n;
int vis[maxn][maxn];
char s[maxn][maxn];
int cnt=0;
int dir[8][2]={{0,1},{1,-1},{-1,-1},{-1,0},{0,-1},{-1,1},{1,0},{1,1}};
typedef struct Node{
? ? int x,y;
}node;
void bfs(int x,int y){
? ? node p,t;
? ? queue<node> q;
? ? p.x=x;
? ? p.y=y;
? ? q.push(p);
? ? while(!q.empty()){
? ? ? ? p=q.front();
? ? ? ? q.pop();
? ? ? ? for(int i=0;i<8;i++){
? ? ? ? ? ? t.x=p.x+dir[i][0];
? ? ? ? ? ? t.y=p.y+dir[i][1];
? ? ? ? ? ? if(t.x<0||t.x>=n||t.x<0||t.y>=m){
? ? ? ? ? ? ? ? continue;
? ? ? ? ? ? }
? ? ? ? ? ? if(!vis[t.x][t.y]&&s[t.x][t.y]=='@'){
? ? ? ? ? ? ? ? vis[t.x][t.y]=1;
? ? ? ? ? ? ? ? q.push(t);
? ? ? ? ? ? }
? ? ? ? }
? ? }
}
int main()
{
? ? while(scanf("%d %d",&n,&m)&&(n+m)){
? ? ? ? memset(vis,0,sizeof vis);
? ? ? ? cnt=0;
? ? ? ? for(int i=0;i<n;i++){
? ? ? ? ? ? scanf("%s",s[i]);
? ? ? ? }
? ? ? ? for(int i=0;i<n;i++){
? ? ? ? ? ? for(int j=0;j<m;j++){
? ? ? ? ? ? ? ? if(!vis[i][j]&&s[i][j]=='@'){
? ? ? ? ? ? ? ? ? ? vis[i][j]=1;
? ? ? ? ? ? ? ? ? ? cnt++;
? ? ? ? ? ? ? ? ? ? bfs(i,j);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? printf("%d\n",cnt);
? ? }
? ? return 0;
}
?
