DFS

Tip

B站讲解
 CSDN

1. DFS（深度优先搜索）

DFS 全称：

Depth First Search

中文叫：

深度优先搜索

它的核心思想是：

沿着一条路一直走到底，走不通再返回继续搜索。

例如走迷宫时：

先选一条路
能走就继续走
走到死路后返回
换另一条路继续走

这就是 DFS。

2. DFS 能解决什么问题

DFS 常见用途：

遍历图和树
连通块搜索
回溯问题
全排列 / 组合
迷宫找路径
枚举所有方案

DFS 特别适合：

需要尝试所有可能情况的问题。

3. DFS 的本质

DFS 本质是：

递归或栈模拟递归

搜索顺序像这样：

起点
→ 下一点
→ 再下一点
→ 再下一点
走到底后返回

所以它叫“深度优先”。

4. DFS 基本模板

void dfs(当前状态)
{
    if(终止条件)
    {
        处理答案;
        return;
    }

    标记当前状态;

    for(所有下一步选择)
    {
        if(可以走)
        {
            dfs(下一状态);
        }
    }
}

核心流程：

到达当前点
向下继续搜
搜完返回

5. 二维地图 DFS 模板

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

void dfs(int x, int y)
{
    vis[x][y] = true;

    for(int i = 0; i < 4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if(nx >= 0 && nx < n &&
           ny >= 0 && ny < m &&
           !vis[nx][ny] &&
           g[nx][ny] != '#')
        {
            dfs(nx, ny);
        }
    }
}

适用于：

岛屿问题
连通块
迷宫区域统计

6. 示例：统计岛屿数量

地图：

1 1 0
0 1 0
1 0 1

相连的 1 算一座岛。

做法：

枚举每个格子
遇到没访问过的 1
岛屿数 +1
用 DFS 把整座岛搜完

7. 示例：全排列

输出 1~3 全排列：

DFS 思想：

第1位选谁
第2位选谁
第3位选谁

一层层递归生成答案。

8. DFS 和 BFS 的区别

算法	搜索方式	常见用途
DFS	一条路走到底	枚举、回溯、连通块
BFS	一层一层扩展	最短路

简单理解：

DFS 像钻洞
BFS 像水波扩散

9. 回溯和 DFS 的关系

很多题里：

回溯 = DFS + 撤销选择

例如排列问题：

选数字
dfs()
取消选择

所以回溯题本质常是 DFS。

10. 常见错误

忘记标记访问

会无限递归。

边界判断错

二维题最常见。

终止条件写错

可能少答案或死循环。

递归太深

数据大时可能爆栈。

11. 如何判断用 DFS

看到这些关键词时考虑 DFS：

所有方案
全排列
所有路径
连通块
岛屿数量
搜索整个区域

通常 DFS 很适合。

12. 一句话理解

DFS = 一条路走到底，不通就返回换路。

13. 总结

DFS 是搜索算法核心基础。

记住三点：

递归向下搜索
走到底再返回
适合枚举所有可能

这是回溯题、图搜索题、网格题的高频算法。