深度优先搜索（DFS）可通过递归和非递归实现，递归写法简洁但可能栈溢出，非递归用显式栈更安全；1. 递归实现利用函数调用栈自动管理路径，代码清晰；2. 非递归使用stack模拟，需逆序压入邻接点以保证输出一致；3. 访问标记在节点首次访问时设置，防止重复入栈；4. 对于非连通图需多次启动DFS；5. 两种方法均适用于邻接表存储的无向图，扩展后可处理带权图。掌握二者可应对多数图遍历场景。
深度优先搜索（DFS）是图论中一种基础且重要的遍历算法，广泛应用于连通性判断、路径查找、拓扑排序等问题。在C++中，DFS可以通过递归和非递归两种方式实现。下面分别介绍这两种写法，并结合邻接表存储的无向图进行说明。
递归实现DFS
递归写法简洁直观，利用函数调用栈自动管理访问路径。
// 使用邻接表表示图
#include
#include iostream>
using namespace std;
// 全局变量：图的邻接表、访问标记数组
vector> graph;
vector visited;
void dfs_recursive(int u) {
visited[u] = true;
cout // 输出当前节点
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_recursive(1);
cout
return 0;
}
非递归实现DFS
非递归使用显式栈（stack）模拟系统调用栈，避免递归带来的栈溢出风险，适合大规模图。
#include
void dfs_iterative(int start) {
stack st;
st.push(start);
while (!st.empty()) {
int u = st.top();
st.pop();
if (visited[u]) continue;
visited[u] = true;
cout
// 将邻接节点压入栈（逆序保证顺序一致）
for (auto it = graph[u].rbegin(); it != graph[u].rend(); ++it) {
if (!visited[*it]) {
st.push(*it);
}
}
}
}
两种写法对比与注意事项
递归写法代码短，逻辑清晰，但深层图可能引发栈溢出；非递归写法控制力更强，适用于生产环境或大图处理。
立即学习“C++免费学习笔记（深入）”；
访问标记应在节点弹出时立即设置，防止重复入栈 非递归中逆序遍历邻接表可使输出顺序与递归一致 若图不连通，需对每个未访问节点启动一次DFS 边权图可在结构体中扩展信息，如pair或自定义Node基本上就这些。掌握这两种写法能应对大多数图遍历问题。
以上就是C++如何实现深度优先搜索(DFS)_C++图论算法中DFS的递归与非递归写法的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1485331.html
微信扫一扫 
支付宝扫一扫 
