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

// 显式栈模拟 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);
        }
    }
}

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