CSP-J/S 初赛图论完全讲义

前言

图论是CSP-J/S初赛中数据结构部分的核心内容之一，也是每年必考的知识板块。从近年的命题趋势来看，图论相关题目在初赛中的分值占比逐年上升，CSP-S提高组中图论相关考点占比可达30%左右。无论是入门组的选手还是提高组的选手，都必须熟练掌握图论的基本概念、存储方式、遍历算法以及常见应用。

本讲义系统梳理了CSP-J/S初赛中图论的全部考点，从最基础的概念出发，逐步深入到各类算法，并结合初赛真题进行讲解，力求帮助考生全面、系统地掌握图论知识。

第一章 图的基本概念

1.1 图的定义

图（Graph）是由顶点（Vertex，也称节点Node）和边（Edge）组成的集合，通常表示为 G = (V, E)，其中 V 是顶点的集合，E 是边的集合。顶点代表对象，边代表对象之间的特定关系。

图论起源于18世纪欧拉对柯尼斯堡七桥问题的研究，1736年欧拉首次提出图论的概念。如今，图论已广泛应用于社交网络分析、电路设计、计算机网络、路径规划等众多领域。

1.2 图的分类

（1）无向图（Undirected Graph）

每条边都是无方向的，边仅表示两个顶点之间存在某种关系，没有方向性。无向图中的边可以表示为 e = (u, v) 或 e = u - v。

（2）有向图（Directed Graph）

每条边都是有方向的，边表示从一个顶点指向另一个顶点。有向图中的边可以表示为 e = u → v。

（3）完全图（Complete Graph）

任意两个顶点之间都有边相连的图。对于有 n 个顶点的完全图：

• 无向完全图的边数为：C(n,2) = n(n-1)/2

• 有向完全图的边数为：n(n-1)（因为每对顶点之间有两个方向的边）

（4）子图（Subgraph）

从原图中取出部分顶点和部分边组成的图。

（5）带权图（Weighted Graph）

边上带有权值的图，权值可以是距离、时间、费用等具有某种含义的数值。

（6）稀疏图与稠密图

边数远小于顶点数平方的图为稀疏图，边数接近顶点数平方的图为稠密图。

（7）简单图（Simple Graph）

没有自环和重边的图。

1.3 顶点的度（Degree）

（1）无向图中的度

与顶点相关联的边的数目。无向图中所有顶点的度数之和等于边数的两倍——这就是著名的握手原理（Handshaking Lemma）。

（2）有向图中的度

有向图中顶点分为出度（Out-degree）和入度（In-degree）：

• 出度：以该顶点为起点的有向边的数量

• 入度：以该顶点为终点的有向边的数量

• 顶点的度 = 出度 + 入度

在有向图中，所有顶点的入度之和等于所有顶点的出度之和，都等于边数。

重要公式：对于任意图（无向图或有向图），设顶点数为 n，边数为 e，则该图所有顶点的度之和 = 2e。

1.4 路径与回路

（1）路径（Path）

从顶点 A 到顶点 B 所经过的所有边的序列。

（2）简单路径（Simple Path）

在一条路径中，除起点和终点外，其余顶点各不相同。

（3）回路/环（Cycle）

起点和终点相同的路径。若回路中除起点外没有重复顶点，则称为简单回路。特别的，起点和终点相同的边称为自环（Self-loop），即 e = (u, u)。

1.5 连通性

（1）连通（Connected）

在无向图中，若两个顶点之间存在路径，则称这两个顶点是连通的。

（2）连通图（Connected Graph）

在无向图中，若任意两个顶点之间都存在路径（直接或间接），则称该图为连通图。

注意：完全图一定是连通图，但连通图不一定是完全图。

（3）连通分量（Connected Component）

无向图中的极大连通子图。任何连通图的连通分量只有一个（即其自身），非连通图则包含多个相互独立的连通分量。

（4）强连通（Strongly Connected）

在有向图中，若两个顶点相互都有路径可以到达，则称这两个顶点是强连通的。

（5）强连通图（Strongly Connected Graph）

在有向图中，若任意两个顶点之间都存在路径（双向可达），则称该图为强连通图。

（6）强连通分量（Strongly Connected Component, SCC）

有向图中的极大强连通子图。

第二章 树的特殊地位

