深度优先搜索（DFS）是一种优先沿着一条路径遍历到无法继续前进时，再回溯到上一个分叉点选择其他路径的算法，在C++中常用于图遍历、树遍历、回溯类问题求解等场景。
DFS的核心思想
DFS的核心原则是“深度优先，回溯补全”，从起始节点出发，每次优先选择未访问过的相邻节点继续深入，直到当前路径没有可访问的相邻节点，再回退到上一个节点选择其他未访问的相邻节点，直到所有可达节点都被访问完毕。
递归实现DFS（最常用方式）
递归实现DFS的逻辑和算法本身的回溯逻辑高度契合，代码简洁易读，是大多数场景下的首选实现方式。下面给出通用的递归DFS模板，适用于图、树等多种结构。
通用递归模板
#include <iostream>
#include <vector>
using namespace std;
// 标记节点是否被访问过
vector<bool> visited;
// 图的邻接表表示，这里以无向图为例
vector<vector<int>> graph;
// DFS递归函数，u为当前访问的节点
void dfs(int u) {
// 标记当前节点为已访问
visited[u] = true;
// 处理当前节点，比如输出节点值
cout << u << " ";
// 遍历当前节点的所有相邻节点
for (int v : graph[u]) {
// 如果相邻节点未被访问，则递归调用DFS
if (!visited[v]) {
dfs(v);
}
}
}
int main() {
int n = 5; // 节点数量，假设节点编号为0到4
graph.resize(n);
visited.resize(n, false);
// 构建图的边，这里示例添加几条边
graph[0].push_back(1);
graph[0].push_back(2);
graph[1].push_back(3);
graph[2].push_back(4);
// 无向图需要添加反向边
graph[1].push_back(0);
graph[2].push_back(0);
graph[3].push_back(1);
graph[4].push_back(2);
// 从节点0开始DFS遍历
cout << "DFS遍历结果：" << endl;
dfs(0);
return 0;
}
模板说明
visited数组用于避免重复访问节点，防止死循环，这是DFS实现中必不可少的组件。graph是图的存储结构，可根据实际需求替换为树的子节点数组、二维矩阵的相邻位置等结构。- 递归终止条件隐含在
if (!visited[v])的判断中，当没有未访问的相邻节点时，递归会自动回退。
栈模拟实现DFS
递归实现本质是使用了系统调用栈，当递归深度过大时可能会出现栈溢出问题，此时可以使用显式栈来模拟递归过程，下面是栈模拟的通用模板。
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
vector<bool> visited;
vector<vector<int>> graph;
void dfs_stack(int start) {
stack<int> st;
// 将起始节点入栈
st.push(start);
visited[start] = true;
while (!st.empty()) {
int u = st.top();
st.pop();
// 处理当前节点
cout << u << " ";
// 遍历相邻节点，注意栈是后进先出，这里逆序入栈可以保证和递归顺序一致
for (auto it = graph[u].rbegin(); it != graph[u].rend(); ++it) {
int v = *it;
if (!visited[v]) {
visited[v] = true;
st.push(v);
}
}
}
}
int main() {
int n = 5;
graph.resize(n);
visited.resize(n, false);
// 构建相同的图结构
graph[0].push_back(1);
graph[0].push_back(2);
graph[1].push_back(3);
graph[2].push_back(4);
graph[1].push_back(0);
graph[2].push_back(0);
graph[3].push_back(1);
graph[4].push_back(2);
cout << "栈模拟DFS遍历结果：" << endl;
dfs_stack(0);
return 0;
}
DFS模板的适用场景
上述两个模板可以直接复用在多种场景中，只需要调整graph的存储结构和节点处理逻辑即可：
- 树的前序、中序、后序遍历，只需要将
graph替换为树的子节点数组即可。 - 二维矩阵的连通区域查找，将每个矩阵位置作为节点，上下左右相邻位置作为相邻节点。
- 回溯类问题如全排列、组合求和，将每一步的选择作为相邻节点，在递归中增加选择记录和撤销选择的步骤即可。
注意事项
- 访问标记数组的大小要和节点数量匹配，避免越界访问。
- 无向图的边需要双向添加，否则会出现节点无法访问的问题。
- 如果是求解路径类问题，需要在递归过程中维护路径数组，在到达目标节点时记录路径。