图论

图用顶点表示对象，用边表示关系。不同问题对边的方向、权值和重复次数有不同约束。

基础

最短路

最短路最小化两个顶点之间的路径权值。无权图使用 BFS；非负边权图可用 Dijkstra；负边权需要额外处理负环。

Dijkstra：非负边权的单源最短路。
Bellman–Ford：允许负边权，检测可达负环。
Floyd–Warshall：所有点对的最短距离。

最小生成树

最小生成树要求连接所有顶点，并最小化树的总边权；它不保证树上任意两点的路径最短。以下算法都针对带权无向图。

Prim：维护一个已连接顶点集合。
Kruskal：按边权排序，用并查集合并分量。
Borůvka：每轮选择各分量的最小外连边。

图模型

2-SAT：把二元逻辑约束变成蕴含图，通过强连通分量求解。
网络最大流：在容量与守恒约束下最大化源汇净流量。