深度优先搜索（DFS）是一种基于栈结构遍历或搜索树或图的算法，核心策略为“不撞南墙不回头”，即沿路径深入探索直至无路可走再回溯。该算法支持递归与迭代两种实现方式，时间复杂度为 O(V+E)。文章解析了 DFS 的核心原理、三色标记法及递归栈机制，提供了 C++ 递归版、迭代版及二叉树遍历的代码示例。同时涵盖连通分量检测、路径总和计算及全排列生成等典型应用场景，并总结了常见误区与优化建议，帮助开发者掌握 DFS 的实际应用。
DFS 的核心思想可以用一句俗语概括：'不撞南墙不回头'。它从起点出发，沿着一条路径尽可能深地探索，直到无法继续（没有未访问的邻接点或到达目标），然后回溯到上一个分支点，选择另一条未走过的路径继续探索，直到遍历完所有可达节点。
形象比喻：你在迷宫中，随便选一个方向，一直往前走，遇到死胡同就退回到上一个岔路口，换一个方向继续走。这个过程就是 DFS。
我们通过一个简单的树形结构来可视化 DFS 的工作过程（节点访问顺序用数字标记）：
A(1)
/ \
B(2) E(5)
/ \ \
C(3) D(4) F(6)
从 A 出发的 DFS 遍历顺序为：A → B → C → D → E → F 具体步骤：
在 DFS 执行过程中，常用三种颜色标记节点状态，这有助于理解递归栈和回溯：
这个标记法在环检测、拓扑排序等高级应用中至关重要。
DFS 通常用递归实现，天然契合'深入 - 回溯'的过程：
DFS(节点 u):
标记 u 为已访问（白色 → 灰色）
对于 u 的每个邻接节点 v:
如果 v 未被访问:
DFS(v)
标记 u 为完全处理（灰色 → 黑色）
递归的本质是系统栈。每次递归调用都会将当前状态（节点、局部变量）压入系统栈，回溯时从栈顶弹出。因此，DFS 也可以显式使用栈来实现非递归版本，避免递归深度限制。
// 显式栈模拟 DFS
stack<int> stk;
stk.push(start);
while (!stk.empty()) {
int cur = stk.top();
stk.pop();
if (!visited[cur]) {
visited[cur] = true;
for (int nei : graph[cur]) {
if (!visited[nei]) stk.push(nei);
}
}
}
| 特性 | 说明 |
|---|---|
| 遍历顺序 | 沿着深度优先，可能先深后广 |
| 空间复杂度 | O(h)，h 为递归深度（树高） |
| 时间复杂度 | O(V+E)，每个节点和边访问一次 |
| 是否保证最短路径 | ❌ 不保证 |
| 适用场景 | 连通性检测、回溯问题、拓扑排序、路径存在性 |
使用 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>
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);
}
应用场景：社交网络中的朋友圈划分、图像连通域标记等。
#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;
}
应用场景：路径规划、决策树回溯（如求所有和为某值的路径）。
#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;
}
应用场景：密码破解、排列组合枚举、旅行商问题初始排列。
#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;
}
| 误区 | 正确做法 |
|---|---|
| 忘记标记 visited | 进入 DFS 前立即标记，防止重复访问 |
| 回溯时忘记撤销 | 如果在递归前修改了状态（如 path），递归后一定要还原 |
| 递归深度过大导致栈溢出 | 改用迭代栈，或调整系统栈大小 |
| 在无向图中遍历所有节点 | 主函数要遍历每个节点，对未访问的调用 DFS（处理非连通图） |
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online