目录
一、代码框架
1. 递归实现（简洁，但栈深度受限）
#include <vector>
#include <unordered_set>
using namespace std;
struct Node {
int val;
vector<Node*> neighbors;
};
void dfsRecursive(Node* node, unordered_set<Node*>& visited) {
if (node == nullptr || visited.count(node)) return; // 终止条件
visited.insert(node); // 标记已访问
// 处理当前节点（前序操作）
for (auto neighbor : node->neighbors) {
dfsRecursive(neighbor, visited); // 递归访问相邻节点
}
// 处理当前节点（后序操作）
}2. 显式栈实现（避免递归栈溢出）
void dfsIterative(Node* start) {
if (start == nullptr) return;
stack<Node*> stk;
unordered_set<Node*> visited;
stk.push(start);
visited.insert(start);
while (!stk.empty()) {
Node* node = stk.top();
stk.pop();
// 处理当前节点
for (auto it = node->neighbors.rbegin(); it != node->neighbors.rend(); ++it) {
Node* neighbor = *it;
if (!visited.count(neighbor)) {
visited.insert(neighbor);
stk.push(neighbor); // 反向压栈以保证顺序
}
}
}
}二、特点
深度优先：沿一条路径探索到底，直到无法继续才回溯（类似“不撞南墙不回头”）。
空间复杂度低：递归实现为
O(h)（树的高度），显式栈实现同理。非最优解：首次找到的解不一定最短（对比BFS的“层序”特性）。
回溯特性：通过递归或栈自然支持状态回退，适合排列组合问题。
需记录访问状态：图遍历必须标记已访问节点，防止重复访问（树无需）。
三、搜索过程
初始化：从起点出发，压入栈或开始递归。
深入探索：访问第一个未探索的相邻节点，重复直到无法深入。
回溯机制：当无法继续时，回退到上一个节点尝试其他分支。
终止条件：所有可达节点均被访问。
四、示例
树的前序遍历：
递归顺序：
A → B → D → (回溯) → B → E → (回溯) → A → C显式栈顺序：
A → B → D → E → C（取决于压栈顺序）
图的遍历（存在环）：
过程：
A → B → C → F → E → D（需记录visited防止循环）
五、C++实现关键细节
访问标记：使用
unordered_set<Node*>或布尔数组（节点编号连续时）。邻接表顺序：显式栈需反向压栈（如
rbegin/rend）以保证与递归顺序一致。后序操作：递归实现中，处理代码放在遍历邻居之后即为后序操作（常用于树形DP）。
六、应用场景
树/图的遍历：前序/后序遍历、连通性检测。
回溯问题：排列组合（如全排列、子集）、N皇后问题。
路径问题：寻找一条可行路径（无需最短）、拓扑排序。
连通分量：计算无向图的连通区域数量。
七、经典问题示例
二叉树的最大深度（递归DFS）：
int maxDepth(TreeNode* root) { if (!root) return 0; return 1 + max(maxDepth(root->left), maxDepth(root->right)); }图的连通分量计数：
int countComponents(vector<vector<int>>& graph) { unordered_set<int> visited; int count = 0; for (int i = 0; i < graph.size(); ++i) { if (!visited.count(i)) { dfs(graph, i, visited); count++; } } return count; } void dfs(vector<vector<int>>& graph, int node, unordered_set<int>& visited) { if (visited.count(node)) return; visited.insert(node); for (int neighbor : graph[node]) { dfs(graph, neighbor, visited); } }
八、总结
递归DFS：代码简洁，适合树或小规模图，但需注意栈溢出风险。
显式栈DFS：更灵活可控，适合大规模数据或需要手动管理栈的场景。
核心思想：一路到底再回溯，空间效率高，天然支持回溯操作。