深度优先搜索（DFS）可通过递归和非递归实现。递归法利用函数调用栈，代码简洁；非递归法使用显式栈避免栈溢出，适合深度大的图。两者时间复杂度均为O(V+E)，空间复杂度O(V)。
深度优先搜索（DFS）是一种用于遍历或搜索图或树的算法。在C++中，DFS可以通过递归和非递归两种方式实现。下面分别介绍这两种方法，并给出具体代码示例。
递归实现DFS
递归是最直观、最常用的DFS实现方式。它利用函数调用栈自动保存访问路径。
思路： 从起始节点开始，标记为已访问，然后对每个未访问的邻接节点递归调用DFS。
使用一个布尔数组记录节点是否被访问过 用邻接表存储图结构（如vector>） 递归进入每一个未访问的相邻节点
代码示例：
立即学习“C++免费学习笔记（深入）”；
#include #include using namespace std;void dfs_recursive(const vector<vector>& graph, vector& visited, int node) { visited[node] = true; cout << node << " "; for (int neighbor : graph[node]) { if (!visited[neighbor]) { dfs_recursive(graph, visited, neighbor); } }}int main() { int n = 5; // 节点数 vector<vector> graph(n); vector visited(n, false); // 构建图：0-1, 0-2, 1-3, 1-4 graph[0] = {1, 2}; graph[1] = {3, 4}; graph[2] = {}; graph[3] = {}; graph[4] = {}; cout << "递归DFS: "; dfs_recursive(graph, visited, 0); cout << endl; return 0;}
非递归实现DFS
非递归版本使用显式的栈（stack）来模拟函数调用过程，避免递归带来的栈溢出风险，尤其适用于深度很大的图。
思路： 使用STL中的stack保存待访问的节点。每次取出栈顶，标记访问，并将其未访问的邻居压入栈中。
手动维护一个栈结构 先访问当前节点，再将邻居逆序入栈（保证顺序一致） 注意入栈前判断是否已访问，避免重复处理
代码示例：
立即学习“C++免费学习笔记（深入）”；
#include #include #include using namespace std;void dfs_iterative(const vector<vector>& graph, int start) { int n = graph.size(); vector visited(n, false); stack stk; stk.push(start); while (!stk.empty()) { int node = stk.top(); stk.pop(); if (visited[node]) continue; visited[node] = true; cout << node << " "; // 逆序压入邻居，确保先访问编号小的节点 for (auto it = graph[node].rbegin(); it != graph[node].rend(); ++it) { if (!visited[*it]) { stk.push(*it); } } }}int main() { int n = 5; vector<vector> graph(n); graph[0] = {1, 2}; graph[1] = {3, 4}; graph[2] = {}; graph[3] = {}; graph[4] = {}; cout << "非递归DFS: "; dfs_iterative(graph, 0); cout << endl; return 0;}
两种方式对比
递归写法简洁易懂，适合大多数场景；非递归写法控制力更强，适合大深度图或防止栈溢出。
递归依赖系统调用栈，可能栈溢出 非递归使用堆内存的stack，更稳定 非递归需要手动管理访问顺序和入栈方向 两者时间复杂度均为O(V + E)，空间复杂度O(V)基本上就这些。根据实际需求选择合适的方式即可。
以上就是c++++怎么实现深度优先搜索（DFS）_c++中DFS算法的递归与非递归实现的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1482410.html
微信扫一扫 
支付宝扫一扫 
