DFS 深度优先搜索CSP-J

💡 核心思想

DFS 是一种遍历图或树的策略：从起点出发，沿一条路走到底，走不动了再回溯到上一个分叉点尝试其他路径。用递归实现最自然，也可以用栈实现。常用于连通性判断、路径搜索、全排列生成等。

🎯 直觉理解

DFS 就像走迷宫——遇到岔路先选一条走到底，走到死胡同再折回来换另一条。BFS 则像是"洪水填充"——从起点开始，先到达所有距离为1的地方，再到达距离为2的地方。

📝 算法流程

1. 标记当前节点已访问
2. 处理当前节点
3. 递归访问所有未访问的邻居
4. 回溯时如需搜索所有路径，取消标记

$$\text{时间复杂度：} O(V + E) \text{（每个顶点和边访问一次）}$$

📊 复杂度分析

💻 参考实现（C++）

#include <bits/stdc++.h>
using namespace std;
vector<int> g[100005];
bool vis[100005];
void dfs(int u) {
    vis[u] = true;
    cout << u << " ";
    for (int v : g[u]) {
        if (!vis[v]) dfs(v);
    }
}
int main() {
    int n, m; cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u); // 无向图
    }
    dfs(1);
    return 0;
}

⚠️ 常见坑点

📚 相关题目