中国招标网官方网_设计本家装_海东地区谷歌seo网络优化_重要新闻今天8条新闻

目录

一、代码框架

1. 递归实现（简洁，但栈深度受限）

2. 显式栈实现（避免递归栈溢出）

二、特点

三、搜索过程

四、示例

树的前序遍历：

图的遍历（存在环）：

五、C++实现关键细节

六、应用场景

七、经典问题示例

二叉树的最大深度（递归DFS）：

图的连通分量计数：

八、总结

---

一、代码框架

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); // 反向压栈以保证顺序}}}
}

---

二、特点

1. 深度优先：沿一条路径探索到底，直到无法继续才回溯（类似“不撞南墙不回头”）。

2. 空间复杂度低：递归实现为 O(h)（树的高度），显式栈实现同理。

3. 非最优解：首次找到的解不一定最短（对比BFS的“层序”特性）。

4. 回溯特性：通过递归或栈自然支持状态回退，适合排列组合问题。

5. 需记录访问状态：图遍历必须标记已访问节点，防止重复访问（树无需）。

---

三、搜索过程

1. 初始化：从起点出发，压入栈或开始递归。

2. 深入探索：访问第一个未探索的相邻节点，重复直到无法深入。

3. 回溯机制：当无法继续时，回退到上一个节点尝试其他分支。

4. 终止条件：所有可达节点均被访问。

四、示例

树的前序遍历：

• 递归顺序：A → B → D → (回溯) → B → E → (回溯) → A → C

• 显式栈顺序：A → B → D → E → C（取决于压栈顺序）

图的遍历（存在环）：

• 过程：A → B → C → F → E → D（需记录 visited 防止循环）

---

五、C++实现关键细节

1. 访问标记：使用 unordered_set<Node*> 或布尔数组（节点编号连续时）。

2. 邻接表顺序：显式栈需反向压栈（如 rbegin/rend）以保证与递归顺序一致。

3. 后序操作：递归实现中，处理代码放在遍历邻居之后即为后序操作（常用于树形DP）。

---

六、应用场景

• 树/图的遍历：前序/后序遍历、连通性检测。

• 回溯问题：排列组合（如全排列、子集）、N皇后问题。

• 路径问题：寻找一条可行路径（无需最短）、拓扑排序。

• 连通分量：计算无向图的连通区域数量。

---

七、经典问题示例

1. 二叉树的最大深度（递归DFS）：

   int maxDepth(TreeNode* root) {if (!root) return 0;return 1 + max(maxDepth(root->left), maxDepth(root->right));
   }

2. 图的连通分量计数：

   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：更灵活可控，适合大规模数据或需要手动管理栈的场景。

• 核心思想：一路到底再回溯，空间效率高，天然支持回溯操作。