2.1 树的定义与性质

树是一种特殊的图：连通且无环的无向图。树具有以下重要性质：

1. 任意两个顶点之间有且仅有一条简单路径

2. 边数 = 顶点数 - 1（E = V - 1）

3. 树是连通图，但连通图不一定是树（连通图可能含环）

4. 树形似倒置的树（根在上，叶子在下）

2.2 树的基本术语

• 根结点：树的最顶层节点，每棵树有且仅有一个

• 深度（Depth） ：节点到根结点的路径上的边数

• 高度（Height） ：所有节点深度的最大值

• 叶结点（Leaf） ：没有子结点的结点

• 父结点（Parent） ：除根结点外，每个结点到根路径上的第二个结点

• 子结点（Child） ：如果 u 是 v 的父亲，那么 v 是 u 的子结点

• 兄弟（Sibling） ：同一父亲的多个子结点互为兄弟

• 祖先（Ancestor） ：结点到根路径上除自身外的所有结点

• 子树（Subtree） ：删除与父结点相连的边后，该结点所在的子图

2.3 特殊的二叉树

（1）满二叉树/完美二叉树

所有叶结点深度相同的二叉树。深度为 h 的满二叉树：

• 节点总数为：2^h - 1

• 第 k 层有 2^(k-1) 个节点

• 叶子节点数 n0 与度为2的节点数 n2 满足：n0 = n2 + 1

（2）完全二叉树（Complete Binary Tree）

只有最下面两层结点的度数可小于2，且最下面一层的结点都集中在该层最左边。

对于完全二叉树，若用数组按层序编号（从1开始）：

• 结点 i 的左儿子编号为：2i

• 结点 i 的右儿子编号为：2i + 1

• 结点 i 的父结点编号为：⌊i/2⌋

2.4 二叉树的遍历

• 前序遍历（先序遍历） ：根 → 左子树 → 右子树

• 中序遍历：左子树 → 根 → 右子树

• 后序遍历：左子树 → 右子树 → 根

重要结论：前序遍历 + 中序遍历 可以唯一确定一棵二叉树；后序遍历 + 中序遍历 也可以唯一确定一棵二叉树。

初赛提示：树的相关知识在CSP初赛中几乎每年必考，尤其是二叉树的遍历、性质计算和完全二叉树的编号规律，是选择题的高频考点。

第三章 图的存储结构

3.1 邻接矩阵（Adjacency Matrix）

邻接矩阵是用一个 n × n 的二维数组来表示具有 n 个顶点的图。数组的行和列都代表顶点，数组元素的值表示顶点之间是否存在边（或边的权值）。

（1）无向图的邻接矩阵

无向图的邻接矩阵具有以下特点：

• 对称性：矩阵是对称的（A[i][j] = A[j][i]）

• 顶点 i 的度：第 i 行（或第 i 列）中 1 的个数

• 完全图的邻接矩阵中，对角元素为 0，其余全为 1

（2）有向图的邻接矩阵

有向图的邻接矩阵具有以下特点：

• 不对称性：矩阵可能是不对称的

• 顶点 i 的出度：第 i 行元素之和

• 顶点 i 的入度：第 i 列元素之和

• 图的度 = 矩阵中 1 的个数（即所有非零元素个数）

（3）带权图的邻接矩阵

对于带权图，邻接矩阵中存储的是边的权值，若无边则通常用 ∞（无穷大）或 -1 表示。

邻接矩阵的优缺点：

• 优点：容易实现图的操作，如求某顶点的度、判断顶点之间是否有边、找顶点的邻接点等

• 缺点：n 个顶点需要 n² 个存储单元，对稀疏图而言浪费空间

• 空间复杂度：O(n²)

• 适用场景：边稠密的图

3.2 邻接表（Adjacency List）

邻接表是用链表数组来表示图：数组长度为顶点数，每个元素都是一个链表，链表中存储与该顶点相邻的所有顶点。

（1）无向图的邻接表

每条边在邻接表中会被存储两次（两个方向各一次）。

（2）有向图的邻接表

每条边只存储一次（按方向存储）。

（3）带权图的邻接表

链表中除了存储邻接顶点外，还同时存储边的权值。

邻接表的优缺点：

• 优点：节省存储空间，尤其适合稀疏图

