Content：图论基础
Date：2025.8.10

课堂内容

图论基础知识

图的定义：由点集 $V$ 和边集 $E$ 组成，记作图 $G (V, E)$ 。
阶：图的点数，记作 $|G|$ 。
相邻：称图中的两个点相邻，当且仅当 $(i,v) \in E$ 。
连通：无向图中若存在 $v_0 = u, v_k = v$ 的路径则称 $u, v$ 连通。
弱连通：若有向图变为无向图后 $u, v$ 连通，则称 $u, v$ 弱连通。
连通图：无向图中任意两点连通的图称作连通图。
弱连通图：有向图中任意两点弱连通的图称作弱连通图。
简单图：不存在重边和自环的图。
稀疏图/稠密图： $|E| \ll |V|^2$ 的图称作稀疏图， $|E|$ 接近 $|V|^2$ 的图称作稠密图。

拓扑排序

Problem

给定一个有向无环图（DAG），要求求出一个序列 $p$ ，其中 $u$ 在排列 $p$ 中的位置记作 $q_u$ ，则这个序列满足满足：

$\forall \ u \to v \in E$ ， $q_u < q_v$ 。

Solution

每次从 DAG 中选择一个入度为 0 的点，将这个点加入序列 $p$ 中，然后删掉这个点和这个点在图中的所有出边，重复这个过程。

Proof

显然对于任意的 $u \to v \in E$ ，点 $u$ 总是在 $v$ 之前被加入序列 $p$ ，所以最后得到的学列一定是合法的。复杂度为 $O (n+m)$ 。

Extend

可以用拓扑排序判断一个有向图是否存在环。

最短路算法

Problem 1

给定一张图和一个源点 $s$ ，求图上所有点到源点 $s$ 的最短距离 $D_u$ 。

Solution

Bellman-Ford

松弛操作：称一次松弛操作为对于每一条边 $(u, v, w)$ ，用 $dis_u + w \to dis_u$ 。
这样进行松弛操作 $n-1$ 轮就可以得到 $D_u$ 。复杂度为 $O (nm)$ 。

Extend: Bellman-Ford 算法也可以用来判断图中是否存在负环。如果进行了 $n-1$ 轮松弛操作后依然存在可以被更新的 $dis_u$ ，则图中一定存在负环。因为在这个操作中负环被视为无穷小而被无限更新下去。

SPFA

~~关于 SPFA，它死了。~~

松弛点 $u$ 时若存在可以用 $(u, v, w)$ 更新的 $dis_v$ 且 $v$ 不在队列中，则将 $v$ 压入队列，重复这个过程知道队列为空。复杂度 $O(nm)$ 。

Extend：和 bellman-ford 一样，如果存在点被压入队列超过 $n-1$ 次，则图中存在负环。

Dijkstra

扩展：对于一个点 $u$ ，称扩展点 $u$ 表示用 $u$ 的所有出边 $(u, v, w)$ 更新 $dis_v$ 。

每次选择未被扩展的 $dis_u$ 最小的点 $u$ 进行扩展，可以用 优先队列 将复杂度优化到 $O(m \log m)$ ，但只能处理 非负权图。

Problem 2

对于一个给定的图，求图中任意两点的最短距离。

Solution

Johnson

从超级源点向所有点连一条 $(S, u, 0)$ 的边，跑一边 Bellman-Ford/SPFA 得到最短路 $h_u$ 。然后改造边为 $(u, v, w + h_u - h_{v})$ 。然后再在新图上跑一边 Dijkstra（新图为非负权图），复杂度为 $O (nm \log m)$ 。

Floyd

初始化所有 $dis_{u, u} = 0;\forall (u,v,w) \in E,dis_{u,v} = \min\{w\}$ ，然后在这个数组上进行如下更新：

dis_{i,j} = \min_{k} (dis_{i,k} + dis{k,j})

实际上就是一个动态规划，复杂度为 $O (n^3)$ 。

最短路树

在单源最短路中，记录每个点最后被更新的前驱 $pre_u$ ，以这个建边得到的树就是最短路树。

删边最短路

Problem

给定一个正权无向图，求删除每一条边后从 $1$ 到 $n$ 的最短路。

Solution

我们建立一个从 $1$ 出发的最短路树 $T_1$ ，和一个到达 $n$ 的最短路树 $T_2$ 。容易发现若删除的边 $(u, v)$ 不在原最短路上，则删除 $(u,v)$ 不会影响答案。

