Skip to content

深度优先搜索 (DFS)

理论

DFS，深度优先搜索，是一种遍历或搜索图或树的算法，意为在遍历时优先往更深的节点走，如果到底了才返回。

DFS最显著的特征是递归调用自己，并对访问过的点打上标记，在遍历时跳过已经访问过的点，以确保每个点只访问一次。

DFS通常的时间复杂度为$O(n+m)$，空间复杂度为$O(n)$（包括栈空间）。其中，n表示点数，m表示边数，邻接矩阵的空间复杂度通常会小于这个量级。

目前大部分算法竞赛都支持无限栈空间，即：栈空间不单独限制，但总内存空间仍然受题面限制。

但大部分操作系统会对栈空间做额外的限制，因此在本地调试时需要一些方式来取消栈空间限制。

在 Windows 上，通常的方法是在 编译选项 中加入 -Wl,--stack=1000000000，表示将栈空间限制设置为 1000000000 字节。

实现

深度搜索优先的一般思路如下：

  1. 确定递归函数及其参数

一般情况，需要至少一个二维数组保存所有路径，一个一维数组保存单一路径。

  1. 确认终止条件

  2. 处理当前节点进入下一节点的逻辑

栈实现

参考代码 
vector<vector<int>> adj;  // 邻接表
vector<bool> vis;         // 记录节点是否已经遍历

void dfs(int s) {
  stack<int> st;
  st.push(s);
  vis[s] = true;

  while (!st.empty()) {
    int u = st.top();
    st.pop();

    for (int v : adj[u]) {
      if (!vis[v]) {
        vis[v] = true;  // 确保栈里没有重复元素
        st.push(v);
      }
    }
  }
}

DFS可以使用栈（Stack）作为遍历中节点的暂存容器。

栈实现的思路是每次循环中弹出栈顶，并检查栈顶对应的顶点是否被标记为已检查。如果是未检查的顶点，就遍历当前顶点对应的链表，将顶点的所有出边压入栈中。

递归实现

模板题

可达路径

题目链接：98. 可达路径

点击展开题目
题目描述

给定一个有 n 个节点的有向无环图，节点编号从 1 到 n。请编写一个函数，找出并返回所有从节点 1 到节点 n 的路径。每条路径应以节点编号的列表形式表示。

输入描述

第一行包含两个整数 N，M，表示图中拥有 N 个节点，M 条边

后续 M 行，每行包含两个整数 s 和 t，表示图中的 s 节点与 t 节点中有一条路径

输出描述

输出所有的可达路径，路径中所有节点之间空格隔开，每条路径独占一行，存在多条路径，路径输出的顺序可任意。如果不存在任何一条路径，则输出 -1。

注意输出的序列中，最后一个节点后面没有空格！ 例如正确的答案是 1 3 5,而不是 1 3 5， 5后面没有空格！

输入示例
5 5
1 3
3 5
1 2
2 4
4 5
输出示例
1 3 5
1 2 4 5
实现代码
点击展开代码 
#include<iostream>
#include<vector>
using namespace std;

//有向无环图
//dfs 数组+vector存

//dfs逻辑：深搜，检查当前节点是否为n
//如果是则输出当前缓存的节点列表并回退
//如果不是则继续搜索
//如果没有下个节点则直接回退

//输出：检查当前是否是第一个元素，若非，则先输出空格，再输出节点

const int MAXN=105,MAXM=505;
int n,m;
vector<int> point[MAXN];
vector<int> path;
int sum=0;           //计数器

void dfs(int p){
    if(p==n){
        for(int _p:path){
            cout<<_p<<" ";
        }
        cout<<n<<endl;
        sum++;
        return;
    }

    if(point[p].size()==0)return;

    path.push_back(p);
    for(int _p:point[p]){
        dfs(_p);
    }
    path.pop_back();
    return;
}

int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int _q,_p;
        cin>>_p>>_q;
        point[_p].push_back(_q);
    }

    //入口节点：1
    dfs(1);

    if(sum==0)cout<<"-1";
}

孤岛问题

计数

题目：99. 计数孤岛

点击展开题目
题目描述

给定一个由 1（陆地）和 0（水）组成的矩阵，你需要计算岛屿的数量。岛屿由水平方向或垂直方向上相邻的陆地连接而成，并且四周都是水域。你可以假设矩阵外均被水包围。

输入描述

第一行包含两个整数 N, M，表示矩阵的行数和列数。