• 缺点：判断两点之间是否有边不如邻接矩阵方便

• 空间复杂度：O(n + m)，其中 n 为顶点数，m 为边数

• 适用场景：边稀疏的图

初赛提示：邻接矩阵和邻接表的对比是初赛选择题的常见考点。考生需要掌握两种存储方式的空间复杂度、适用场景以及各自的特点。

第四章 图的遍历算法

图的遍历是指从某个顶点出发，按照某种规则访问图中所有顶点且仅访问一次的算法。两种最基本的遍历算法是深度优先搜索（DFS）和广度优先搜索（BFS）。

4.1 深度优先搜索（DFS）

基本思想：从某个顶点出发，尽可能深入地访问相邻顶点，直到无法继续，然后回溯到上一个顶点，继续访问其他未访问的相邻顶点。

实现方式：递归或使用栈。

算法步骤：

1. 从起始顶点开始，标记该顶点为已访问

2. 选择一个未访问的邻接顶点，递归地进行DFS

3. 若当前顶点的所有邻接顶点都已访问，则回溯

4. 重复上述过程直到所有顶点都被访问

应用场景：

• 连通性判断

• 寻找连通分量

• 检测环

• 拓扑排序（后序逆序）

4.2 广度优先搜索（BFS）

基本思想：从起始顶点开始，逐层向外扩展，先访问离起始顶点近的顶点。

实现方式：使用队列。

算法步骤：

1. 将起始顶点入队并标记为已访问

2. 从队列中取出一个顶点，访问其所有未访问的邻接顶点，将它们入队并标记

3. 重复步骤2直到队列为空

应用场景：

• 求无权图的最短路径

• 层序遍历

• 判断二分图

4.3 DFS与BFS的对比

特性	DFS	BFS
数据结构	栈（递归）	队列
访问顺序	深度优先	广度优先
空间复杂度	O(深度)	O(宽度)
最短路径	不保证	保证（无权图）
实现难度	递归较简单	需要手写队列

初赛提示：DFS和BFS的遍历顺序、适用场景以及各自使用的数据结构（栈/队列）是初赛选择题的常见考点。

第五章 最短路径算法

最短路径问题是图论中最经典的问题之一，也是CSP初赛的重要考点。

5.1 Dijkstra算法——单源最短路径

问题描述：给定一个带权图和一个源点，求源点到图中所有其他顶点的最短路径。

适用条件：图中不存在负权边。

基本思想：贪心算法。将顶点分为已确定最短路径的集合和未确定的集合，每次从未确定的顶点中选择距离源点最近的顶点加入已确定集合，并用该顶点更新其他顶点的距离。

算法步骤：

1. 初始化：dist[源点] = 0，其余顶点的 dist = ∞

2. 从未处理顶点中选择 dist 最小的顶点 u

3. 标记 u 为已处理

4. 对于 u 的每个邻接顶点 v，若 dist[u] + w(u,v) < dist[v]，则更新 dist[v]

5. 重复步骤2-4，直到所有顶点都被处理

时间复杂度：

• 朴素实现：O(n²)

• 堆优化：O((n + m) log n)

5.2 Floyd算法——多源最短路径

问题描述：求图中任意两个顶点之间的最短路径。

基本思想：动态规划。逐步允许中间顶点加入路径，更新任意两点之间的最短距离。

核心代码（三重循环）：

text

for k in 1..n:
    for i in 1..n:
        for j in 1..n:
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

时间复杂度：O(n³)

适用场景：顶点数较少（通常 n ≤ 200）的图，或需要所有点对之间最短路径的情况。

5.3 算法对比

特性	Dijkstra	Floyd
问题类型	单源最短路径	多源最短路径
适用图	无负权边	可有负权边（无负环）
时间复杂度	O((n+m)log n)	O(n³)
空间复杂度	O(n+m)	O(n²)
思想	贪心	动态规划

初赛提示：Dijkstra和Floyd算法的适用条件、时间复杂度和基本思想是初赛选择题的高频考点。考生需要能够判断在什么情况下应该使用哪种算法。

第六章 最小生成树

最小生成树（Minimum Spanning Tree, MST）是带权无向连通图中的一个重要概念。CSP-S 2025年的题目就考查了最小生成树算法的应用。

