深度优先搜索（DFS）通过递归或栈实现，先访问节点并标记，再深入未访问的邻接点，回溯时继续探索其他路径，适用于图和树的遍历。
深度优先搜索（DFS）是一种用于遍历或搜索图和树的算法。它的核心思想是沿着一条路径尽可能深入地访问节点，直到无法继续为止，然后回溯到上一个节点尝试其他路径。在C++中，可以通过递归或栈来实现DFS。下面详细介绍如何在图和树中实现DFS。
图的邻接表表示与DFS实现
在图中，通常使用邻接表来存储节点之间的连接关系。每个节点维护一个相邻节点的列表。
以下是一个无向图的DFS实现示例：
// 使用vector模拟邻接表#include #include iostream>using namespace std;
class Graph {int V; // 节点数量vector> adj; // 邻接表void dfsUtil(int v, vector& visited);
public:Graph(int V);void addEdge(int v, int w);void dfs(int start);};
Graph::Graph(int V) {this->V = V;adj.resize(V);}
void Graph::addEdge(int v, int w) {adj[v].push_back(w);adj[w].push_back(v); // 无向图双向添加}
void Graph::dfsUtil(int v, vector& visited) {visited[v] = true;cout
for (int neighbor : adj[v]) { if (!visited[neighbor]) { dfsUtil(neighbor, visited); }}
}
立即学习“C++免费学习笔记（深入）”；
void Graph::dfs(int start) {vector visited(V, false);dfsUtil(start, visited);}
说明：构造函数初始化邻接表；addEdge添加边；dfsUtil是递归辅助函数，打印当前节点并递归访问未访问的邻居；dfs启动遍历，初始化访问标记数组。
二叉树的DFS遍历
对于二叉树，DFS有三种常见顺序：前序、中序、后序。它们都可通过递归轻松实现。
struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}};
// 前序遍历：根 -> 左 -> 右void preorder(TreeNode* root) {if (root == nullptr) return;cout val left);preorder(root->right);}
// 中序遍历：左 -> 根 -> 右void inorder(TreeNode* root) {if (root == nullptr) return;inorder(root->left);cout val right);}
// 后序遍历：左 -> 右 -> 根void postorder(TreeNode* root) {if (root == nullptr) return;postorder(root->left);postorder(root->right);cout val
每种遍历方式只是处理根节点的位置不同，其余结构一致。可根据需求选择合适顺序。
使用栈实现非递归DFS
递归本质是系统栈的调用，也可以手动用栈模拟，避免递归带来的栈溢出风险，尤其适用于深度较大的结构。
#include
void dfsIterative(Graph& g, int start) {int V = g.V;vector visited(V, false);stack s;
s.push(start);while (!s.empty()) { int v = s.top(); s.pop(); if (!visited[v]) { cout << v << " "; visited[v] = true; } // 将所有未访问的邻接点压入栈（注意顺序可影响输出） for (auto it = g.adj[v].rbegin(); it != g.adj[v].rend(); ++it) { if (!visited[*it]) { s.push(*it); } }}
}
使用栈时要注意：为了保证与递归顺序一致，通常需要逆序压入邻接点。因为栈是后进先出，先压入右边会导致左边先被访问。
基本上就这些。无论是图还是树，DFS的核心就是“一路走到底，走不通再回头”。递归写法简洁直观，适合大多数场景；非递归则更灵活可控。理解访问标记数组的作用和回溯时机是掌握DFS的关键。
以上就是C++怎么实现深度优先搜索(DFS)_C++图与树的遍历算法详解的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1485636.html
微信扫一扫 
支付宝扫一扫 
