初级图论
2021.12.5:修改例题代码与部分表述,增加基础定义.
2022.4.22:重构文章.
2022.5.21:进行一些增补,添加 Floyd 算法,E-BCC 和 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)),用