🕸️ 408 图论核心算法速查笔记

核心痛点解决

图论算法极容易混淆(Prim/Kruskal/Dijkstra/Floyd)。本笔记按 408 考察频率 排序。 【口诀 + 可折叠手算例子 + 破局思路 + 变体预警】,让你看到题目就能瞬间提取出“该用哪个算法”。


1. 广度优先搜索(BFS)—— 考察频率:⭐⭐⭐⭐⭐

一句话记忆

“层序遍历,无权图的最短路径”。从起点开始,一圈一圈往外扩,第一次遇到的节点,路径一定最短。

变体预警

如果题目说“各边权值不全为 1”(带权图),BFS 就失效了,必须用 Dijkstra(非负权)或 Floyd。408 选择题最爱考这个“权值均为 1”的前提。


2. 迪杰斯特拉(Dijkstra)—— 考察频率:⭐⭐⭐⭐⭐

一句话记忆

“单源最短路径,贪心选最近”。从起点开始,每次从未确定的点中选一个距离最小的,然后用它去更新邻居。

变体预警

408 常考“Dijkstra 算法在什么时候会失效?”答案就是存在负权边时。带负权的最短路径要用 Floyd 或 Bellman-Ford。


3. 普利姆(Prim)与克鲁斯卡尔(Kruskal)最小生成树 —— 考察频率:⭐⭐⭐⭐

核心机制一句话秒杀

  • Prim(加点法 · 滚雪球):从源点出发,时刻保持一棵唯一的连通生长树,每次从连接“已选点”与“未选点”的跨界割边中挑最小边把新点拉入。适合稠密图(时间复杂度 ,与边数无关)。
  • Kruskal(加边法 · 森林合并):全局按权值贪心升序挑边,只要权值最小就选,根本不管跟当前树连不连得上!允许中间状态呈现多棵孤立树构成的森林,依赖并查集防环。适合稀疏图(时间复杂度 )。

变体预警(408 连环陷阱)

  1. “某算法在执行过程中的某一时刻,已选的边集可能包含若干棵互不连通的子树,该算法是?” → 毫无悬念,必选 Kruskal!
  2. “某算法在任何时刻选出的边集始终构成一棵连通的树,该算法是?” → 毫无悬念,必选 Prim!
  3. 如果题目说“各边权值均为 1”,Prim 和 Kruskal 都能求出最小生成树,但它们求的是整体连通代价最小,不是单源最短路径(单源最短路径边权为 1 必须用 BFS)。

5. 弗洛伊德(Floyd)—— 考察频率:⭐⭐⭐⭐

一句话记忆

“多源最短路径,动态规划”。用一个二维矩阵,不断尝试“经过中间点 k 会不会更短”。

变体预警

Floyd 的时间复杂度是 O(n³),适合多源最短路径。408 常考“Floyd 算法可以处理负权边,但不能处理负权回路”。


6. 拓扑排序(Topological Sort)—— 考察频率:⭐⭐⭐⭐

一句话记忆

“有向无环图,找入度为 0 的点”。每次选一个入度为 0 的顶点输出,然后删除它和它的所有出边。

变体预警

408 常考“拓扑排序和逆拓扑排序的区别”。逆拓扑排序是每次选出度为 0 的点输出并删除入边。


7. 关键路径(Critical Path)—— 考察频率:⭐⭐⭐

一句话记忆

“AOE 网,源点到汇点的最长路径”。最长路径的长度决定了整个工程的最短完成时间(工期)。

变体预警(408 最爱考的 3 条铁律)

  1. 缩短某条关键活动的时间,不一定能缩短整个工期:因为缩短太多可能会使原本的关键路径变成非关键路径;或者当图中存在多条并列的关键路径时,只缩短其中一条关键路径上的活动,总工期完全不变!
  2. 要缩短整个工期,必须同时缩短所有关键路径上的关键活动(或缩短所有关键路径的公共关键活动)。
  3. 延长任意一条关键活动的时间,整个工程工期一定延长!

📋 图论算法速查表(重点背诵)

算法目的适用图时间复杂度核心口诀
BFS单源最短路径无权图O(V+E)层序遍历,边权为 1
Dijkstra单源最短路径非负权图O(V²)贪心选最近,不能负权
Floyd多源最短路径带权图O(V³)动态规划,三重循环
Prim最小生成树稠密图O(V²)加点法,选最小边
Kruskal最小生成树稀疏图O(E log E)加边法,判环
拓扑排序有向无环图排序DAGO(V+E)入度为 0 输出
关键路径AOE 网工期DAGO(V+E)最长路径,无机动

易混淆对比(408 最爱考)

  • Prim vs Dijkstra:Prim 求的是“连通所有点的最小总代价”,Dijkstra 求的是“从起点到各点的最短路径”。两者都是贪心,都从已选点集出发,但目标不同。
  • BFS vs Dijkstra:BFS 是 Dijkstra 在“边权为 1”时的特例。BFS 用队列,Dijkstra 用优先队列。
  • Kruskal vs Prim:Kruskal 适合稀疏图,Prim 适合稠密图。
  • Floyd vs Dijkstra:Floyd 是多源,Dijkstra 是单源;Floyd 可以处理负权边,Dijkstra 不能。
  • 拓扑排序 vs 关键路径:拓扑排序是求“一个可行的执行顺序”,关键路径是求“最短完成时间”。关键路径上的活动没有机动时间。

📝 考前复习建议

考前复习建议

  1. 画图:Prim/Kruskal 手动画生成树过程;Dijkstra/Floyd 手动更新 dist 矩阵。
  2. 背表:上面的速查表和易混淆对比,考前看一遍,选择题直接秒杀。
  3. 看变体预警:每个算法下的 [!warning] 块,都是选择题的陷阱所在。
  4. 抓前提:题目中的“权值均为 1”、“非负权”、“稀疏图/稠密图”是关键判断依据。