我的算法书 - 图的遍历

一句话算法

图遍历就是从一个点出发，沿着边不断访问还没访问过的点，直到能到达的点全部被标记。

问题模型

给定一张图 $G=(V,E)$ ：

点集 $V$ 表示对象；
边集 $E$ 表示对象之间的连接关系；
图可以是无向图，也可以是有向图。

图遍历要解决两个基础问题：

从某个起点出发，哪些点能到达？
整张无向图被分成了几个互不连通的部分？

这两个问题是连通性、拓扑排序、最短路、生成树、强连通分量等图论算法的前置基础。

核心直觉

把图想成很多房间和走廊。

从一个房间出发，遇到一条走廊就走过去；如果那个房间已经去过，就不再进去。这样做的关键是 visited 标记：

没访问过：可以进入，并继续扩展；
已访问过：说明这条路以前处理过，直接跳过。

DFS 和 BFS 的区别只在“下一步先处理谁”：

方法	下一步选择	数据结构	直觉
DFS	先沿一条路走到底	递归栈或手写栈	一条路走深
BFS	先处理同一层邻居	队列	一圈一圈扩散

算法步骤

DFS 遍历

将所有点标记为未访问。
从起点 start 调用 dfs(start)。
进入 dfs(u)：
- 标记 u 已访问；
- 枚举 u 的每个邻点 v；
- 如果 v 未访问，递归调用 dfs(v)。

查找无向图所有连通块

将所有点的 component[u] 设为 0。
从 1 到 n 枚举每个点 u。
如果 component[u] == 0，说明发现一个新连通块：
- 连通块编号加一；
- 从 u 开始 DFS，把能到达的点全部标记为这个编号。
枚举结束后，编号数量就是连通块数量。

算法证明

1. DFS 会访问所有从起点可达的点

核心不变量：只要一个点被访问，所有从它出发的未访问邻点都会被继续访问。

设某个点 x 从起点 s 可达，则存在路径：

s = v_0 \to v_1 \to \cdots \to v_k = x

DFS 访问 v_0 后，会枚举它的邻点，因此会访问 v_1。同理，访问 v_i 后会继续访问未访问的 v_{i+1}。

沿路径归纳可知，x 一定会被访问。

2. DFS 不会重复处理同一个点

每个点第一次进入 DFS 时会被标记。之后任何边再次指向它，都会因为 visited 为真而跳过。

所以每个点最多进入 DFS 一次。

3. 连通块标记正确

每次从一个未标记点 u 开始 DFS，DFS 标记的正是与 u 相互连通的所有点。

外层循环只会在遇到未标记点时开启新 DFS，因此每次开启都对应一个新的连通块，不会和之前的连通块重叠。

因此算法能正确得到所有连通块。

复杂度分析

设点数为 $n$ ，边数为 $m$ 。

邻接表存图时，DFS/BFS 时间复杂度为 $O(n+m)$ 。
空间复杂度为 $O(n+m)$ ，包括邻接表和访问标记。
递归 DFS 的额外栈空间最坏为 $O(n)$ 。

如果图很深，递归 DFS 可能栈溢出，可以改成手写栈。

代码实现

DFS 遍历图

cpp

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

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

struct Graph {
    int n;
    vector<vector<int>> adj;
    vector<int> visited;
    vector<int> order;

    explicit Graph(int n) : n(n), adj(n + 1), visited(n + 1, 0) {}

    void add_edge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    void dfs(int u) {
        visited[u] = 1;
        order.push_back(u);

        for (int v : adj[u]) {
            if (visited[v]) continue;
            dfs(v);
        }
    }
};

int main() {
    int n, m, start;
    cin >> n >> m >> start;

    Graph graph(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph.add_edge(u, v);
    }

    for (int u = 1; u <= n; u++) {
        sort(graph.adj[u].begin(), graph.adj[u].end());
    }

    graph.dfs(start);

    for (int i = 0; i < (int)graph.order.size(); i++) {
        if (i) cout << ' ';
        cout << graph.order[i];
    }
    cout << "\n";

    return 0;
}

无向图连通块

cpp

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

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

struct Graph {
    int n;
    vector<vector<int>> adj;
    vector<int> component;
    int component_count = 0;

