图的基本概念 知识点讲解

概念

在信息学竞赛里，图（Graph） 就像一张错综复杂的“关系网”或“地图”。想象一下：

• 生活场景：你想知道从北京到上海有哪些直达航班（有向边）？或者两个城市之间修路需要多少成本（边权）？
• 游戏场景：在《我的世界》里，方块之间相邻就算连通；在《俄罗斯方块》里，四个方块连成一线就算消除。

这些场景本质上都在描述“点与点之间的连接关系”。如果只用数组存数字，那是“线性”的；如果存矩阵，那是“二维”的。但现实世界往往是非线性的网状结构，这时候就需要图论登场。

为了让你直观感受图的威力，我们先看一个极小的暴力例子：

假设你有 3 个任务 A、B、C，任务 A 必须在 B 之前做，B 必须在 C 之前做。

• 如果不用图，你可能要写一堆 if (A_done) { if (B_done) { ... } } 的嵌套判断，代码会像俄罗斯套娃一样深不见底。
• 如果用了图，你只需要画一条链 A -> B -> C，然后跑一遍拓扑排序，就能自动得到合法的执行顺序。

一句话：图就是“点 + 边”。后面所有图论算法（最短路、最小生成树、拓扑、网络流）都建立在这套基本概念和存储方式之上。先把“怎么存、怎么遍历”学扎实。

触发清单（看到这些信号第一时间想到本知识点）

定义

图（graph） 由两部分组成：

• 顶点（vertex）：点，常编号 1..n；
• 边（edge）：连接两个顶点的线，可带权值（长度/代价）。

按边有没有方向分：

• 无向图：边 (u, v) 双向可达，如公路；
• 有向图：边 只从 u 到 v，如单行道、微博关注。

存储方式：邻接矩阵 vs 邻接表

邻接矩阵（适合稠密图，n 小）：

用二维数组 g[u][v] 表示 u 到 v 的边权（若无边则设为无穷大 INF）。

int g[1005][1005]; // g[u][v] = 边权，无边设 INF
g[u][v] = w; // 无向图还要 g[v][u] = w

它的优点是查询两点间是否有直接边非常快（O(1)），但缺点是空间复杂度为 O(n²)，当 n 很大时（如 10⁵）会爆内存。

邻接表（适合稀疏图，n 大，推荐）：

用数组里的 vector 来存，每个点挂一条“邻边列表”。

vector<pair<int,int>> adj[1005]; // <到达点, 边权>
adj[u].push_back({v, w}); // 无向图 adj[v].push_back({u, w}) 也加

它的优点是只存真实存在的边，总空间复杂度为 O(n+m)（m 为边数），对于竞赛中常见的稀疏图（m ≈ n 量级）非常节省空间且遍历效率高。

度数与握手定理

• 无向图：顶点 v 的度数 = 与它相连的边数；所有顶点度数之和 = 2 × 边数（每条边被两个端点各算一次）。
• 有向图：入度 = 指向它的边数，出度 = 它指出去的边数。

连通性

无向图中任意两点可达 → 连通图；有向图中任意两点互相可达 → 强连通。没有环的连通图就是树（n 个点 n−1 条边）。

推演：为什么这些写法是对的（以及它们能用来干什么）

推演 1 · 为什么邻接表比邻接矩阵省空间

n 个点，邻接矩阵开 n×n 个格子，无论边多少都占 O(n²)。但竞赛图常常是稀疏的（边数 m ≈ n 量级），邻接表只存“真实存在的边”，总空间 O(n+m)。所以当边不多时用邻接表，空间和遍历都更优。稠密图（m ≈ n²）两者差不多，矩阵还方便查“两点间是否直接相连”。

用法：看到 n 很大（1e5）基本用邻接表；n ≤ 2000 且要频繁查边可用矩阵。

推演 2 · 为什么握手定理成立

每条无向边连接两个顶点，统计“所有顶点度数之和”时，这条边会被它的两个端点各计一次，所以总和恰好是边数的 2 倍。推论：无向图度数之和为偶数，且奇数度顶点个数必为偶数——判图合法性常用。

用法：握手定理能快速检查“度数数据是否自洽”，也是欧拉通路/度数类题的出发点。

推演 3 · 为什么 DFS/BFS 能不重不漏遍历全图

遍历时用 vis[] 标记“已访问”。每到一个点，沿它的邻边走到未访问的邻居；vis 保证每个点只进一次。DFS 用递归/栈往深处走（一条路走到底再回溯），BFS 用队列一层层扩散（先近后远）。两者都保证在 O(n+m) 内访问完连通块内所有点。

用法：判连通、数连通块、求最短路（BFS 用于无权图）、搜路径，全靠这套遍历。

技巧速查表（背下来）

例题

例 1：统计无向图有多少个连通块

① 题目描述

给定一个无向图，包含 $n$ 个点和 $m$ 条边。请计算该图中共有多少个连通块。

② 审题分析

