2025 Summer Day25

课堂内容

图论基础知识

  • 图的定义：由点集 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