深度优先搜索 (DFS) 算法原理与 C++ 实现

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 通常用递归实现，天然契合'深入 - 回溯'的过程：

void DFS(int u) {
    // 标记 u 为已访问（白色 → 灰色）
    visited[u] = true;
    for (int v : adj[u]) {
        if (!visited[v]) {
            DFS(v);
        }
    }
    // 标记 u 为完全处理（灰色 → 黑色）
}

1.5 递归与栈的关系

递归的本质是系统栈。每次递归调用都会将当前状态（节点、局部变量）压入系统栈，回溯时从栈顶弹出。因此，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 : adj[cur]) {
            if (!visited[nei]) {
                stk.push(nei);
            }
        }
    }
}

1.6 关键特性总结

特性	说明
遍历顺序	沿着深度优先，可能先深后广
空间复杂度	O(h)，h 为递归深度（树高）
时间复杂度	O(V+E)，每个节点和边访问一次
是否保证最短路径	❌ 不保证
适用场景	连通性检测、回溯问题、拓扑排序、路径存在性

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

2.1 动画演示理解

通过动态演示可以更直观地理解 DFS 的遍历过程，包含二叉树和有向图的示例。动图展示了节点被访问的顺序以及栈的变化情况。

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

3.1 基本代码演示

C++ 递归:

void dfs_recursive(const vector<vector<int>>& 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 vector<vector<int>>& 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>
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. 注意事项

误区	正确做法
忘记标记 visited	进入 DFS 前立即标记，防止重复访问
回溯时忘记撤销	如果在递归前修改了状态（如 path），递归后一定要还原
递归深度过大导致栈溢出	改用迭代栈，或设置递归深度限制
在无向图中遍历所有节点	主函数要遍历每个节点，对未访问的调用 DFS（处理非连通图）