• 读题抓条件：无向图，求连通块数量。
• 定需求：需要访问所有点，且不能重复访问，每找到一个从未访问过的点，就代表发现了一个新的连通块。
• 为什么能用本知识点：连通性的本质就是“可达性”。DFS 或 BFS 可以遍历一个连通块内的所有点。只要我们在循环中检查 vis[i]，一旦发现未访问的点，就启动一次 DFS，计数器加一，完美契合。
• 如果不用会怎样：如果用邻接矩阵暴力枚举所有点对判断是否连通，复杂度是 $O(n^2 \cdot m)$，在 $n=1000$ 时绝对超时；如果不用 DFS/BFS 而用其他遍历方式（如随机游走），无法保证 $O(n+m)$ 的时间复杂度。

③ 解题思路

1. 使用邻接表存储图（因为通常图是稀疏的）。

2. 初始化 vis 数组全为 false。

3. 从 1 到 $n$ 遍历每个点：

- 如果 vis[i] 为 false，说明这是一个新连通块的起点。

- 调用 dfs(i) 将该连通块内所有点标记为 true。

- 计数器 blocks 加 1。

4. 输出 blocks。

④ C++ 完整参考代码

#include <iostream>
#include <vector>
using namespace std;

// 全局变量：邻接表和访问标记数组
// 使用 vector<int> 存无向图的邻居，bool vis 标记是否访问过
vector<int> adj[1005];
bool vis[1005];

// DFS 函数：从点 u 开始，递归访问所有能到达的点
void dfs(int u) {
 vis[u] = true; // 标记 u 已访问，防止重复进入
 for (int v : adj[u]) { // 遍历 u 的所有邻居
 if (!vis[v]) { // 如果邻居 v 还没被访问过
 dfs(v); // 递归进入 v，继续深搜
 }
 }
}

int main() {
 // 优化输入输出效率
 ios::sync_with_stdio(false);
 cin.tie(nullptr);

 int n, m;
 if (!(cin >> n >> m)) return 0; // 读取点数 n 和边数 m

 // 读入 m 条边
 for (int i = 0; i < m; i++) {
 int u, v;
 cin >> u >> v;
 // 无向图：边 (u, v) 意味着 u 能去 v，v 也能去 u
 // 必须两边都加，否则只能单向走，连通块会算错
 adj[u].push_back(v);
 adj[v].push_back(u);
 }

 int blocks = 0;
 // 遍历所有点，寻找未访问的点作为新连通块的入口
 for (int i = 1; i <= n; i++) {
 if (!vis[i]) {
 dfs(i); // 启动 DFS 标记整个连通块
 blocks++; // 发现了一个新连通块
 }
 }

 cout << blocks << '\n';
 return 0;
}

⑤ 代码解读（含真实运行输出）

假设输入如下：

6 5
1 2
2 3
4 5
5 6
3 4

这是一个由两个连通块组成的图：1-2-3-4-5-6 实际上是一条链，但题目给的边是 1-2, 2-3, 4-5, 5-6, 3-4，连起来是 1-2-3-4-5-6 一个连通块。等等，我重新构造一个有两个连通块的例子以便演示：

6 4
1 2
2 3
4 5
5 6

这里 1-2-3 是一个块，4-5-6 是另一个块。

运行结果：

2

解读：

• 程序从 i=1 开始，vis[1] 为假，调用 dfs(1)。
• dfs(1) 标记 1，然后访问 2，再访问 3。此时 vis[1,2,3] 均为真。
• 循环回到 i=2,3，因为已访问，跳过。
• 当 i=4 时，vis[4] 为假，调用 dfs(4)。
• dfs(4) 标记 4，访问 5，再访问 6。此时 vis[4,5,6] 均为真。
• 循环结束，blocks 累加了 2 次，输出 2。正确。

例题复盘总结

归纳题：

• P3916 图的遍历（反向建边统计可达点）：考察无向图建边时方向的重要性，以及 DFS 遍历顺序对结果的影响。
• P1363 幻象迷宫（DFS 判环/无限走）：考察 DFS 在判环和检测“能否无限走”中的应用，需要结合 vis 和递归栈的状态。
• P4017 最大食物链计数（DAG 拓扑 + 计数）：考察有向无环图（DAG）上结合拓扑排序和动态规划求路径数，是图论与 DP 的经典结合。
• P1983 车站分级（依约束建有向边 + 拓扑）：考察如何将现实约束转化为有向边，并利用拓扑排序解决依赖问题。

共性特征：

• 所有题目都涉及“点与边的关系”，核心操作都是建图和遍历。
• 无向图题目必须注意双向加边，有向图题目必须注意边的方向（依赖关系）。
• 涉及连通性、可达性、最长链、依赖顺序的题目，几乎都可以用 DFS/BFS 或拓扑排序解决。

各自技巧：

