E6 图与复杂度

对应大纲： 2.1.3-4 简单图、2.1.4-1 算法概念与描述、2.1.4-7/8 搜索与图论算法（概念层）

分量： 图的基本概念每年 1~2 题；复杂度分析出现在 9/19 套。

一、图的基本概念

术语	含义
顶点 / 边	记作 $n$ （或 $V$ ）个点、 $m$ （或 $E$ ）条边
无向图 / 有向图	边有没有方向
度	无向图：连到该点的边数；有向图分入度（指进来）和出度（指出去）
路径 / 回路	一串首尾相接的边；起点等于终点的路径叫回路（环）
连通	无向图中任意两点可达
强连通	有向图中任意两点互相可达
完全图	任意两点之间都有边
稀疏图 / 稠密图	边少 / 边多

★ 握手定理与边数结论（必背）

结论	公式
无向图所有顶点度数之和	$= 2m$ （边数的两倍）
有向图入度之和 = 出度之和	$= m$ （边数）
无向图中奇度顶点的个数	一定是偶数个
无向完全图的边数	$C(n,2) = \dfrac{n(n-1)}{2}$
无向连通图最少边数	$n - 1$ （一棵树）
有向强连通图最少边数	$n$ （一个有向环）
无向图保证连通所需边数	$C(n-1,2) + 1$

⚠️ 无向和有向差一倍，别搞混。 CSP 2024 第 11 题问无向图（答案「边数的两倍」），CSP 2025 第 5 题问有向图（答案「边数」）——连着两年，一年一个方向。

⚠️ 最后三行的区别要读清题：

「 $n$ 个点的无向图至少多少条边才能连通」→ $n-1$
「至少多少条边才能保证一定连通（不管怎么摆）」→ $C(n-1,2)+1$

CSP 2020 第 8 题选项最大才 12，说明问的是第一种。

📝 删边成树： $n$ 点 $m$ 边的无向连通图，要删 $m - (n-1) = \mathbf{m-n+1}$ 条边才能变成树（CSP 2021 第 6 题）。别把 $-1$ 漏掉。

二、图的存储

方式	结构	空间	查「u,v 之间有没有边」	适合
邻接矩阵	`g[u][v]`	$O(n^2)$	$O(1)$ 快	稠密图、小图
邻接表	每个点挂一个链表/vector	$O(n+m)$	$O(\deg u)$	稀疏图（竞赛常用）

📝 邻接矩阵里非零元素的个数 = 边数（无向图算两次，因为对称）。

⚠️ CSP 2022 第 9 题： $N$ 个顶点的有向连通图，邻接矩阵至少几个非零元素？→ $N$ （最省的连法是串成一个有向环）。

📝 无向图的邻接矩阵是对称矩阵，主对角线（自环）通常为 0。

三、图的遍历

算法	用什么数据结构	特点
DFS 深度优先	栈（递归本质是栈）	一条路走到黑，走不通再回头
BFS 广度优先	队列	一层一层往外扩，能求无权图最短路

📝 「DFS 用栈、BFS 用队列」是送分题（CSP 2022 第 10 题）。

★ DFS 序的枚举题

给一张小图，问「从某点出发，哪些点可能是最后一个被访问的」。

做法：按「第一步先走谁」分支，逐个展开到底。

CSP 2021 第 14 题：图为 $a\text{–}b,\ a\text{–}c,\ b\text{–}d,\ c\text{–}d,\ c\text{–}e$ ，从 $a$ 出发。全部 DFS 序只有 3 种：

a b d c e     ← 最后是 e
a c d b e     ← 最后是 e
a c e d b     ← 最后是 b

所以答案是 2 个（ $b$ 和 $e$ ）。

📝 关键洞察：能当「最后一个」的必须是「走到它时已无路可走」的点。 夹在环里的点（本题的 $c$ 、 $d$ ）后面总还有没访问的邻居，不可能收尾——想通这一点能砍掉一半分支。

⚠️ 别只试一两种走法就下结论。 这类题必须穷举分支。

四、图论算法（概念层，初赛只考认识）

算法	干什么	复杂度
拓扑排序	有向无环图（DAG）的线性排序，保证每条边 $u\to v$ 中 $u$ 排在 $v$ 前	$O(n+m)$
最小生成树	Prim、Kruskal	$O(m\log m)$
最短路	Dijkstra（非负权）、Floyd（多源、 $O(n^3)$ ）、SPFA	—
并查集	维护连通性	近似 $O(1)$