后续 N 行，每行包含 M 个数字，数字为 1 或者 0。

输出描述

输出一个整数，表示岛屿的数量。如果不存在岛屿，则输出 0。

输入示例
4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1
输出示例
3
实现代码
点击展开代码 
#include<iostream>
using namespace std;

//存图：二维表，元素为（类型，访问标记）构成的结构体
//遍历表，
//如果当前陆地未标记：计数器+1，访问该节点的所有相邻节点并标记陆地
//如果当前陆地未标记：跳过

//dfs逻辑：
//参数：当前节点的行和列
//向该节点上下左右四个方向访问，如果是陆地就标记，如果是海洋则跳过；

const int MAX=55;
int n,m;
int sum=0;

struct point{
    bool isvist=false;
    int island=0;
}map[MAX][MAX];

void dfs(int x,int y){
    if(x<1||x>n||y<1||y>m)return;
    if(map[x][y].island==0||map[x][y].isvist)return;

    map[x][y].isvist=true;
    dfs(x-1,y);
    dfs(x,y-1);
    dfs(x+1,y);
    dfs(x,y+1);
}

int main(){
    cin>>n>>m;
    for(int x=1;x<=n;x++){
        for(int y=1;y<=m;y++){
            cin>>map[x][y].island;
        }
    }

    for(int x=1;x<=n;x++){
        for(int y=1;y<=m;y++){
            if(map[x][y].isvist)continue;
            else if(map[x][y].island==1){
                dfs(x,y);
                sum++;
            }
        }
    }
    cout<<sum;

    return 0;
}

最大孤岛面积

题目链接：100. 最大岛屿的面积

点击展开题目
# 题目描述

给定一个由 1（陆地）和 0（水）组成的矩阵，计算岛屿的最大面积。岛屿面积的计算方式为组成岛屿的陆地的总数。岛屿由水平方向或垂直方向上相邻的陆地连接而成，并且四周都是水域。你可以假设矩阵外均被水包围。

# 输入描述

第一行包含两个整数 N, M，表示矩阵的行数和列数。后续 N 行，每行包含 M 个数字，数字为 1 或者 0，表示岛屿的单元格。

# 输出描述

输出一个整数，表示岛屿的最大面积。如果不存在岛屿，则输出 0。

# 输入示例
4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1
# 输出示例
4
实现代码

整体思路和计数问题一致，但需要注意用于存储当前陆地面积的变量area必须放在全局，否则在向下递归到不同分支时会各算各的。

点击展开代码 
#include<iostream>
using namespace std;

//存图：二维表，元素为（类型，访问标记）构成的结构体
//遍历表，
//如果当前陆地未标记：计数器+1，访问该节点的所有相邻节点并标记陆地
//如果当前陆地未标记：跳过

//dfs逻辑：
//参数：当前节点的行和列,当前岛屿块的面积
//向该节点上下左右四个方向访问，如果是陆地就标记，如果是海洋则跳过；

const int MAX=55;
int n,m;
int maxArea=0;
int area=0;

struct point{
    bool isvist=false;
    int island=0;
}map[MAX][MAX];

void dfs(int x,int y){
    if(x<1||x>n||y<1||y>m)return;
    if(map[x][y].island==0||map[x][y].isvist)return;

    map[x][y].isvist=true;
    area++;
    dfs(x-1,y);
    dfs(x,y-1);
    dfs(x+1,y);
    dfs(x,y+1);
}

int main(){
    cin>>n>>m;
    for(int x=1;x<=n;x++){
        for(int y=1;y<=m;y++){
            cin>>map[x][y].island;
        }
    }

    for(int x=1;x<=n;x++){
        for(int y=1;y<=m;y++){
            if(map[x][y].isvist)continue;
            else if(map[x][y].island==1){
                area=0;
                dfs(x,y);
                maxArea=maxArea>area?maxArea:area;
            }
        }
    }
    cout<<maxArea;

    return 0;
}

构造最大面积岛屿

题目链接：104. 建造最大岛屿

点击展开题目
# 题目描述

给定一个由 1（陆地）和 0（水）组成的矩阵，你最多可以将矩阵中的一格水变为一块陆地，在执行了此操作之后，矩阵中最大的岛屿面积是多少。

岛屿面积的计算方式为组成岛屿的陆地的总数。岛屿是被水包围，并且通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设矩阵外均被水包围。

# 输入描述

第一行包含两个整数 N, M，表示矩阵的行数和列数。之后 N 行，每行包含 M 个数字，数字为 1 或者 0，表示岛屿的单元格。

