第 4 章 · 01 最短路与最小生成树(对应 docs/graph/)

第 4 章 · 01 最短路与最小生成树(对应 docs/graph/)

本节定位:对应 OI Wiki docs/graph/(图论,61 篇)的基础部分。难度:进阶。前置依赖:第 3 章 01 节(并查集用于 Kruskal)+ 第 2 章(优先队列/复杂度)。

⚠️ 注意:图论题第一步永远是"看清是有向图还是无向图、有无负权、点数边数范围"。看错这些,Dijkstra 写得再对也 WA。这是图论题最常见的爆零原因。

知识地图

docs/graph/ 页面地图(基础部分)

docs/graph/ 61 篇,本节讲基础(最短路 + 最小生成树 + 图的存储 + 拓扑排序),进阶的网络流放第 02 节,连通性放第 03 节。

图的基本概念

• docs/graph/concept.md:图的概念(点/边/有向/无向/度/路径/连通)。
• docs/graph/save.md:图的存储(邻接矩阵 / 邻接表 / 链式前向星)。
• docs/graph/node.md:点相关。
• docs/graph/dfs.md / docs/graph/bfs.md:DFS / BFS 遍历。

最短路

• docs/graph/shortest-path.md:最短路总览(必读)。
• Dijkstra(在 shortest-path.md 内):非负权单源最短路。
• Bellman-Ford / SPFA(在 shortest-path.md 内):可判负环。
• Floyd(在 shortest-path.md 内):全源最短路 O(n^3)。
• docs/graph/diff-constraints.md:差分约束系统(最短路的转化应用)。
• docs/graph/kth-path.md:第 k 短路。
• docs/graph/mod-shortest-path.md:模意义最短路。
• docs/graph/min-cycle.md:最小环。

最小生成树

• docs/graph/mst.md:最小生成树(Kruskal / Prim)。
• docs/graph/dmst.md:有向最小生成树。
• docs/graph/mdst.md:最小直径生成树。
• docs/graph/steiner-tree.md:斯坦纳树。
• docs/graph/matrix-tree.md:矩阵树定理(生成树计数)。
• docs/graph/stoer-wagner.md:无向图最小割。

拓扑与 DAG

• docs/graph/topo.md:拓扑排序(Kahn 算法 / DFS)。
• docs/graph/dag.md:有向无环图。

图的存储

邻接矩阵 g[i][j]:O(n^2) 空间,适合稠密图(m 接近 n^2)和 Floyd。查询边 O(1)。

链式前向星(竞赛主流):用数组模拟邻接表,O(n+m) 空间,适合稀疏图。

struct Edge{ int to, w, nxt; } e[M];
int head[N], cnt;
void add(int u,int v,int w){
  e[++cnt]={v, w, head[u]}; head[u]=cnt;
}
// 遍历 u 的所有出边:
for(int i=head[u]; i; i=e[i].nxt){
  int v=e[i].to, w=e[i].w;
  ...
}
​

链式前向星比 vector<int> g[N] 略快(无动态分配),但 vector 写法更简洁,新人先用 vector 也行。

最短路算法对比

Dijkstra(堆优化)必会:docs/graph/shortest-path.md。核心:用小根堆维护"未确定最短路的点中距离最小的",每次取出确定,松弛邻居。

priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>> q;
memset(dis,0x3f,sizeof dis); dis[s]=0;
q.push({0,s});
while(!q.empty()){
  auto [d,u]=q.top(); q.pop();
  if(d>dis[u]) continue;            // ★ 过期数据跳过(重要优化)
  for(int i=head[u]; i; i=e[i].nxt){
    int v=e[i].to;
    if(dis[u]+e[i].w<dis[v]){
      dis[v]=dis[u]+e[i].w;
      q.push({dis[v],v});
    }
  }
}
​

💡 学习提示:if(d > dis[u]) continue; 这一行是堆优化 Dijkstra 的关键优化。堆里可能有同一点的多个过期记录(后来被更短距离覆盖),必须跳过,否则复杂度退化。

