02 DFS 与连通块

userId_undefined
吴老师
7月全勤卷王8月全勤卷王10月全勤卷王倔强青铜时间刺客空间掌握者

2026-06-30 18:48:52

发布于：广东

4阅读
0回复
0点赞

02 DFS 与连通块

一、本阶段目标

学完本阶段，学生要能做到：

1. 理解 DFS 是“沿着一条路走到底，再回退”。
2. 会用 DFS 遍历图。
3. 会统计连通块数量。
4. 会处理网格图 DFS。
5. 会解释 vis 数组的意义。
6. 会处理简单染色问题，为二分图做铺垫。

二、DFS 的核心思想

DFS，全称 Depth First Search，深度优先搜索。

通俗理解：

从一个点出发，先尽量往深处走。
走不动了，就回到上一个点，换另一条路继续走。

它很像走迷宫：

选一条路一直走
遇到死胡同就退回来
再换路

三、DFS 模板：图的遍历

void dfs(int u) {
    vis[u] = true;

    for (int v : g[u]) {
        if (!vis[v]) {
            dfs(v);
        }
    }
}

其中：

u：当前所在点
vis[u]：点 u 是否已经访问过
g[u]：从 u 能走到的所有点

vis 数组非常重要。没有 vis，图中有环时会无限递归。

例如：

1 -- 2

如果没有 vis：

dfs(1) 调 dfs(2)
dfs(2) 又调 dfs(1)
dfs(1) 又调 dfs(2)
...

四、完整模板

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

const int N = 100005;
vector<int> g[N];
bool vis[N];

void dfs(int u) {
    vis[u] = true;
    cout << u << ' ';

    for (int v : g[u]) {
        if (!vis[v]) {
            dfs(v);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs(1);
    return 0;
}

五、连通块

在无向图中，如果一组点互相可以到达，就属于同一个连通块。

统计连通块数量的方法：

枚举每个点
如果这个点没被访问过，说明发现一个新的连通块
从它开始 DFS，把整个连通块都标记掉

代码：

int cnt = 0;
for (int i = 1; i <= n; i++) {
    if (!vis[i]) {
        cnt++;
        dfs(i);
    }
}

六、连通块大小

有时不仅要知道有几个连通块，还要知道每个连通块有多大。

int dfs(int u) {
    vis[u] = true;
    int sz = 1;

    for (int v : g[u]) {
        if (!vis[v]) {
            sz += dfs(v);
        }
    }

    return sz;
}

使用：

for (int i = 1; i <= n; i++) {
    if (!vis[i]) {
        int size = dfs(i);
        cout << size << '\n';
    }
}

七、网格图 DFS

迷宫、地图、岛屿都可以看成图。

每个格子是一个点
上下左右相邻的可走格子之间有边

方向数组：

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

边界判断：

bool inside(int x, int y) {
    return x >= 1 && x <= n && y >= 1 && y <= m;
}

网格 DFS：

void dfs(int x, int y) {
    vis[x][y] = true;

    for (int k = 0; k < 4; k++) {
        int nx = x + dx[k];
        int ny = y + dy[k];

        if (!inside(nx, ny)) continue;
        if (a[nx][ny] == '#') continue;
        if (vis[nx][ny]) continue;

        dfs(nx, ny);
    }
}

八、岛屿数量模型

题目常见描述：

给一个 01 矩阵，1 表示陆地，0 表示水。
上下左右相邻的陆地属于同一个岛屿。
问一共有多少个岛屿。

建模：

点：值为 1 的格子
边：相邻两个 1 之间连边
答案：连通块数量

代码框架：

int ans = 0;
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        if (a[i][j] == '1' && !vis[i][j]) {
            ans++;
            dfs(i, j);
        }
    }
}

九、填涂颜色模型

类似 P1162 填涂颜色。

关键思想：

不要直接找“里面的 0”。
先从边界上的 0 出发，标记所有能到达边界的外部区域。
最后没有被标记的 0，就是内部区域。

这是一个很重要的反向思维。

步骤：

1. 从边界所有 0 开始 DFS/BFS。
2. 标记这些 0 为外部。
3. 扫描整个矩阵：
   - 原来是 0 且没有被标记：改成 2
   - 其他保持不变

这种思想在自招题里很常见：

正面不好判断，就从反面出发。

十、染色思想

有些题要判断能不能把点分成两组，使得每条边两端颜色不同。

这就是二分图染色的基础。

bool dfs(int u, int c) {
    color[u] = c;

    for (int v : g[u]) {
        if (!color[v]) {
            if (!dfs(v, 3 - c)) return false;
        } else if (color[v] == color[u]) {
            return false;
        }
    }

    return true;
}

其中颜色用 1 和 2 表示，3 - c 可以在 1 和 2 之间切换。

十一、DFS 常见错误

错误 后果 修正
忘记 vis 死循环或爆栈 进入点后立刻标记
递归层数太深 栈溢出 大图可改 BFS 或手写栈
网格越界 RE 先判断 inside
把 x/y 写反 答案错 统一行列含义
有向图当无向图建 可达性错误 看清题目方向
多组数据不清空 上一组数据污染 清空 g、vis

十二、课堂例题

例题 1：判断两点是否连通

给无向图，问从 s 能不能到 t。

做法：

从 s 开始 DFS。
如果 vis[t] 为 true，则能到达。

例题 2：统计连通块

给无向图，问有几个互不相连的区域。

做法：

枚举所有点，遇到未访问点就 DFS，答案 +1。

例题 3：迷宫方案数

给迷宫，问从起点到终点有多少条路径。

注意：这是“方案数”，不是“最短路”。

通常使用 DFS 回溯。

void dfs(int x, int y) {
    if (x == tx && y == ty) {
        ans++;
        return;
    }

    vis[x][y] = true;

    for (int k = 0; k < 4; k++) {
        int nx = x + dx[k];
        int ny = y + dy[k];
        if (!inside(nx, ny)) continue;
        if (block[nx][ny]) continue;
        if (vis[nx][ny]) continue;
        dfs(nx, ny);
    }

    vis[x][y] = false; // 回溯
}

这里要特别强调：

遍历连通块：vis 不撤销
枚举所有路径：vis 要撤销

十三、练习题

题号 题名 训练点 建议
P1605 迷宫 DFS 回溯、路径数量 必做
P1162 填涂颜色 从边界反向搜索 必做
P1451 求细胞数量 连通块数量 必做
P1596 Lake Counting S 八方向连通块 选做
P1330 封锁阳光大学 染色、二分图雏形 提高
P6566 观星 连通块大小 提高

链接：

https://www.luogu.com.cn/problem/P1605
https://www.luogu.com.cn/problem/P1162
https://www.luogu.com.cn/problem/P1451
https://www.luogu.com.cn/problem/P1596
https://www.luogu.com.cn/problem/P1330
https://www.luogu.com.cn/problem/P6566

十四、本阶段作业

  1. 手写图 DFS 模板。
  2. 手写网格 DFS 模板。
  3. 解释“连通块为什么可以用一次 DFS 全部找出来”。
  4. 完成 P1605、P1162。
  5. 选做 P1330，并写出染色失败的条件。

十五、本阶段小结

DFS 适合解决：

可达性
连通块
路径枚举
树的遍历
染色

但 DFS 不适合直接求无权图最短路。只要题目出现“最少步数”，优先考虑 BFS。

userId_undefined
去预览
0/2000
暂无数据

这里空空如也

热门讨论