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

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 关键特性总结

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. 注意事项