    explicit Graph(int n) : n(n), adj(n + 1), component(n + 1, 0) {}

    void add_edge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    void dfs(int u, int id) {
        component[u] = id;
        for (int v : adj[u]) {
            if (component[v]) continue;
            dfs(v, id);
        }
    }

    void find_components() {
        for (int u = 1; u <= n; u++) {
            if (component[u]) continue;
            component_count++;
            dfs(u, component_count);
        }
    }
};

int main() {
    int n, m;
    cin >> n >> m;

    Graph graph(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph.add_edge(u, v);
    }

    graph.find_components();

    cout << graph.component_count << "\n";
    for (int u = 1; u <= n; u++) {
        if (u > 1) cout << ' ';
        cout << graph.component[u];
    }
    cout << "\n";

    return 0;
}

测试用例

DFS 遍历

输入：

输出：

1 2 4 3 5

解释：代码会先对邻接点排序，因此从 1 先走到 2，再走到 4，回退后走到 3 和 5。

连通块

输入：

输出：

2
1 1 1 2 2

解释：点 1,2,3 属于第一个连通块，点 4,5 属于第二个连通块。

应用分类详解

图遍历的本质是：从局部连接关系出发，把所有可达状态都展开一次。只要题目里有“点与点的连接”“状态之间能转移”“区域能扩散”，就应该先想到图遍历。

一、连通性判断

典型模式： 判断两个点是否连通，或统计图中有几个连通块。

识别信号： 出现“能否到达”“几个连通区域”“朋友圈”“岛屿数量”。

核心建模： 点表示对象，边表示可直接到达；遍历一次得到一个连通块。

应用场景	经典题目	核心思路
无向图连通块	luogu-B3862	从未访问点开始 DFS
岛屿数量	LeetCode 200	网格相邻格子建隐式图

二、可达性与路径搜索

典型模式： 从起点出发，找能到哪些状态。

识别信号： 出现“从 A 能否走到 B”“所有能到达的点”“迷宫搜索”。

核心建模： 每个位置或状态是点，合法移动是边。

应用场景	经典题目	核心思路
迷宫可达	luogu-P1605	DFS 枚举路径
有向图可达点	luogu-P3916	反图 DFS 或拓扑顺序处理

三、树和图上的结构遍历

典型模式： 需要处理父子关系、子树、进入时间、退出时间。

识别信号： 出现“子树”“祖先”“DFS 序”“树上统计”。

核心建模： DFS 的进入和退出顺序把树形结构转化成线性区间。

应用场景	经典题目	核心思路
DFS 序	本书 `tree-algo/dfs-order`	子树对应连续区间
树的直径	本书 `graph/diameter_of_tree`	两次 DFS 找最长链

四、作为高级图论算法的骨架

典型模式： 算法主体看起来复杂，但底层仍然是在边上 DFS/BFS。

识别信号： 出现“拓扑排序”“Tarjan”“二分图染色”“网络流分层图”。

核心建模： 遍历负责把图结构展开，高级算法在访问过程中维护额外信息。

应用场景	经典题目	核心思路
二分图染色	luogu-P1330	BFS/DFS 给相邻点染不同颜色
Tarjan SCC	本书 `graph/scc`	DFS 过程中维护时间戳和 lowlink
拓扑排序	本书 `graph/topsort`	按入度或 DFS 顺序展开 DAG

经典例题

1. luogu-B3862

基础图遍历题。重点是把边存入邻接表，然后从指定起点 DFS 或 BFS。

2. luogu-P3916

有向图可达性问题。直接从每个点 DFS 会超时，常见做法是在反图上按点编号从大到小遍历并传播答案。

3. luogu-P1330

二分图染色题。遍历时给相邻点染相反颜色，一旦遇到冲突说明不存在合法方案。

练习

id: graph-traversal-practice title: practice description: 图的遍历练习题：B3862、P3916、P2661。 tags: [“图论”, “DFS”, “BFS”, “练习题”]

luogu
b3862
3916
2661
1330
1341
2921
1113

参考

旧版文章：Rbook_ejs_old/book/graph/traversal/index.md
本书相关：图的存储、树的 DFS 序