5分钟看懂——D~F~S！！

@llx

2025-08-12 13:38:25

发布于：浙江

13阅读

0回复

0点赞

时隔多日我们再次相见！今天我们就来唠一唠DFS！
一句话记住 DFS：
~~像走迷宫，选一条路一直走到头，撞墙了就回头，换条新路继续走！~~

1. 生活例子

你在学校图书馆找《某某》。
DFS 做法：

从进门左手第一排书架开始，一本一本往右找；
走到尽头，发现没有，退后一格，再进下一排；
直到找到书或逛完整馆。
~~虽说你心里知道永远也找不到的~~

2. 算法模板（C++，不到 20 行）
题目：数房间

给一个 n×m 的地图，# 是墙，. 是空地，问有多少个独立房间（上下左右连通）。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;
char g[MAXN][MAXN];
int n, m;

void dfs(int x, int y) {          // 核心 4 行
    if (x < 0 || x >= n || y < 0 || y >= m || g[x][y] != '.') return;
    g[x][y] = '#';                // 标记已访问
    dfs(x-1, y); dfs(x+1, y);     // 上下
    dfs(x, y-1); dfs(x, y+1);     // 左右
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) cin >> g[i];
    
    int ans = 0;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if (g[i][j] == '.') { // 找到新房间
                dfs(i, j);
                ++ans;
            }
    cout << ans;
    return 0;
}

3.为什么要用 DFS？

典型应用	一句话解释	难度
图/树的遍历	打印、统计、收集信息	★☆☆
连通块/连通分量	求岛屿数量、朋友圈	★★☆
路径问题	迷宫寻路、单词接龙	★★☆
拓扑排序	有向无环图（DAG）线性化	★★★
回溯/剪枝	N 皇后、数独、全排列	★★★
二分图判定	染色法	★★☆

一句话总结：“只要问题能抽象成‘在一张图里找东西’，DFS 大概率用得上。”

4. 小练习
把上面代码粘到洛谷p1596 交一交，看是不是 AC？
提示：
条件，DFS判断，八联通还是四联通~

5.通用模板（图的DFS）
以下代码实现了 “从任意起点出发遍历整张图” 的通用 DFS，可直接复制粘贴。

#include <bits/stdc++.h>
using namespace std;

using Graph = vector<vector<int>>;   // 邻接表

// 递归版
void dfs(int u, const Graph& g, vector<bool>& vis,
         const function<void(int)>& work = [](int){}) {
    vis[u] = true;
    work(u);                          // 访问节点 u
    for (int v : g[u])
        if (!vis[v]) dfs(v, g, vis, work);
}

// 非递归版（显式栈）
void dfs_iter(int start, const Graph& g,
              const function<void(int)>& work = [](int){}) {
    int n = g.size();
    vector<bool> vis(n, false);
    stack<int> st;
    st.push(start);
    vis[start] = true;
    while (!st.empty()) {
        int u = st.top(); st.pop();
        work(u);
        for (int v : g[u])
            if (!vis[v]) {
                vis[v] = true;
                st.push(v);
            }
    }
}

/* ------------ 测试 ------------ */
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;                 // 节点数、边数
    cin >> n >> m;
    Graph g(n + 1);           // 1~n
    for (int i = 0; i < m; ++i) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);    // 无向图
    }

    vector<bool> vis(n + 1, false);
    for (int i = 1; i <= n; ++i)
        if (!vis[i]) dfs(i, g, vis, [](int x){ cout << x << ' '; });
    return 0;
}

6.易踩的坑 & 注意事项

维度	复杂度 & 说明	注意事项（坑点）
时间复杂度	O(V + E)<br>每个顶点、每条边最多访问一次	网格图为 O(n·m)，树形图为 O(n)
空间复杂度	O(V)<br>递归栈或显式栈 + visited 数组	网格 1e3×1e3 时递归深度 1e6 可能爆栈；改用 BFS 或手写栈
重复访问	—	必须设 visited 标记；无向图/双向边尤其注意死循环
回溯还原	—	枚举所有方案时需撤销标记（`vis[x]=false`）
剪枝	—	找到答案立即返回；无效状态提前跳过
输入规模	—	n、m > 1e3 时 DFS 常数大，易 TLE；考虑 BFS 或 IDA*
方向/建图	—	无向图要加两条有向边；别把方向搞反
递归深度限制	—	Linux 默认栈 8 MB≈1e5 层；可用 `-Wl,--stack=268435456` 放大或改迭代

~~再会！！~~

有帮助，赞一个

去预览

0/2000

这里空空如也

热门讨论