• P3916：反向建边意味着原图中的“可达”变成了新图中的“不可达”，需要仔细审题转换视角。
• P1363：DFS 递归深度可能很大，需考虑栈溢出风险（虽然本题数据范围通常允许），且判环逻辑比单纯计数复杂。
• P4017：拓扑排序后，可以用 DP 累加路径数，注意初始化 dp[起点]=1。
• P1983：建图时，若 A 必须在 B 前面，则边是 A -> B，拓扑序即为合法顺序。

审题模板（固定思考流程）：

1. 点是谁、边是谁、有向还是无向？ → 决定建图方式（邻接表/矩阵，加边方向）。

2. 要遍历/判连通？ → 选 DFS 或 BFS。

3. 有依赖顺序？ → 拓扑排序。

4. 求最短步数（无权）？ → BFS。

5. 求最长链（DAG）？ → 拓扑 + DP。

错误清单（特有）：

• 无向图只加一条边：导致只能单向走，连通块数量偏多（如例 1 中若漏加反向边，1-2-3 和 4-5-6 会变成两个独立块，但实际是连通的）。
• 矩阵大小开错：点编号 1..n，数组要开到 n+1；g[u][v] 下标超界会 RE。
• 遍历忘打 vis：同一点反复进，死循环或 TLE；每个点只应进一次。
• 把有向当无向：有向边只加 adj[u].push_back(v)，反向不可达，别顺手加两次。
• 度数统计漏边：无向图一条边贡献两个端点的度数，别只算一端。
• 拓扑前没算入度 / 入队条件错：拓扑排序要先把所有入度为 0 的点入队，每次删边后更新入度。
• 混淆 DFS 与 BFS 用途：求无权最短步数用 BFS（队列），DFS 只保证访问不保证“最近”。

写法总表

分工说明：

• 触发清单 告诉你“看到什么信号该想到本知识点”（宏观选题）。
• 技巧速查表 告诉你“具体怎么做”（微观实现）。
• 写法总表 将技法按粒度从细到粗分层，帮助你建立知识体系。

常见错误

1. 无向图只加一条边：无向边要 adj[u].push_back(v) 和 adj[v].push_back(u) 都加，否则只能单向走。

2. 矩阵大小开错：点编号 1..n，数组要开到 n+1；g[u][v] 下标超界会 RE。

3. 遍历忘打 vis：同一点反复进，死循环或 TLE；每个点只应进一次。

4. 把有向当无向：有向边只加 adj[u].push_back(v)，反向不可达，别顺手加两次。

5. 度数统计漏边：无向图一条边贡献两个端点的度数，别只算一端。

6. 拓扑前没算入度 / 入队条件错：拓扑排序要先把所有入度为 0 的点入队，每次删边后更新入度。

7. 混淆 DFS 与 BFS 用途：求无权最短步数用 BFS（队列），DFS 只保证访问不保证“最近”。

自测

1. 邻接矩阵和邻接表分别在什么情况下更合适？空间复杂度各是多少？

2. 无向图握手定理是什么？它能推出什么关于“奇数度顶点个数”的结论？

3. 无向图建图时为什么一条边要加两次？有向图呢？

4. DFS 和 BFS 各用什么结构实现？分别适合解决什么问题？

5. 遍历图时 vis 数组的作用是什么？不写会怎样？

6. 有向图的入度和出度分别怎么定义？拓扑排序为什么要看入度？

7. 给一个 n 点 m 边的稀疏图（m≈n），你会选哪种存储？为什么？

举一反三 · 审题流水线

第一步：定模型。看到“关系/连接/网络/通路”，立刻在脑海里画点连线。确认是无向还是单向（“依赖”、“必须在前”就是有向）。

第二步：选存储。点数 $n$ 是多少？边数 $m$ 是多少？若 $n$ 很大（如 $10^5$）或 $m \ll n^2$，直接上邻接表；若 $n$ 很小（如 $200$）且要频繁查两点是否相连，考虑邻接矩阵。

第三步：定操作。

• 要数连通块？DFS/BFS 跑一遍，vis 数组清零，每发现一个未访问点就 dfs 一次，计数加一。
• 要判可达？同上，从起点 dfs，看终点 vis 是否为真。
• 要最短路（无权）？BFS，第一次访问到某点即为最短。
• 有依赖？建边，算入度，拓扑排序，若排不完说明有环。

第四步：防坑。无向边两边加！矩阵下标开 n+1！拓扑前初始化入度为 0 的点入队！

练手题

题 A：无向图的连通块计数

给定 $n$ 个点和 $m$ 条边，求连通块数量。

输入：第一行 $n, m$；接下来 $m$ 行每行 $u, v$。

输出：一个整数。

题 B：有向图的拓扑排序

给定 $n$ 个点和 $m$ 条有向边，表示任务依赖关系。若存在合法的执行顺序，输出按拓扑序排列的点编号（任意一种合法顺序均可）；否则输出 -1。

输入：第一行 $n, m$；接下来 $m$ 行每行 $u, v$。

输出：一行 $n$ 个整数或 -1。