C++深度优先搜索详解（从零开始掌握DFS算法与图遍历）

什么是深度优先搜索？

想象你在走一个迷宫。你选择一条路一直往前走，直到碰到死胡同。这时你会退回上一个岔路口，尝试另一条路。这就是 DFS 的核心思想——“一条路走到黑，不行就回头”。

DFS 常用于：

• 图的连通性检测
• 拓扑排序
• 寻找路径或环
• 解决数独、八皇后等回溯问题

DFS 的两种实现方式

DFS 可以通过 递归 或 栈（显式使用 stack）来实现。下面我们分别介绍这两种方法。

1. 递归实现（推荐初学者使用）

递归是最直观的 DFS 写法。我们用一个 visited 数组记录哪些节点已经被访问过，避免重复访问。

#include <iostream>#include <vector>using namespace std;// 图的邻接表表示vector<vector<int>> graph;vector<bool> visited;// 深度优先搜索函数void dfs(int node) {    cout << "访问节点: " << node << endl;    visited[node] = true; // 标记为已访问    // 遍历当前节点的所有邻居    for (int neighbor : graph[node]) {        if (!visited[neighbor]) {            dfs(neighbor); // 递归访问未访问的邻居        }    }}int main() {    int n = 5; // 节点数量（0 到 4）    graph.resize(n);    visited.assign(n, false);    // 构建图：添加边    graph[0].push_back(1);    graph[0].push_back(2);    graph[1].push_back(3);    graph[2].push_back(4);    cout << "开始深度优先搜索...\n";    dfs(0); // 从节点 0 开始搜索    return 0;}

这段代码展示了如何用 C++深度优先搜索 遍历一个简单图。运行后会按顺序输出访问的节点：0 → 1 → 3 → 2 → 4。

2. 使用栈的非递归实现

如果你担心递归可能导致栈溢出（比如图非常深），可以使用显式的栈结构：

#include <iostream>#include <vector>#include <stack>using namespace std;void dfs_iterative(int start, const vector<vector<int>>& graph) {    int n = graph.size();    vector<bool> visited(n, false);    stack<int> stk;    stk.push(start);    while (!stk.empty()) {        int node = stk.top();        stk.pop();        if (visited[node]) continue;                cout << "访问节点: " << node << endl;        visited[node] = true;        // 注意：为了保持与递归相同的访问顺序，        // 我们需要逆序压入邻居（因为栈是后进先出）        for (auto it = graph[node].rbegin(); it != graph[node].rend(); ++it) {            if (!visited[*it]) {                stk.push(*it);            }        }    }}

时间与空间复杂度

- 时间复杂度：O(V + E)，其中 V 是顶点数，E 是边数。每个节点和每条边最多被访问一次。
- 空间复杂度：O(V)，用于存储 visited 数组和递归栈（或显式栈）。

常见应用场景

掌握 DFS算法实现 后，你可以解决许多经典问题，例如：

• 岛屿数量（LeetCode 200）：用 DFS 标记所有相连的陆地
• 路径是否存在：判断两点是否连通
• 全排列/组合生成：通过回溯+DFS 枚举所有可能

小结

通过本教程，你已经学会了如何用 C++ 实现 深度优先搜索。无论是递归还是栈的方式，核心思想都是“深入探索 + 回溯”。建议你动手编写代码，修改图的结构，观察输出结果，加深理解。

记住，C++图遍历 是算法面试和实际开发中的基础技能。掌握好 DFS，你就迈出了成为算法高手的第一步！

希望这篇 递归搜索教程 对你有帮助。欢迎多加练习，祝你编程愉快！