6.1 基本概念

生成树：一个连通图的生成树是一个包含图中所有顶点的极小连通子图，它有 n-1 条边且无环。

最小生成树：在带权连通图中，所有生成树中边权之和最小的那棵生成树。

6.2 Prim算法

基本思想：从一个结点开始，不断往生成树中加入顶点。每次选择距离当前生成树最近的顶点加入。

算法步骤：

1. 任选一个顶点作为起点，加入生成树

2. 在所有连接树内顶点和树外顶点的边中，选择权值最小的边

3. 将该边及其连接的树外顶点加入生成树

4. 重复步骤2-3，直到所有顶点都在生成树中

时间复杂度：

• 朴素实现：O(n²)

• 堆优化：O((n + m) log n)

6.3 Kruskal算法

基本思想：按边权从小到大依次考虑每条边，若加入该边不会形成环，则将其加入生成树。

算法步骤：

1. 将所有边按权值从小到大排序

2. 依次取出每条边，检查其两个端点是否已在同一连通分量中（使用并查集）

3. 若不在同一分量，则加入该边，合并两个分量

4. 重复步骤2-3，直到加入了 n-1 条边

时间复杂度：O(m log m)

6.4 算法对比

特性	Prim	Kruskal
基本策略	加点	加边
适用图	稠密图	稀疏图
时间复杂度	O(n²) 或 O((n+m)log n)	O(m log m)
辅助结构	优先队列	并查集

初赛提示：Prim和Kruskal算法的基本思路、时间复杂度和适用场景是初赛的常考内容。考生需要理解两种算法的核心区别：Prim是"加点"，Kruskal是"加边"。

第七章 拓扑排序

7.1 基本概念

有向无环图（DAG, Directed Acyclic Graph） ：不存在有向环的有向图。

拓扑排序：对有向无环图的所有顶点进行线性排序，使得对于图中的每条有向边 u → v，顶点 u 在排序中都出现在顶点 v 之前。

7.2 拓扑排序算法

基本思想：反复选择入度为0的顶点输出，并将其所有出边删除。

算法步骤：

1. 计算所有顶点的入度

2. 将所有入度为0的顶点入队

3. 从队列中取出一个顶点并输出

4. 将该顶点的所有邻接顶点的入度减1，若有顶点入度变为0则入队

5. 重复步骤3-4，直到队列为空

判断有环：若输出的顶点数小于图中顶点总数，则说明图中存在环。

7.3 初赛常见考点

1. 给定DAG，写出所有可能的拓扑排序序列

2. 判断给定序列是否是合法的拓扑排序

3. 判断图中是否有环（拓扑排序是否能完成）

4. 拓扑排序结果是否唯一

初赛提示：拓扑排序是CSP初赛的高频考点，2023年的初赛就考查了拓扑排序的相关知识。考生需要熟练掌握拓扑排序的算法流程，并能判断一个序列是否为合法的拓扑序。

第八章 欧拉路径与欧拉回路

8.1 基本概念

欧拉路径：经过图中每条边恰好一次的路径。

欧拉回路：经过图中每条边恰好一次且回到起点的回路。

8.2 判定条件

无向图：

• 存在欧拉回路：所有顶点的度数均为偶数，且图连通

• 存在欧拉路径：恰好有0个或2个顶点的度数为奇数，且图连通

有向图：

• 存在欧拉回路：所有顶点的入度等于出度，且所有非零度顶点强连通

• 存在欧拉路径：恰好一个顶点出度比入度大1，恰好一个顶点入度比出度大1，其余顶点入度等于出度，且所有非零度顶点连通

第九章 二分图

9.1 基本概念

二分图（Bipartite Graph），又称二部图，是指能将顶点划分为两个不相交的集合 A 和 B，使得图中的每条边都连接 A 中的一个顶点和 B 中的一个顶点，即同一集合内的顶点之间没有边相连。

等价表述：可以用2种颜色完成顶点染色，使得相邻顶点颜色不同。

9.2 二分图的判定

判断一个图是否为二分图，常用的方法有：

1. DFS/BFS染色法：从任一顶点开始染色，相邻顶点染不同颜色，若发现矛盾则不是二分图

2. 并查集法：通过拆点或关系型并查集维护

重要性质：二分图等价于没有奇环的图。

