深度优先搜索(DFS)算法详解：从原理到C++实战

目录

1.深度优先搜索(DFS)核心原理:

1.1 核心思想：一条路走到黑

1.2 工作过程详解

1.3 三色标记法

1.4 算法步骤（递归版本）

1.5 递归与栈的关系

1.6 关键特性总结

2.深度优先搜索(DFS)动画演示理解

2.1动画演示理解

3.基本演示代码和实用兼容代码

3.1基本代码演示

3.2实用兼容代码

1. 连通分量检测（无向图）

2. 二叉树路径总和 II（返回所有满足条件的路径）

3. 全排列生成（回溯法）

4.注意事项

1.深度优先搜索(DFS)核心原理:

1.1 核心思想：一条路走到黑

DFS 的核心思想可以用一句俗语概括：“不撞南墙不回头”。它从起点出发，沿着一条路径尽可能深地探索，直到无法继续（没有未访问的邻接点或到达目标），然后回溯到上一个分支点，选择另一条未走过的路径继续探索，直到遍历完所有可达节点。

形象比喻：你在迷宫中，随便选一个方向，一直往前走，遇到死胡同就退回到上一个岔路口，换一个方向继续走。这个过程就是 DFS。

1.2 工作过程详解

我们通过一个简单的树形结构来可视化 DFS 的工作过程（节点访问顺序用数字标记）：

 A(1) / \ B(2) E(5) / \ \ C(3) D(4) F(6)

从 A 出发的 DFS 遍历顺序为：A → B → C → D → E → F
具体步骤：

1. 访问 A，标记已访问。
2. 从 A 的第一个邻接点 B 出发，访问 B，标记。
3. 从 B 的第一个邻接点 C 出发，访问 C，标记。
4. C 无未访问邻接点，回溯到 B。
5. 从 B 的下一个邻接点 D 出发，访问 D，标记。
6. D 无未访问邻接点，回溯到 B；B 也无其他邻接点，回溯到 A。
7. 从 A 的下一个邻接点 E 出发，访问 E，标记。
8. 从 E 的第一个邻接点 F 出发，访问 F，标记。
9. F 无未访问邻接点，回溯到 E；E 无其他邻接点，回溯到 A。
10. A 所有邻接点访问完毕，结束。

1.3 三色标记法

在 DFS 执行过程中，常用三种颜色标记节点状态，这有助于理解递归栈和回溯：

• 白色：尚未发现的节点（未被访问）。
• 灰色：已发现但尚未处理完所有邻接点的节点（当前在递归栈中）。
• 黑色：所有邻接点都已处理完毕的节点（已完成探索）。

这个标记法在环检测、拓扑排序等高级应用中至关重要。

1.4 算法步骤（递归版本）

DFS 通常用递归实现，天然契合“深入-回溯”的过程：

DFS(节点 u): 标记 u 为已访问（白色 → 灰色） 对于 u 的每个邻接节点 v: 如果 v 未被访问: DFS(v) 标记 u 为完全处理（灰色 → 黑色）

1.5 递归与栈的关系

递归的本质是系统栈。每次递归调用都会将当前状态（节点、局部变量）压入系统栈，回溯时从栈顶弹出。因此，DFS 也可以显式使用栈来实现非递归版本，避免递归深度限制。

// 显式栈模拟 DFS stack<node> stk; stk.push(start); while (!stk.empty()) { node cur = stk.top(); stk.pop(); if (!visited[cur]) { visited[cur] = true; for (每个邻接点 nei) { if (!visited[nei]) stk.push(nei); } } }

1.6 关键特性总结

2.深度优先搜索(DFS)动画演示理解

2.1动画演示理解

使用HTML制作了一个简单的动画演示 包含二叉树和有向图的演示

动图演示/视频演示

