C++ 深度优先搜索（DFS）入门教程

吉士嘉

341人浏览 · 2026-06-05 21:13:15

吉士嘉 · 2026-06-05 21:13:15 发布

一、什么是 DFS（深度优先搜索）？

想象你在一个迷宫里，面前有好几条岔路。DFS 的策略是：

选一条路，一直往深处走，走到死胡同再退回来，换一条路继续走。

这就是 DFS 的核心思想——“一条路走到黑，不行就回头”。它和 BFS（广度优先搜索）是图/树搜索的两大基础算法。

生活类比：你在一个商场找一家店铺，DFS 就像你先坐电梯到顶层，一层一层往下找；而 BFS 则是每一层都先逛一圈再上楼。

二、DFS 的关键概念

• 递归（Recursion）：DFS 通常用递归来实现。递归就是函数自己调用自己，每次调用相当于“往深处走一步”。

• 回溯（Backtrack）：当一条路走不通时，退回到上一个路口，尝试其他方向。

• 访问标记（Visited）：为了避免重复访问同一个节点，我们需要一个数组来记录“这个节点已经来过了”。

• 栈（Stack）：递归底层其实用的就是栈。你也可以用显式的栈来实现 DFS（迭代版本）。

三、DFS 的执行流程（文字版）

以一个简单的图为例，假设我们有如下无向图：

0 --- 1

| |

3 --- 2

从节点 0 出发，DFS 的访问顺序是：

① 访问节点 0，标记为已访问

② 找到 0 的邻居 1，访问节点 1

③ 找到 1 的邻居 2，访问节点 2

④ 找到 2 的邻居 3，访问节点 3

⑤ 3 的邻居（0、2）都已访问，回溯到 2

⑥ 2 的邻居都已访问，回溯到 1

⑦ 1 的邻居都已访问，回溯到 0

⑧ 0 的邻居都已访问，搜索结束！

记住：DFS 的访问顺序取决于邻接表中邻居的存储顺序。不同的顺序会导致不同的遍历路径，但最终所有节点都会被访问到。

四、完整样例代码（C++）

下面是一个完整的、可直接编译运行的 C++ DFS 示例：

#include <iostream>
#include <vector>
using namespace std;
 
// ======== 全局变量 ========
const int MAXN = 1005;          // 最大节点数
vector<int> graph[MAXN];        // 邻接表存图
bool visited[MAXN];             // 访问标记数组
 
// ======== DFS 函数 ========
// 参数 u：当前正在访问的节点
void dfs(int u) {
    // 1. 标记当前节点为已访问
    visited[u] = true;
    cout << "访问节点: " << u << endl;
 
    // 2. 遍历当前节点的所有邻居
    for (int i = 0; i < (int)graph[u].size(); i++) {
        int v = graph[u][i];  // 取出邻居节点
        if (!visited[v]) {    // 如果邻居没被访问过
            dfs(v);           // 递归访问邻居
        }
    }
    // 3. 函数结束时自动回溯
}
 
// ======== 主函数 ========
int main() {
    int n, m;  // n = 节点数, m = 边数
    cout << "请输入节点数和边数: ";
    cin >> n >> m;
 
    cout << "请输入 " << m << " 条边 (格式: u v):" << endl;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);  // 添加 u -> v 的边
        graph[v].push_back(u);  // 无向图，反过来也要加
    }
 
    cout << "======= DFS 遍历结果 =======" << endl;
    dfs(1);  // 从节点 1 开始遍历
 
    return 0;
}

运行示例

输入：

5 4

1 2

1 3

2 4

3 5

输出：

======= DFS 遍历结果 =======

访问节点: 1

访问节点: 2

访问节点: 4

访问节点: 3

访问节点: 5

对应的图结构：1-2-4、1-3-5。DFS 从 1 出发，先走 2→4，回溯后走 3→5。

五、代码逐行解析

▸ 邻接表存图：graph[MAXN] 是一个 vector 数组，graph[u] 里存放节点 u 的所有邻居。比如 graph[1] = {2, 3} 表示节点 1 和节点 2、3 相连。

▸ visited 数组：bool visited[MAXN] 用来记录每个节点是否被访问过。初始化时全部为 false。

▸ dfs(int u) 函数：这是核心函数。进入后先标记已访问，然后遍历所有邻居，对未访问的邻居递归调用 dfs。

▸ 回溯：当 for 循环结束，说明当前节点的所有邻居都处理完了，函数自然返回——这就是回溯，不需要额外写代码。

六、DFS 的常见应用场景

迷宫求解：经典的走迷宫问题，DFS 可以找到从起点到终点的一条路径。

连通分量：判断一张图中有几个独立的“块”（连通分量）。

全排列 / 组合：用 DFS + 回溯生成所有排列或组合。

岟屿问题：LeetCode 经典题，统计网格中岟屿的数量。

树的遍历：二叉树的前序、中序、后序遍历本质上都是 DFS。

拓扑排序：DFS 可以用来判断有向图中是否存在环。

七、DFS vs BFS 对比

对比项	DFS（深度优先）	BFS（广度优先）
策略	一条路走到黑	逐层扩展
数据结构	栈（递归栈）	队列
空间复杂度	O(树的高度)	O(每层最大宽度)
是否找最短路径	不保证	无权图最短路径
适用场景	路径搜索、回溯、排列组合	最短路径、层序遍历