深度優(yōu)先搜索算法（Depth First Search钠糊，簡稱DFS）
是一種用于遍歷或搜索樹或圖的算法砍艾。 沿著樹的深度遍歷樹的節(jié)點悯衬，盡可能深的搜索樹的分支码耐。
當節(jié)點v的所在邊都己被探尋過或者在搜尋時結點不滿足條件追迟，搜索將回溯到發(fā)現(xiàn)節(jié)點v的那條邊的起始節(jié)點。
整個進程反復進行直到所有節(jié)點都被訪問為止骚腥。
屬于盲目搜索,最糟糕的情況算法時間復雜度為O(!n)敦间。
深度優(yōu)先搜索算法難以尋找最優(yōu)解，僅僅只能尋找有解束铭。其優(yōu)點就是內(nèi)存消耗小
演示
求圖中的V0出發(fā)廓块，是否存在一條路徑長度為4的搜索路徑
有這樣一個解的：V0->V3->V5->V6。
處理過程：
基本模板
int check(參數(shù))
{
if(滿足條件)
return 1;
return 0;
}
void dfs(int step)
{
判斷邊界
{
相應操作
}
嘗試每一種可能
{
滿足check條件
標記
繼續(xù)下一步dfs(step+1)
恢復初始狀態(tài)（回溯的時候要用到）
}
}
實例
1契沫、全排列問題
//全排列問題
#include<stdio.h>
#include<string.h>
int n;
char a[15];
char re[15];
int vis[15];
//假設有n個字符要排列带猴，把他們依次放到n個箱子中
//先要檢查箱子是否為空，手中還有什么字符懈万，把他們放進并標記拴清。
//放完一次要恢復初始狀態(tài)，當?shù)絥+1個箱子時钞速，一次排列已經(jīng)結束
void dfs(int step)
{
int i;
if(step==n+1)//判斷邊界
{
for(i=1;i<=n;i++)
printf("%c",re[i]);
printf("\n");
return ;
}
for(i=1;i<=n;i++)//遍歷每一種情況
{
if(vis[i]==0)//check滿足
{
re[step]=a[i];
vis[i]=1;//標記
dfs(step+1);//繼續(xù)搜索
vis[i]=0;//恢復初始狀態(tài)
}
}
return ;
}
int main(void)
{
int T;
scanf("%d",&T);
getchar();
while(T--)
{
memset(a,0,sizeof(a));
memset(vis,0,sizeof(vis));//對存數(shù)據(jù)的數(shù)組分別初始化
scanf("%s",a+1);
n=strlen(a+1);
dfs(1);//從第一個箱子開始
}
return 0;
}
2贷掖、一個環(huán)由個圈組成，把自然數(shù)1渴语，2苹威，…，N分別放在每一個圓內(nèi)驾凶，數(shù)字的在兩個相鄰圈之和應該是一個素數(shù)牙甫。 注意：第一圈數(shù)應始終為1。
input: N(0~20)
output:輸出格式如下所示的樣品调违。每一行表示在環(huán)中的一系列圓號碼從1開始順時針和按逆時針方向窟哺。編號的順序必須滿足上述要求。打印解決方案的字典順序技肩。
//Prime Ring Problem
//與上面的全排列問題其實思路差不多且轨，只是需要判斷的條件比較多
//化大為小
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int book[25];
int result[25];
int n;
int num;
//判斷是否為素數(shù)
int prime(int n)
{
if(n<=1)
return 0;
int i;
for(i=2;i*i<=n;i++)
{
if(n%i==0)
break;
}
if(i*i>n)
return 1;
return 0;
}
//判斷是否能將當前的數(shù)字放到當前的圈內(nèi)
int check(int i,int step)
{
if((book[i]==0) && prime(i+result[step-1])==1)
{
if(step==n-1)
{
if(!prime(i+result[0]))
return 0;
}
return 1;
}
return 0;
}
void dfs(int step)
{
if(step==n)//判斷邊界
{
int a;
printf("%d",result[0]);
for(a=1;a<n;a++)
{
printf(" %d",result[a]);
}
printf("\n");
return ;
}
int i;
for(i=2;i<=n;i++)//遍歷每一種情況
{
if(check(i,step))//check是否滿足
{
book[i]=1;//標記
result[step]=i;//記錄結果
dfs(step+1);//繼續(xù)往下搜索
book[i]=0;//恢復初始狀態(tài)
}
}
}
int main(void)
{
while(scanf("%d",&n)!=EOF)
{
num++;
memset(result,0,sizeof(result));
memset(book,0,sizeof(book));
result[0]=1;
printf("Case %d:\n",num);//格式比較容易出錯
dfs(1);
printf("\n");
}
return 0;
}
3、油田問題
問題：GeoSurvComp地質調查公司負責探測地下石油儲藏。 GeoSurvComp現(xiàn)在在一塊矩形區(qū)域探測石油旋奢，并把這個大區(qū)域分成了很多小塊泳挥。他們通過專業(yè)設備，來分析每個小塊中是否蘊藏石油至朗。如果這些蘊藏石油的小方格相鄰屉符，那么他們被認為是同一油藏的一部分。在這塊矩形區(qū)域锹引，可能有很多油藏矗钟。你的任務是確定有多少不同的油藏。
input: 輸入可能有多個矩形區(qū)域（即可能有多組測試）嫌变。每個矩形區(qū)域的起始行包含m和n吨艇，表示行和列的數(shù)量，
1<=n,m<=100初澎，如果m =0表示輸入的結束秸应，接下來是n行，每行m個字符碑宴。每個字符對應一個小方格软啼，并且要么是’*’，代表沒有油延柠，要么是’@’祸挪，表示有油。
output: 對于每一個矩形區(qū)域贞间，輸出油藏的數(shù)量贿条。兩個小方格是相鄰的，當且僅當他們水平或者垂直或者對角線相鄰（即8個方向）增热。
//A - Oil Deposits
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
char a[105][105];
int n,m,result;
int dir[8][2]={{1,0},{-1,0},{0,1},{0,-1},{1,1},{-1,-1},{1,-1},{-1,1}};//表示8個方向
int check(int x,int y)//檢查是否有油田
{
if(x>=0&&x<m&&y>=0&&y<n&&a[x][y]=='@')
return 1;
return 0;
}
int dfs(int x, int y)
{
int i,xx,yy;
if(check(x,y))
{
a[x][y]='.'; //統(tǒng)計之后就可以把該油田標記整以，且不用恢復（要不會重復），
//也可以用一個數(shù)組來存每個點的訪問情況峻仇，但是感覺沒必要公黑，浪費空間
for(i=0;i<8;i++)
{
xx=x+dir[i][0];
yy=y+dir[i][1];
dfs(xx,yy);//依次檢查8個方向
}
return 1;
}
return 0;
}
int main(void)
{
int i,j;
while(scanf("%d %d",&m,&n)==2)
{
if(m==0&&n==0)
break;
result = 0;
memset(a,0,sizeof(a));
for(i=0;i<m;i++)
scanf("%s",a[i]);
for(i=0;i<m;i++)//在每一個點都搜索一次
{
for(j=0;j<n;j++)
{
if(dfs(i,j))//找到油田就可以將結果加1
result++;
}
}
printf("%d\n",result);
}
return 0;
}
4、棋盤問題
問題：在一個給定形狀的棋盤（形狀可能是不規(guī)則的）上面擺放棋子摄咆，棋子沒有區(qū)別凡蚜。要求擺放時任意的兩個棋子不能放在棋盤中的同一行或者同一列，請編程求解對于給定形狀和大小的棋盤吭从，擺放k個棋子的所有可行的擺放方案C朝蜘。
input： 輸入含有多組測試數(shù)據(jù)。 每組數(shù)據(jù)的第一行是兩個正整數(shù)涩金，n k谱醇，用一個空格隔開暇仲，表示了將在一個n*n的矩陣內(nèi)描述棋盤，以及擺放棋子的數(shù)目枣抱。 n <= 8 , k <= n 當為-1 -1時表示輸入結束熔吗。 隨后的n行描述了棋盤的形狀：每行有n個字符，其中 # 表示棋盤區(qū)域佳晶， . 表示空白區(qū)域（數(shù)據(jù)保證不出現(xiàn)多余的空白行或者空白列）。
output：對于每一組數(shù)據(jù)讼载，給出一行輸出轿秧，輸出擺放的方案數(shù)目C （數(shù)據(jù)保證C<2^31）。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int n, k, ans;
char str[10][10];
int vis[100];
void dfs(int r, int k)
{
if(k==0)//判斷邊界咨堤，此時棋子已經(jīng)放完
{
ans++;
return;
}
for(int i=r; i<n; i++)//每次都從放過棋子下一行開始搜索菇篡，保證不重復
{
for(int j=0; j<n; j++)
{
//循環(huán)保證行不重復，check保證列不重復
if(str[i][j]=='.' || vis[j]==1)
continue;//不滿足條件直接跳過
vis[j] = 1;//標記
dfs(i+1, k-1);//繼續(xù)下一次標記
vis[j] = 0;//恢復初始狀態(tài)
}
}
}
int main(void)
{
while(1)
{
scanf("%d %d", &n, &k);
getchar();
if(n==-1 && k==-1)
break;
memset(str, '\0', sizeof(str));
memset(vis, 0, sizeof(vis));
ans = 0;
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
str[i][j] = getchar();
getchar();
}
dfs(0, k);//從第0行開始放一喘，此時手中還剩k個棋子
printf("%d\n", ans);
}
return 0;
}
關于連通分量的個數(shù)
在無向圖中驱还，如果從頂點vi到頂點vj有路徑，則稱vi和vj連通凸克。
如果圖中任意兩個頂點之間都連通议蟆，則稱該圖為連通圖，
否則萎战，稱該圖為非連通圖咐容，
則其中的極大連通子圖稱為連通分量，
這里所謂的極大是指子圖中包含的頂點個數(shù)極大蚂维。
例如：一個無向圖有5個頂點戳粒，1-3-5是連通的，2是連通的虫啥，4是連通的蔚约，則這個無向圖有3個連通分量。
連通分量的個數(shù)就是DFS使用的次數(shù)
參考資料：
https://blog.csdn.net/ldx19980108/article/details/76324307#commentBox
https://blog.csdn.net/qq_40763929/article/details/81629800
https://www.cnblogs.com/DWVictor/p/10048554.html
