初级图论有哪些基本概念和算法？

本文共计24301个文字，预计阅读时间需要98分钟。

基础图论：最短路径（Bellman-Ford、Dijkstra、SPFA、Johnson、Floyd）, 差分约束，最小生成树（Kruskal、Prim、Boruvka）, 有向图与无向图连通性（割点、割边，E-BCC 和 SCC 的缩点），欧拉回路 + CHA

基础图论：最短路（Bellman-Ford，Dijsktra，SPFA，Johnson，Floyd），差分约束，最小生成树（Kruskal，Prim，Boruvka），有向图与无向图连通性（割点，割边，E-BCC 和 SCC 的缩点），欧拉回路 CHANGE LOG

• 2021.12.5：修改例题代码与部分表述，增加基础定义。
• 2022.4.22：重构文章。
• 2022.5.21：进行一些增补，添加 Floyd 算法和 SCC 缩点。
• 2022.5.25：添加 Hierholzer 算法。

1. 最短路

最短路是图论最基本的一类问题。

下文记 \(dis_u\) 表示从源点到节点 \(u\) 的最短路，\(n\) 为节点数 \(|V|\)，\(m\) 为边数 \(|E|\)。

1.1 Bellman-Ford

Bellman-Ford 是一种非常暴力的求解最短路的方法（BF 之于 Dijkstra 如同 FF 之于 Dinic）。

称一轮 松弛 为对于每一条边 \((u, v)\)，用 \(dis_u + w_{u, v}\) 更新 \(dis_v\)。我们断言每轮至少有一个节点的最短路被更新。松弛 \(n - 1\) 轮即可。

正确性证明：设源点为 \(1\)。