9.3 初赛常见考点

• 判断一个图是否为二分图

• 二分图的最大边数问题

• 完全二分图（K_{a,b}）的边数 = a × b

第十章 初赛常见题型与解题技巧

10.1 概念辨析题

这类题目考查对基本概念的理解和区分。常见考点包括：

• 完全图与连通图的区别与联系

• 连通图与强连通图的区别（无向图 vs 有向图）

• 树与一般图的区别（无环连通）

• 邻接矩阵与邻接表的优缺点对比

10.2 性质计算题

这类题目要求根据图的定义计算相关数值。常见考点包括：

• 完全图的边数计算

• 度数与边数的关系（握手原理）

• 树的边数 = 顶点数 - 1

• 二叉树的性质（n0 = n2 + 1）

10.3 遍历与算法题

这类题目考查对图遍历和经典算法的理解。常见考点包括：

• DFS和BFS的遍历顺序

• Dijkstra算法的执行过程

• 拓扑排序的合法序列判断

• Prim和Kruskal算法的执行过程

10.4 真题示例

例1（2022年CSP-J初赛）：关于邻接矩阵存储图，以下说法正确的是？

解析：邻接矩阵的空间复杂度为 O(n²)，与边数无关，适合稠密图。无向图的邻接矩阵是对称的。

例2（2023年CSP-J初赛）：拓扑排序相关判断。

解析：拓扑排序只能对DAG进行。拓扑排序的结果可能不唯一。若拓扑排序无法完成（输出的顶点数小于总顶点数），则图中存在环。

例3（二分图相关）：24个顶点的二分图至多有多少条边？

解析：二分图的两部分顶点数分别为 a 和 b（a + b = 24），最大边数为 a × b。当 a = b = 12 时取得最大值 144。

第十一章 备考建议

11.1 知识体系梳理

图论的知识体系可以按照以下层次进行梳理：

第一层（CSP-J必备） ：

• 图的基本概念（顶点、边、有向/无向、完全图、连通图）

• 树的定义与性质、二叉树的遍历

• 邻接矩阵与邻接表的存储

• DFS与BFS的基本思想

第二层（CSP-S必备） ：

• 最短路径（Dijkstra、Floyd）

• 最小生成树（Prim、Kruskal）

• 拓扑排序

• 二分图判定

第三层（拓展提高） ：

• 强连通分量

• 欧拉路径与欧拉回路

• 网络流初步

11.2 复习策略

1. 概念先行：先确保所有基本概念烂熟于心，这是解题的基础

2. 算法理解：不仅要记住算法的步骤，更要理解算法的思想和适用条件

3. 真题演练：通过历年真题检验自己的掌握程度，发现薄弱环节

4. 错题整理：将做错的题目分类整理，分析错误原因

11.3 考场技巧

1. 仔细审题：注意题目说的是"有向图"还是"无向图"，"连通图"还是"完全图"

2. 画图辅助：对于抽象的描述，可以在草稿纸上画出图形帮助理解

3. 特殊值检验：对于选择题，可以用特殊值（如 n=1, 2, 3）进行检验

4. 排除法：对于不确定的选项，先排除明显错误的选项

附录：重要公式汇总

公式	说明
E = n(n-1)/2	n个顶点的无向完全图的边数
E = n(n-1)	n个顶点的有向完全图的边数
所有顶点度数之和 = 2E	握手原理（适用于任何图）
E = V - 1	树的边数与顶点数的关系
节点总数 = 2^h - 1	深度为h的满二叉树的节点数
n0 = n2 + 1	二叉树中叶子节点与度为2的节点的关系
左儿子 = 2i，右儿子 = 2i+1	完全二叉树的数组编号规律
O(n²)	邻接矩阵的空间复杂度
O(n+m)	邻接表的空间复杂度
O((n+m)log n)	堆优化Dijkstra的时间复杂度
O(n³)	Floyd算法的时间复杂度
O(m log m)	Kruskal算法的时间复杂度

图论是信息学竞赛的核心内容之一，也是CSP初赛的重点考查板块。希望本讲义能帮助考生系统掌握图论知识，在初赛中取得理想的成绩。建议考生在阅读本讲义的基础上，结合历年真题进行练习，将理论知识转化为解题能力。