深度优先搜索（DFS）可通过递归和非递归实现，递归写法简洁但可能栈溢出，非递归用显式栈更安全；1. 递归实现利用函数调用栈自动管理路径，代码清晰；2. 非递归使用stack模拟，需逆序压入邻接点以保证输出一致；3. 访问标记在节点首次访问时设置，防止重复入栈；4. 对于非连通图需多次启动DFS；5. 两种方法均适用于邻接表存储的无向图，扩展后可处理带权图。掌握二者可应对多数图遍历场景。
深度优先搜索（DFS）是图论中一种基础且重要的遍历算法，广泛应用于连通性判断、路径查找、拓扑排序等问题。在C++中，DFS可以通过递归和非递归两种方式实现。下面分别介绍这两种写法，并结合邻接表存储的无向图进行说明。
递归实现DFS
递归写法简洁直观，利用函数调用栈自动管理访问路径。
// 使用邻接表表示图#include <vector>
#include <iostream>
using namespace std;
// 全局变量：图的邻接表、访问标记数组
vector<vector<int>> graph;
vector<bool> visited;
void dfs_recursive(int u) {
visited[u] = true;
cout << u << " "; // 输出当前节点
for (int v : graph[u]) {
if (!visited[v]) {
dfs_recursive(v);
}
}
}
// 初始化图并调用DFS
int main() {
int n = 5; // 节点数
graph.resize(n + 1);
visited.assign(n + 1, false);
// 构建无向图
graph[1].push_back(2); graph[2].push_back(1);
graph[1].push_back(3); graph[3].push_back(1);
graph[2].push_back(4); graph[4].push_back(2);
graph[2].push_back(5); graph[5].push_back(2);
cout << "递归DFS: ";
dfs_recursive(1);
cout << endl;
return 0;
}
非递归实现DFS
非递归使用显式栈（stack）模拟系统调用栈，避免递归带来的栈溢出风险，适合大规模图。
#include <stack>
void dfs_iterative(int start) {
stack<int> st;
st.push(start);
while (!st.empty()) {
int u = st.top();
st.pop();
if (visited[u]) continue;
visited[u] = true;
cout << u << " ";
// 将邻接节点压入栈（逆序保证顺序一致）
for (auto it = graph[u].rbegin(); it != graph[u].rend(); ++it) {
if (!visited[*it]) {
st.push(*it);
}
}
}
}
两种写法对比与注意事项
递归写法代码短，逻辑清晰，但深层图可能引发栈溢出；非递归写法控制力更强，适用于生产环境或大图处理。
立即学习“C++免费学习笔记（深入）”；
- 访问标记应在节点弹出时立即设置，防止重复入栈
- 非递归中逆序遍历邻接表可使输出顺序与递归一致
- 若图不连通，需对每个未访问节点启动一次DFS
- 边权图可在结构体中扩展信息，如pair或自定义Node