HTML部分样式代码(需要可以直接使用)

 <style> * { box-sizing: border-box; font-family: 'Segoe UI', Roboto, 'Helvetica Neue', sans-serif; } body { background: linear-gradient(145deg, #f6f9fc 0%, #e9f1f8 100%); min-height: 100vh; margin: 0; display: flex; justify-content: center; align-items: center; padding: 20px; } .card { max-width: 1000px; width: 100%; background: rgba(255,255,255,0.75); backdrop-filter: blur(8px); border-radius: 40px; box-shadow: 0 20px 40px rgba(0,15,30,0.2), 0 4px 12px rgba(0,0,0,0.05); padding: 30px 30px 40px; border: 1px solid rgba(255,255,255,0.6); } h1 { margin: 0 0 8px 0; font-weight: 600; font-size: 2.2rem; color: #0a2a44; letter-spacing: -0.5px; display: flex; align-items: center; gap: 12px; } h1 small { font-size: 1rem; font-weight: 400; background: #1e3a5f; color: white; padding: 6px 14px; border-radius: 40px; letter-spacing: 0.3px; } .sub { color: #2c3e66; margin: 0 0 25px 0; font-size: 1.05rem; border-left: 5px solid #3a6ea5; padding-left: 18px; background: rgba(58, 110, 165, 0.04); border-radius: 0 20px 20px 0; } .canvas-container { background: #ffffffd9; border-radius: 32px; padding: 20px; box-shadow: inset 0 2px 6px rgba(0,0,0,0.04), 0 12px 24px -8px rgba(0,35,70,0.2); border: 1px solid rgba(255,255,255,0.7); } canvas { display: block; width: 100%; height: auto; background: #ffffff; border-radius: 24px; box-shadow: 0 4px 12px rgba(0,0,0,0.05); cursor: pointer; transition: box-shadow 0.2s; } canvas:active { box-shadow: 0 2px 4px rgba(0,0,0,0.1); } .info-panel { display: flex; flex-wrap: wrap; gap: 25px; margin: 25px 0 20px; align-items: stretch; } .stack-box { flex: 2; min-width: 250px; background: #f0f4fa; border-radius: 28px; padding: 18px 22px; box-shadow: 0 8px 18px -6px rgba(0,32,64,0.12); border: 1px solid #ffffff; } .visited-box { flex: 3; min-width: 280px; background: #f0f4fa; border-radius: 28px; padding: 18px 22px; box-shadow: 0 8px 18px -6px rgba(0,32,64,0.12); border: 1px solid #ffffff; } .label { font-size: 0.85rem; text-transform: uppercase; letter-spacing: 1px; font-weight: 600; color: #1e3a5f; margin-bottom: 10px; display: flex; align-items: center; gap: 8px; } .label span { background: #1e3a5f; color: white; padding: 4px 12px; border-radius: 30px; font-size: 0.75rem; } .stack-content, .visited-content { font-family: 'JetBrains Mono', 'Fira Code', monospace; font-size: 1.2rem; background: #ffffffc0; padding: 15px 18px; border-radius: 20px; min-height: 60px; border: 1px solid #cdddec; color: #0a2a44; word-break: break-all; box-shadow: inset 0 1px 4px #00000008; } .action-badge { margin-top: 12px; font-size: 1rem; font-weight: 500; color: #1e4f7a; background: #d3e3f5; padding: 8px 16px; border-radius: 30px; display: inline-block; } .control-bar { display: flex; flex-wrap: wrap; gap: 12px; margin: 28px 0 20px; align-items: center; justify-content: center; } button, .selector { background: white; border: none; padding: 12px 22px; border-radius: 60px; font-weight: 600; font-size: 0.95rem; box-shadow: 0 6px 14px rgba(0,35,70,0.1); display: inline-flex; align-items: center; gap: 8px; transition: all 0.15s; border: 1px solid rgba(255,255,255,0.8); cursor: pointer; color: #1e3a5f; } button:hover { background: #e3efff; transform: translateY(-2px); box-shadow: 0 12px 20px -8px #1e3a5f40; } button:active { transform: translateY(1px); box-shadow: 0 2px 6px #0000001a; } select { background: white; border: none; padding: 12px 30px 12px 22px; border-radius: 60px; font-weight: 500; appearance: none; background-image: url("data:image/svg+xml;utf8,<svg xmlns='http://www.w3.org/2000/svg' viewBox='0 0 24 24' fill='none' stroke='%231e3a5f' stroke-width='2'><polyline points='6 9 12 15 18 9'/></svg>"); background-repeat: no-repeat; background-position: right 18px center; background-size: 14px; box-shadow: 0 6px 14px rgba(0,35,70,0.1); } .speed-slider { display: flex; align-items: center; gap: 10px; background: #ffffffd0; padding: 6px 18px 6px 22px; border-radius: 60px; box-shadow: 0 6px 14px rgba(0,35,70,0.1); } .gif-button { background: #1e3a5f; color: white; border: 1px solid #ffffff60; } .gif-button:hover { background: #2b4b78; } .step-indicator { font-weight: 600; background: #cbddec; padding: 8px 20px; border-radius: 60px; font-size: 0.95rem; } footer { text-align: center; color: #3a5f7a; font-size: 0.85rem; margin-top: 30px; opacity: 0.8; } </style>

3.基本演示代码和实用兼容代码

3.1基本代码演示

C++递归:

void dfs_recursive(const Graph& graph, int node, unordered_set<int>& visited) { visited.insert(node); cout << node << " "; // 访问节点 for (int neighbor : graph[node]) { if (visited.find(neighbor) == visited.end()) { dfs_recursive(graph, neighbor, visited); } } }

C++栈版本:

void dfs_iterative(const Graph& graph, int start) { unordered_set<int> visited; stack<int> stk; stk.push(start); while (!stk.empty()) { int node = stk.top(); stk.pop(); if (visited.find(node) == visited.end()) { visited.insert(node); cout << node << " "; // 将邻居逆序压栈，使访问顺序与递归相近 const auto& neighbors = graph[node]; for (auto it = neighbors.rbegin(); it != neighbors.rend(); ++it) { if (visited.find(*it) == visited.end()) { stk.push(*it); } } } } }

C++二叉树遍历:

struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; void dfs_tree(TreeNode* root) { if (!root) return; cout << root->val << " "; // 前序 dfs_tree(root->left); dfs_tree(root->right); }

3.2实用兼容代码

1. 连通分量检测（无向图）

应用场景：社交网络中的朋友圈划分、图像连通域标记等。

#include <iostream> #include <vector> #include <stack> using namespace std; void dfs(int node, vector<vector<int>>& graph, vector<bool>& visited, vector<int>& component) { visited[node] = true; component.push_back(node); for (int neighbor : graph[node]) { if (!visited[neighbor]) dfs(neighbor, graph, visited, component); } } vector<vector<int>> findConnectedComponents(vector<vector<int>>& graph, int n) { vector<bool> visited(n, false); vector<vector<int>> components; for (int i = 0; i < n; ++i) { if (!visited[i]) { vector<int> comp; dfs(i, graph, visited, comp); components.push_back(comp); } } return components; } int main() { // 图：0-1-2 3-4 vector<vector<int>> graph = {{1}, {0,2}, {1}, {4}, {3}, {}}; int n = 6; auto comps = findConnectedComponents(graph, n); cout << "连通分量:" << endl; for (auto& comp : comps) { for (int x : comp) cout << x << " "; cout << endl; } return 0; }

2. 二叉树路径总和 II（返回所有满足条件的路径）

应用场景：路径规划、决策树回溯（如求所有和为某值的路径）。

#include <iostream> #include <vector> using namespace std; struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} TreeNode(int x, TreeNode* l, TreeNode* r) : val(x), left(l), right(r) {} }; void dfs(TreeNode* node, int currentSum, int targetSum, vector<int>& path, vector<vector<int>>& res) { if (!node) return; currentSum += node->val; path.push_back(node->val); if (!node->left && !node->right && currentSum == targetSum) { res.push_back(path); } else { dfs(node->left, currentSum, targetSum, path, res); dfs(node->right, currentSum, targetSum, path, res); } path.pop_back(); } vector<vector<int>> pathSum(TreeNode* root, int targetSum) { vector<vector<int>> res; vector<int> path; dfs(root, 0, targetSum, path, res); return res; } int main() { // 构建树 TreeNode* root = new TreeNode(5); root->left = new TreeNode(4, new TreeNode(11, new TreeNode(7), new TreeNode(2)), nullptr); root->right = new TreeNode(8, new TreeNode(13), new TreeNode(4, nullptr, new TreeNode(1))); int target = 22; auto paths = pathSum(root, target); cout << "路径总和为 " << target << " 的路径:" << endl; for (auto& p : paths) { for (int v : p) cout << v << " "; cout << endl; } return 0; }

3. 全排列生成（回溯法）

应用场景：密码破解、排列组合枚举、旅行商问题初始排列。

#include <iostream> #include <vector> using namespace std; void dfs(vector<int>& nums, vector<bool>& used, vector<int>& path, vector<vector<int>>& res) { if (path.size() == nums.size()) { res.push_back(path); return; } for (int i = 0; i < nums.size(); ++i) { if (!used[i]) { used[i] = true; path.push_back(nums[i]); dfs(nums, used, path, res); path.pop_back(); used[i] = false; } } } vector<vector<int>> permute(vector<int>& nums) { vector<vector<int>> res; vector<int> path; vector<bool> used(nums.size(), false); dfs(nums, used, path, res); return res; } int main() { vector<int> nums = {1,2,3}; auto perms = permute(nums); cout << "全排列:" << endl; for (auto& p : perms) { for (int v : p) cout << v << " "; cout << endl; } return 0; }

4.注意事项