所以我们不妨设原最短路为 $1 \leadsto i \to j \leadsto n$ ，找到所有满足 $u$ 不在 $T_2$ 的 $i$ 的子树内， $v$ 不在 $T_1$ 的 $j$ 的子树内的所有边 $(u, v, w)$ 。用 $dis(u,LCA(T_1,u,n)) + w(u,v) + dis(v,LCA(T_2,v,1))$ 更新答案。复杂度可以用数据结构优化到 $O(m \log m)$ 。

无向图连通性

定义

割边：删去后使得连通分量增加的边。
割点：删去后使得连通分量增加的点
点双连通图：不存在割点的无向连通图。
边双连通图：不存在割边的无向连通图。
点双连通分量：极大点双连通子图，即 V-BCC。
边双连通分量：极大边双连通子图，即 E-BCC。

性质

点双连通分量

若两个点双连通分量有交点，则这个交点有且仅有一个，且为割点。
一个点是割点当且仅当它属于超过一个边双连通分量。
一条边仅属于一个点双连通分量。
由一条边直接连接的两个点 点双连通。
点双内任意一个点 $u$ 均存在经过这个点的简单环。
点双内任意一个点对 $(u,v)$ ，均存在包含这个点对的简单环。

边双连通分量

两个点之间任意一条迹上的所有割边就是这两个点的必经边。
若 $x$ 和 $y$ 边双连通， $y$ 和 $z$ 边双连通，则 $x$ 和 $z$ 边双连通（传递性）。
$u$ 和 $v$ 之间边双连通当且仅当这两个点之间的必经边集合为空。
对于一个边双连通分量中的任意一条边 $(u,v)$ ，均存在经过这条边的回路。
边双内任意一点均存在经过这个点的回路。
边双内任意一组点对 $(u,v)$ 均存在包含这个点对的回路。

求解

点双连通分量：Link
边双连通分量：Link

有向图连通性

定义

强连通：一个点对 $(u,v)$ 互相可达。
强连通图：图中任意两点互相可达的有向连通图。
强连通分量：极大的强连通子图，即 SCC。

性质

若 $dfn_v < dfn_u$ ，则 $u$ 可达 $v$ 当且仅当 $v$ 可达 $u$ 。
若 $u,v$ 强连通，则 $u,v$ 在 dfs 树上路径的所有点弱连通。
强连通分量在 dfs 树上弱连通。

求解

强连通分量（Tarjan）：Link

最小生成树

定义

生成树：对于连通图而言，生成树是原图一个树形结构的生成子图。
生成森林：每一个连通分量的生成树组成的子图。

求解最小生成树

Kruskal

首先对原图的边按照边的权值从小到大排序，然后枚举每一条边，如果这条边连接的两个点现在并不连通，则将这一条边加入最小生成树。连通性可以用并查集维护，复杂度为 $O(m \log m)$ 。

实现：Link

Prim

类似 Dijkstra，每次选择一个现在在最小生成树上的点 $u \in S$ （ $S$ 为当前已经加入最小生成树的点集），将满足 $(u,v,w) \in E,v \not\in S$ 且 $w$ 最小的边加入最小生成树。用优先队列可以把复杂度优化到 $O((n+m) \log n)$ 。

实现：Link

例题

Luogu-P1967 [NOIP 2013 提高组] 货车运输

题目大意

给定一张由 $n$ 个点 $m$ 条双向边组成的无向带权图，有 $q$ 次询问，每次询问 $u, v$ 之间的最大瓶颈路。

思路

首先如果对于每次询问都单独跑一边 Dijkstra 的复杂度是 $O (n m \log m)$ 的，显然不可接受。

我们发现由于题目要求的是瓶颈路，所以很多边都是用不到的。更进一步的，我们发现只有原图中 最大生成树 上的边才是有用的。所以我们可以对于原图的最大生成树重新建边，然后这个问题就转化为了树上问题。

转化为树上问题后， $u, v$ 的路径很显然可以分为 $u \to LCA (u, v)$ 和 $v \to LCA (u, v)$ ，所以就转化为了求树上两个点之间路径上的最小权值。可以用倍增求 $LCA$ ，复杂度为 $O(n \log n)$ 。

提交记录：Link