⚠️ 这些在 CSP-J 第一轮里只考「是什么、用在哪」，不要求写代码。 别在这上面花时间。

拓扑排序的验证法（考过）

CSP 2023 第 12 题：边 $(1,2)(1,3)(2,4)(3,4)$ ，哪个是合法拓扑序？

📝 做法：把每条边 $(u,v)$ 拿出来，检查序列里 $u$ 是不是排在 $v$ 前面。 四条边挨个查，比在脑子里模拟入度快。

📝 拓扑排序不唯一——本题 1,2,3,4 和 1,3,2,4 都合法。

⚠️ 有环的图没有拓扑序。

五、算法与复杂度

算法的五个特征

有穷性、确定性、可行性、输入、输出

📝 「有穷性」= 必须在有限步内结束——死循环的不是算法。

算法的三种描述方式（大纲 2.1.4-1）

自然语言、流程图、伪代码

流程图符号：

图形	含义
椭圆	开始 / 结束
平行四边形	输入 / 输出
矩形	处理（赋值、计算）
菱形	判断（分支）
箭头	流程方向

⚠️ 菱形 = 判断，平行四边形 = 输入输出——这两个最常考，别记反。

★ 时间复杂度

大 O 记号只保留最高次项、去掉常数。

复杂度	典型算法	$n=10^6$ 时能否通过
$O(1)$	直接计算	✓
$O(\log n)$	二分查找	✓
$O(\sqrt n)$	试除法判素数、枚举因数	✓
$O(n)$	单重循环、线性筛	✓
$O(n\log n)$	快排、归并、`sort`	✓
$O(n^2)$	冒泡、选择、插入排序；双重循环	✗（ $n \le 5000$ 才行）
$O(n^3)$	Floyd、三重循环	✗（ $n \le 500$ ）
$O(2^n)$	枚举子集	✗（ $n \le 20$ ）
$O(n!)$	全排列	✗（ $n \le 10$ ）

📝 数循环层数是最可靠的判定法。 三重循环里内层跑到 $i$ ，就按 $n$ 算，别管常数——CSP 2022 第 17 题问 g(n,m) 的复杂度，三层循环 $n \times m \times n$ → $O(n^2 m)$ 。

📝 必背的近似值： $2^{10} \approx 10^3$ ， $2^{20} \approx 10^6$ ， $2^{30} \approx 10^9$ 。

⚠️ 二分查找 $n$ 个元素最多比较 $\lceil \log_2(n+1) \rceil$ 次。 $100 \to 7$ （CSP 2019 第 5 题）， $1000 \to 10$ （CSP 2024 第 9 题）。这两个数直接背。

📝 打擂台找最大值需要 $n-1$ 次比较——这是理论下界，不可能更少（CSP 2021 第 4 题）。

空间复杂度

看开了多大的数组。 int a[1000000] 约 4 MB。

⚠️ 常见限制是 256 MB，所以 int 数组最多约 $6 \times 10^7$ 个元素。二维数组 int f[5007][5007] 就是 $2.5\times10^7 \times 4\text{B} = 100$ MB，已经很危险了（CSP 2024 第 18 题的程序就是这么开的）。

30 秒自测

无向图所有顶点度数之和等于什么？有向图呢？
$n$ 点 $m$ 边的无向连通图，删几条边变成树？
邻接矩阵和邻接表，各适合什么图？空间各是多少？
DFS 用什么数据结构？BFS 呢？
流程图里菱形和平行四边形分别代表什么？
三重循环 for i<n { for j<m { for k<i } } 的复杂度是多少？
1000 个有序元素二分查找，最多比较几次？
$n$ 个数打擂台找最大值，最少要比较几次？

参考答案

无向 $= 2m$ （边数两倍）；有向的入度和 = 出度和 $= m$
$m - n + 1$
矩阵适合稠密图 $O(n^2)$ ；表适合稀疏图 $O(n+m)$
栈 / 队列
菱形 = 判断；平行四边形 = 输入输出
$O(n^2 m)$
$\lceil \log_2 1001 \rceil = \mathbf{10}$ 次
$n - 1$ 次