1.什么是dfs，以及算法的基礎是什么？

dfs:深度優(yōu)先搜索算法，是一種用于遍歷或搜索樹或圖的算法.沿著樹的深度遍歷樹的節(jié)點，盡可能深的搜索樹的分支。當節(jié)點v的所在邊都己被探尋過，搜索將回溯到發(fā)現(xiàn)節(jié)點v的那條邊的起始節(jié)點。這一過程一直進行到已發(fā)現(xiàn)從源節(jié)點可達的所有節(jié)點為止。如果還存在未被發(fā)現(xiàn)的節(jié)點，則選擇其中一個作為源節(jié)點并重復以上過程，整個進程反復進行直到所有節(jié)點都被訪問為止。屬于盲目搜索。簡單來說就是一條路走到黑，直到?jīng)]路了，或者找到結果才返回。

深度優(yōu)先搜索算法的基礎：遞歸與回溯

遞歸與回溯是相輔相成的，有遞歸就會有回溯，遞歸函數(shù)的下面部分就是回溯的過程以及回溯的邏輯

回溯是一種純暴力搜索。

2.使用原因

雖然深度優(yōu)先搜索算法的效率很低，但是有些問題只能通過dfs來解決，有些時候多重循環(huán)就照不出來結果

能夠解決的問題有：

1.組合問題? ? ? ? ?

2.切割問題

3.子集問題

4.排列問題

5.棋盤問題

3.如何去理解深度優(yōu)先搜索的回溯算法

回溯算法是一個很抽象的東西，但是所有的回溯算法都可以抽象成一個樹狀結構，可以將其抽象成一個n叉樹問題。樹的深度取決于要搜索問題的層數(shù)，樹的寬度取決于每個節(jié)點處理集合的大小。

回溯法的模版：

void 函數(shù)名（參數(shù)）//回溯算法的參數(shù)一般比較多，要根據(jù)具體情況進行分析
{
    if(終止條件)
      {
         收集最后節(jié)點結果
         return  ;
      }
//單層搜索的邏輯:
    for(集合的元素）//遍歷的是集合里的每一個元素，也可能是集合節(jié)點的子節(jié)點個數(shù)
      {
          處理節(jié)點
          遞歸函數(shù)
          回溯操作（撤銷處理節(jié)點的操作）
      }
    return ；
}

基本上一般的回溯問題都可以通過這個模版的變形從而解決問題

4.例題以及AC代碼（C語言）

1.第一題

這是洛谷上的一道dfs的入門題，我們通過這題來了解一下dfs

#include <stdio.h>
int n,m,t,p,q;//n和m分別代表迷宮有多少行和列，t代表有多少個障礙物，p和q是障礙物的坐標
int sx,sy,fx,fy;//輸入起始位置和終止位置坐標
int a[6][6];//棋盤數(shù)組
int b[6][6];//標記數(shù)組，若元素是1，則代表這個位置已經(jīng)訪問過了，不用再次訪問
int next[4][2]={{1,0},{0,1},{-1,0},{0,-1}};//要進行操作的集合，分別代表右，下，左，上的移動
int count=0;//統(tǒng)計共有多少種方法
void dfs(int x,int y)//進行回溯的函數(shù)
{
    int dx,dy;//代替x，y進行移動操作，這樣回溯的時候不用回溯x和y，只需要回溯標記就好，更簡潔
    if(x==fx&&y==fy)//終止條件，當x和y到達終止位置時，會將次數(shù)加一，并且終止遞歸
    {
        count++;
        return ;
    }
    for(int i=0;i<4;i++)//遍歷移動集合，進行移動
    {
        dx=x+next[i][0];//移動后的行坐標
        dy=y+next[i][1];//移動后的列坐標
        if(dx<1||dx>n||dy<1||dy>m)//假如數(shù)組越界就可以直接跳過（即邊界的判斷條件）
        {
            continue;
        }
        if(b[dx][dy]==0&&a[dx][dy]==0)//這個位置沒有被訪問過
        {
            b[dx][dy]=1;//標記訪問
            dfs(dx,dy);//繼續(xù)遞歸
            b[dx][dy]=0;//回溯
        }
    }
    return ;
}
int main()
{
    scanf("%d%d%d",&n,&m,&t);
    scanf("%d%d%d%d",&sx,&sy,&fx,&fy);
    b[sx][sy]=1;//將其實位置標記為1，代表一開始就訪問過了
    while(t--)
    {
        scanf("%d%d",&p,&q);
        b[p][q]=1;//將障礙物標記為1，相當于訪問過這樣一視同仁代碼更加簡潔
    }
    dfs(sx,sy);//調用遞歸函數(shù)
    printf("%d\n",count);
}

可以看到這個基礎題的代碼和上述模版十分相似，但是后續(xù)的難題就不能完全依靠模板了，那個只是起到一個輔助的思路，主要還是需要自己思考

2.第二題

首先根據(jù)題意，我們可以知道只有附近八格內，只要連續(xù)就可以構成一個水坑，那么我們就可以想到終止條件就是假如附近八格內沒有水了就可以直接結束了，而函數(shù)里的參數(shù)就是首個出現(xiàn)的水坑，我們要進行循環(huán)的集合就是水坑的附近八格，因此我們可以寫出AC代碼文章來源地址http://www.zghlxwxcb.cn/news/detail-830322.html

#include <stdio.h>
int n,m;
char a[105][105];//定義一個棋盤數(shù)組
int b[105][105];//標記數(shù)組
int count=0;
void dfs(int x,int y)//遞歸函數(shù)
{
    if(a[x][y]=='.')//終止條件就是碰到  .
    { 
        return ;
    }
    int dx,dy;
    for(int i=-1; i<=1; i++)
    {
        for(int j=-1; j<=1; j++)
        {
            dx=x+i;
            dy=y+j;
            if(dx>=0&&dx<=n&&dy>=0&&dy<m&&a[dx][dy]=='W'&&b[dx][dy]==0)
            {
                b[dx][dy]=1;
                dfs(dx,dy);//此處無需回溯，因為需要進行標記
            }
        }
    }
    return ;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0; i<n; i++)
    {
        scanf("%s",a[i]);
    }
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            if(a[i][j]=='W'&&b[i][j]==0)
            {
                dfs(i,j);
                count+=1;
            }
        }
    }
    printf("%d\n",count);
    return 0;
}

到了這里，關于第一周算法訓練（dfs）（深度優(yōu)先搜索算法）的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！