# 输出描述

输出一个整数，表示最大的岛屿面积。

# 输入示例
4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1
# 输出示例
6

数据范围

1 <= M, N <= 50。

实现代码

思路：

1.遍历陆地区域，标记岛屿及其面积，更新最大岛屿总面积为当前最大值 2.遍历海洋区域，在当前区块增加陆地时，检查其上下左右是否存在陆地，如果存在，将岛屿的编号和对应面积存入一个临时的unordered_map容器中；计算当前总面积，更新当前最大总面积

点击展开代码 
#include<iostream>
#include<unordered_map>
#include<utility>
using namespace std;
//存图：结构体数组，包括水陆标记，岛屿编号，访问标记
//unordered_map:存每个编号对应的岛屿的面积

//思路：
//1.遍历陆地区域，标记岛屿及其面积，更新最大岛屿总面积为当前最大值
//2.遍历海洋区域，在当前区块增加陆地时，检查其上下左右是否存在陆地，如果存在，将岛屿的编号和对应面积存入一个临时的unordered_map容器中；计算当前总面积，更新当前最大总面积

const int MAX=55;
int n,m;
int maxArea,currArea;
int landNum=0;
unordered_map<int,int> landArea;
struct point{
    int land=0;
    int landNum;
    bool isVist;
} map[MAX][MAX];

void dfs(int x,int y,int landNum){
    if(x<=0||x>n||y<=0||y>m)return;
    if(map[x][y].land==0||map[x][y].isVist)return;

    currArea++;
    map[x][y].landNum=landNum;
    map[x][y].isVist=true;

    dfs(x-1,y,landNum);
    dfs(x,y-1,landNum);
    dfs(x+1,y,landNum);
    dfs(x,y+1,landNum);
}

pair<int,int> checkArea(int x,int y){
    if(x<=0||x>n||y<=0||y>m)return make_pair(0,0);
    if(map[x][y].land==0)return make_pair(0,0);

    int num=map[x][y].landNum;
    int area=landArea[num];

    return make_pair(num,area);
}

int totalLand(int x,int y){
    unordered_map<int,int> landList;
    landList.emplace(checkArea(x-1,y));
    landList.emplace(checkArea(x+1,y));
    landList.emplace(checkArea(x,y-1));
    landList.emplace(checkArea(x,y+1));

    int sum=1;
    for(pair<int,int> i:landList)sum+=i.second;
    return sum;
}


int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>map[i][j].land;
        }
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if((map[i][j].land==1) && (!map[i][j].isVist) ){
                currArea=0;
                landNum++;
                dfs(i,j,landNum);
                landArea[landNum]=currArea;
                maxArea=maxArea>currArea?maxArea:currArea;
            }
        }
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(map[i][j].land==0){
                currArea=totalLand(i,j);
                maxArea=maxArea>currArea?maxArea:currArea;
            }
        }
    }

    cout<<maxArea;

    return 0;

}

岛屿周长

题目链接：106. 海岸线计算

点击展开题目
# 题目描述

给定一个由 1（陆地）和 0（水）组成的矩阵，岛屿是被水包围，并且通过水平方向或垂直方向上相邻的陆地连接而成的。

你可以假设矩阵外均被水包围。在矩阵中恰好拥有一个岛屿，假设组成岛屿的陆地边长都为 1，请计算海岸线，即：岛屿的周长。岛屿内部没有水域。

# 输入描述

第一行包含两个整数 N, M，表示矩阵的行数和列数。之后 N 行，每行包含 M 个数字，数字为 1 或者 0，表示岛屿的单元格。

# 输出描述

输出一个整数，表示岛屿的周长。

# 输入示例
5 5
0 0 0 0 0 
0 1 0 1 0
0 1 1 1 0
0 1 1 1 0
0 0 0 0 0
# 输出示例
14

数据范围：

1 <= M, N <= 50。

实现代码

对于该类问题，在地图范围大于$1000*1000$后非常容易栈溢出，此时推荐使用BFS。

点击展开代码 
#include<iostream>
using namespace std;

//对于任意陆地节点，向四个方向检索
//如果当前节点为水面，则总周长+1并回退；
//如果当前节点为陆地，则继续搜索；
//如果越界，视为水面

//存图：结构体数组，包括陆地标记、访问标记

const int MAX=55;
int n,m;
int edge=0;

struct point{
    int land=0;
    bool isVist=false;
}map[MAX][MAX];

