C++ 深度优先搜索 (DFS) 学习记录

深度优先搜索是一种用于遍历或搜索树或图的算法。所谓深度优先，就是说每次都尝试向更深的节点走。

要说个人理解的话，我的理解大概就是这样：

有一个人去某景区旅游，他现在在景区入口，景区里的一些路，有的能通到出口，有的不能。

这个人呢很倔强，他要一条一条去走，不走到路的尽头绝不回头。

他从第一条路走下去，走到头发现没路了，再回头到上一个分叉点，记下来这个分叉走过了；然后走另一个分叉，全部分叉走完了，再回到分叉点，再往回退一个分叉，记下来这个大分叉走过了没有路，然后走下一个分叉……

如果把这样一个景区抽象为一个图，那么也就是说，深度优先的搜索就是每次都尝试向更深的节点走。

DFS 搜索的实现方式一般是递归。也就是递归调用自身。在每次 DFS 遍历中都会对访问过的点打上标记，在遍历图的时候跳过已标记的点，以确保每个点只访问一次。

复杂度

时间复杂度	空间复杂度

$O(n+m)$ | $O(m)$

实现

寻找路线（走迷宫）

bool DFS(int r,int c){
    // 设定这个位置已经访问
    visited[r][c]=true; 

    // 存储遍历时行走的参数，这样循环遍历的时候方便调用
    // dr 为横着走, dc 为竖着走
    // 顺序分别为：左 右 上 下
    int dr[]={-1, 1, 0, 0};
    int dc[]={0, 0, -1, 1};

    if(/*当前位置为目标位置*/)return true;

    // 遍历图，开始找路
    for(int d=0;d<4;++d){
        int tr=r+dr[d]; // 横向
        int tc=c+dc[d]; // 竖向

        // 如果满足特定条件我就继续找，什么时候找到了 (DFS 返回 True) 就直接结束，这里不回溯
        if(inMap(tr,tc)&&/*满足特定条件*/*&&!visited[tr][tc])
            if(DFS(tr,tc))
                return true;
    }
    // 没找到
    return false;
}

bool inMap(int r,int c){
    return r>=0&&r<n&&c>=0&&c<m;
}

上述代码调用 DFS 时，传入起点坐标，返回 true 则找到，false 则没找到。

例题

深さ優先探索

AC 代码：

#include<iostream>
using namespace std;

char map[505][505];
bool visited[505][505];
int n,m;

bool DFS(int,int);
bool inMap(int,int);


int main(){
    cin >> n >> m;
    for(int i=0;i<n;++i)
        for(int j=0;j<m;++j)
            cin >> map[i][j];
    
    int startx,starty;
    for(int i=0;i<n;++i)
        for(int j=0;j<m;++j)
        if(map[i][j]=='s'){
            startx=i;
            starty=j;
        }
    
    bool res=DFS(startx,starty);
    cout << (res?"Yes\n":"No\n");
    return 0;
}

bool DFS(int r,int c){
    visited[r][c]=true;
    int dr[]={-1, 1, 0, 0};
    int dc[]={0, 0, -1, 1};

    if(map[r][c]=='g')return true;

    for(int d=0;d<4;++d){
        int tr=r+dr[d];
        int tc=c+dc[d];
        if(inMap(tr,tc)&&map[tr][tc]!='#'&&!visited[tr][tc])
            if(DFS(tr,tc))
                return true;
    }
    return false;
}

bool inMap(int r,int c){
    return r>=0&&r<n&&c>=0&&c<m;
}

灌水

AC 代码 (已经过处理)：

#include <iostream>
using namespace std;

char matrix[30][40];
int count = 0;

void DFS(int, int);

int main() {
    for (int i = 0; i < 30; ++i)
        for (int j = 0; j < 40; ++j)
            cin >> matrix[i][j]; // 调试用

    DFS(0, 0);
    cout << count << endl;
    // cout << 541 << endl; 评测机要求必须直接输出结果
    return 0;
}

void DFS(int x, int y) {
    if (x < 0 || x >= 30 || y < 0 || y >= 40 || matrix[x][y] != '0')
        return;
    count++;
    matrix[x][y] = '2';
    DFS(x + 1, y);
    DFS(x - 1, y);
    DFS(x, y + 1);
    DFS(x, y - 1);
}

在这里面没有单独存储已经遍历过的位置，是因为题目要求每走一步，就将这个地方标记为 $2$，也相当于已经标记过了。

最大连通

AC 代码（已经过处理）：

#include <iostream>
#include <cmath>
using namespace std;

char matrix[30][60];
bool visited[30][60];
int count=0,cntmax=0;
void DFS(int,int);

int main()
{
  for(int i=0;i<30;++i)
    for(int j=0;j<60;++j)
      cin >> matrix[i][j];

  for(int i=0;i<30;++i)
      for(int j=0;j<60;++j){
        count=0;
        DFS(i,j);
        cntmax=max(count,cntmax);
      }

  cout << cntmax << endl;
  // cout << 148 << endl; 评测机要求必须直接输出结果
  return 0;
}

void DFS(int x,int y){
  if(x<0||x>=30||y<0||y>=60||matrix[x][y]=='0'||visited[x][y]==1)
    return;
  visited[x][y]=1;
  count++;

  int dx[4]={1,-1,0,0};
  int dy[4]={0,0,-1,1};


  for(int i=0;i<4;++i){
    int nextx=x+dx[i];
    int nexty=y+dy[i];
    if(nextx>=0&&nextx<30&&nexty>=0&&nexty<60&&matrix[nextx][nexty]=='1'&&visited[nextx][nexty]==0){
      DFS(nextx,nexty);
    }
  }
}