图论算法全家桶：最短路径、最小生成树、网络流一网打尽

图论是 NOI 级别的核心考点，约占总分的 25%-35%。本文系统整理竞赛中需要的图论算法。

一、图的基础

• 邻接矩阵、邻接表、链式前向星（竞赛首选）


• 有向图/无向图、连通图、完全图


• 度、入度、出度、路径、回路

• Dijkstra（堆优化）：非负权图首选，O((V+E) log V)


• SPFA：可处理负权，但可能被卡到 O(VE)


• Floyd-Warshall：多源最短路，O(V³)


• Johnson：含负权图的多源最短路

• Kruskal（并查集 + 排序）：最常用


• Prim（堆优化）：稠密图更优


• 次小生成树（严格/非严格）

• Kahn 算法（BFS 入度）


• DFS 后序遍历


• DAG 上的 DP

• 强连通分量：Tarjan 算法、Kosaraju 算法


• 双连通分量：点双/边双


• 桥与割点


• 2-SAT 问题

• 倍增法（最常用）


• Tarjan 离线算法


• 树链剖分求 LCA


• RMQ + 欧拉序

• 最大流：Dinic 算法（竞赛首选）


• 最小费用最大流：SPFA + Dinic


• 上下界网络流


• 最大权闭合子图


• 二分图最大匹配 → 匈牙利算法 / 网络流