void dfs(int x,int y){
    if(x<=0||y<=0||x>n||y>m){
        edge++;
        return;
    }
    if(map[x][y].isVist)return;
    if(map[x][y].land==0){
        edge++;
        return;
    }

    map[x][y].isVist=true;
    dfs(x-1,y);
    dfs(x,y-1);
    dfs(x+1,y);
    dfs(x,y+1);
}

int main(){
    cin>>n>>m;
    for(int x=1;x<=n;x++){
        for(int y=1;y<=m;y++){
            cin>>map[x][y].land;
            }
    }

    for(int x=1;x<=n;x++){
        for(int y=1;y<=m;y++){
            if((map[x][y].land==1)&&(!map[x][y].isVist)){
                dfs(x,y);
            }
        }
    }

    cout<<edge;

    return 0;
}

矩阵水流问题

题目链接：103. 高山流水

点击展开题目
# 题目描述

现有一个 N × M 的矩阵，每个单元格包含一个数值，这个数值代表该位置的相对高度。矩阵的左边界和上边界被认为是第一组边界，而矩阵的右边界和下边界被视为第二组边界。

矩阵模拟了一个地形，当雨水落在上面时，水会根据地形的倾斜向低处流动，但只能从较高或等高的地点流向较低或等高并且相邻（上下左右方向）的地点。我们的目标是确定那些单元格，从这些单元格出发的水可以达到第一组边界和第二组边界。

# 输入描述

第一行包含两个整数 N 和 M，分别表示矩阵的行数和列数。

后续 N 行，每行包含 M 个整数，表示矩阵中的每个单元格的高度。

# 输出描述

输出共有多行，每行输出两个整数，用一个空格隔开，表示可达第一组边界和第二组边界的单元格的坐标，输出顺序任意。

# 输入示例
5 5
1 3 1 2 4
1 2 1 3 2
2 4 7 2 1
4 5 6 1 1
1 4 1 2 1
# 输出示例
0 4
1 3
2 2
3 0
3 1
3 2
4 0
4 1
# 提示信息

img

图中的蓝色方块上的雨水既能流向第一组边界，也能流向第二组边界。所以最终答案为所有蓝色方块的坐标。

数据范围：

1 <= M, N <= 100。

实现代码

该题的思路核心在于将可以同时抵达两组边界的点转换为两组边界可以同时抵达的点，以边界的每个点为入口，搜索所有可以抵达的点并标记，最后遍历所有点筛选同时持有两个边界的标记的点。 在这个思路下存图使用一个结构体数组，每个节点包括节点高度、第一边界访问标记和第二边界访问标记。

点击展开代码 
#include<iostream>
using namespace std;

//存图：结构体，结构包括相对高度、是否可以从第一边界可达、是否可以从第二边界可达
//遍历逻辑：遍历地图的四边节点
//输出：遍历地图，检查是否同时可以从第一边界和第二边界抵达。

//dfs
//参数：当前节点的坐标、当前从第x个边界出发
//逻辑：每到达一个节点标记从当前边界可达
//如果已标记/越界：返回

const int MAX=105;
int n,m;

struct point{
    int h;
    bool edge_1=false;
    bool edge_2=false;
}map[MAX][MAX];

void dfs(int x,int y,int edge,int h){
    if(x<0||x>=n||y<0||y>=m)return;
    if(edge==1&&map[x][y].edge_1)return;
    if(edge==2&&map[x][y].edge_2)return;

    if(h>map[x][y].h)return;

    if(edge==1)map[x][y].edge_1=true;
    else map[x][y].edge_2=true;

    dfs(x+1,y,edge,map[x][y].h);
    dfs(x-1,y,edge,map[x][y].h);
    dfs(x,y+1,edge,map[x][y].h);
    dfs(x,y-1,edge,map[x][y].h);
}

int main(){
    cin>>n>>m;
    for(int x=0;x<n;x++){
        for(int y=0;y<m;y++){
            cin>>map[x][y].h;
        }
    }

    for(int i=0;i<m;i++){
        dfs(0,i,1,0);
        dfs(n-1,i,2,0);
    }
    for(int i=0;i<n;i++){
        dfs(i,0,1,0);
        dfs(i,m-1,2,0);
    }

    for(int x=0;x<n;x++){
        for(int y=0;y<m;y++){
            if(map[x][y].edge_1&&map[x][y].edge_2)cout<<x<<" "<<y<<endl;
        }
    }

    return 0;
}