SPFA"已死"的梗:SPFA(Shortest Path Faster Algorithm)是 Bellman-Ford 的队列优化,平均快但最坏 O(nm),会被特殊构造的数据卡到 TLE。NOIp2018 出题人故意卡 SPFA 后,"SPFA 已死"成梗。但 SPFA 仍要会——它能判负环(Dijkstra 不能),且差分约束系统靠它。

Floyd:三重循环 dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k]+dp[k-1][k][j]),滚动数组降到二维。求全源最短路、传递闭包、找最小环。

最小生成树

Kruskal(更常用):把所有边按权排序,依次尝试加入,用并查集判是否成环。O(m \log m),稀疏图首选。

sort(e+1, e+m+1, [](Edge a,Edge b){ return a.w<b.w; });
for(int i=1; i<=m && cnt<n-1; i++){
  if(find(e[i].u)!=find(e[i].v)){
    unite(e[i].u, e[i].v);
    ans += e[i].w; cnt++;
  }
}
​

Prim(堆优化):类似 Dijkstra,从一点出发每次加入最近的非树点。O((n+m)\log n),稠密图更优。

拓扑排序

docs/graph/topo.md。DAG(有向无环图)的拓扑序:BFS 入度法(Kahn),每次取入度为 0 的点入队,删边更新邻居入度。用于:依赖关系、DP 转移顺序、判断是否有环。

学习建议

Dijkstra 是图论必会

💡 学习提示:堆优化 Dijkstra 是图论最高频的算法,几乎所有最短路题都用它(只要无负权)。代码 20 行,必须背到能默写。STL priority_queue 默认大根堆,要小根堆写 priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>>。

MST Kruskal 比 Prim 更常用

竞赛图多为稀疏图,Kruskal(排序边 + 并查集)代码更短、思路更清晰,默认选 Kruskal。Prim 只在稠密图(m 接近 n^2)时考虑。

学习顺序

1. 图的概念 + 存储(concept.md / save.md,先过)
2. DFS / BFS(dfs.md / bfs.md,遍历基础)
3. Dijkstra 堆优化(★ 必精)
4. SPFA + 判负环(会写、知道最坏复杂度)
5. Floyd(会用,知道 n \le 500)
6. Kruskal MST(★ 必精,复用并查集)
7. Prim(了解)
8. 拓扑排序(DAG 基础)
9. 差分约束系统(最短路转化,diff-constraints.md)

每个算法配套刷洛谷模板题:P4779 单源最短路(Dijkstra)、P3371 单源最短路(SPFA)、P3366 最小生成树。

常见误区

⚠️ 注意:

1. 有向图当无向图写:加边时只加单向,或建无向图只加一次边。无向图要 add(u,v,w); add(v,u,w);。
2. 负权图用 Dijkstra:Dijkstra 不能处理负权,会出错。有负权用 SPFA / Bellman-Ford。
3. SPFA 不带 SLF 优化被卡 / 带了 SLF 被故意卡:竞赛中 SPFA 谨慎用,优先 Dijkstra。
4. Kruskal 忘排序边:必须先按权升序排序。
5. Dijkstra 堆里过期数据没跳过:if(d>dis[u]) continue; 漏写会 TLE/MLE。
6. 图论题不看数据范围:n=10^5 写 Floyd 必 TLE。

本节要点

1. docs/graph/ 基础:图的存储(邻接矩阵 / 链式前向星)+ 最短路 + MST + 拓扑排序。
2. 链式前向星是竞赛主流存储,O(n+m) 空间。
3. Dijkstra 堆优化是图论必会,非负权单源最短路 O((n+m)\log n),堆里过期数据要跳过。
4. SPFA 能判负环但最坏 O(nm),"SPFA 已死"指别滥用;Floyd 全源 O(n^3) 适合 n \le 500。
5. MST 默认 Kruskal(排序边 + 并查集)O(m \log m);Prim 稠密图更优。Kruskal 前置是第 3 章并查集。