考研笔记

最小生成树与最短路径

四个算法你都会写，但 408 一个都不让你写——它让你「动手模拟实现步骤」。

教材对 MST 的要求写得很直白：

对这两种算法应主要掌握算法的本质含义和基本思想，并能动手模拟算法的实现步骤。

所以这一节的全部工作量在手上：Prim 的逐步加点图、Kruskal 的逐步选边图、Dijkstra 的逐轮 dist 表。 三张图表画熟，这一节就结束了。

机制

最小生成树的性质

假设 是一个带权连通无向图， 是顶点集 的一个非空子集。若 是一条具有最小权值的边，其中 ，，则必存在一棵包含边 的最小生成树。

基于该性质的最小生成树算法主要有 Prim 算法和 Kruskal 算法，它们都基于贪心算法的策略。

教材还给了一个通用算法，把两者的共性抽出来：

GENERIC_MST(G){
    T=NULL;
    while T 未形成一棵生成树;
        do 找到一条最小代价边(u,v)并且加入 T 后不会产生回路;
            T=T∪(u,v);
}

「加入后不会产生回路」这句话就是 Kruskal 需要并查集的原因。

Prim 算法

初始时从图中任取一顶点（如顶点 1）加入树 ，此时树中只含有一个顶点，之后选择一个与当前 中顶点集合距离最近的顶点，并将该顶点和相应的边加入 ，每次操作后 中的顶点数和边数都增 1。以此类推，直至图中所有的顶点都并入 。此时 中必然有 条边。

  • 初始化：向空树 中添加图 的任意一个顶点 ，使 ，。
  • 循环（重复下列操作直至 ）：从图 中选择满足 且具有最小权值的边 ，加入树 ，置 ，。

时间复杂度 ，不依赖 ，因此适用于求解边稠密的图。

Kruskal 算法

按权值的递增次序选择合适的边来构造最小生成树：初始时为只有 个顶点而无边的非连通图 ，每个顶点自成一个连通分量；然后按照边的权值由小到大的顺序，不断选取当前未被选取过且权值最小的边，若该边依附的顶点落在 中不同的连通分量上，则将此边加入 ，否则舍弃此边而选择下一条权值最小的边。以此类推，直至 中所有顶点都在一个连通分量上。

时间复杂度 ，适合于边稀疏而顶点较多的图。

边界辨析：

最小生成树的权值之和总是唯一的，但树形不一定唯一。 判据：若图中各边的权值互不相等，则最小生成树唯一；若存在相等权值的边，可能有多棵。 另外，MST 的边数恒为 ，且 MST 只对连通无向图有定义——非连通图只有最小生成森林。

Dijkstra 算法

教材表 6.2 的逐轮填表法就是标准答题格式，必须照着写。以教材图 6.17 为例，求从顶点 出发至其余顶点的最短路径：

初始化：集合 初始为 ， 可达 和 ， 不可达 和 ，因此 dist[] 数组各元素的初始值依次设置为 dist[2]=10、dist[3]=∞、dist[4]=∞、dist[5]=5。

顶点第 1 轮第 2 轮第 3 轮第 4 轮
210
8
8
314
13
9
47
55
集合

每轮两个动作：① 选出 dist[] 中的最小值，把该顶点并入 ；② 以这个新点为中转，更新 外所有点的 dist[]。

时间复杂度 。

关联对照：

教材脚注专门问了「Dijkstra 算法与 Prim 算法有何异同之处」，并给了三条答案：

PrimDijkstra
i. 目的构建最小生成树构建单源点的最短路径树
ii. 思路从一个点开始，每次选择权值最小的边，将其连接到已构建的生成树上每次找出到源点距离最近且未归入集合的点，并以这个点为基础更新源点到其他所有顶点的距离
iii. 适用的图只能用于带权无向图可用于带权有向图或带权无向图

第 iii 条最常考。 两者都基于贪心策略，但「选边最小」和「选点距离最小」是两回事—— Prim 比的是这一条边的权，Dijkstra 比的是从源点累计的距离。

边权为负时 Dijkstra 失效

Dijkstra 算法要求边上的权值非负。 若存在负权边，已并入 的顶点的 dist 可能还会被后来的负边改小，而算法不再回头更新它，因此结果可能错误。

Floyd 算法

用于求每对顶点之间的最短路径，采用动态规划思想：递推产生一个 阶方阵序列 ，其中

时间复杂度 ，空间复杂度 。Floyd 算法允许图中有带负权值的边，但不允许有包含带负权值的边组成的回路。

Floyd 也适用于带权无向图（可视为有向完全图）。

手算模板

Prim：

  1. 圈定起点，。
  2. 每轮：在所有一端在 、另一端在 的边里挑权最小的，加入。
  3. 画出每一轮后的树形。共 轮。

Kruskal：

  1. 把所有边按权值从小到大排成一列。
  2. 逐条看：两端在不同连通分量则选，否则跳过。
  3. 选够 条就停。

Dijkstra（照表 6.2 的格式）：

  1. 画表：行是顶点，列是轮次，每格写 dist 值 + 路径。
  2. 初始化 dist[]：源点直接可达的填权值，不可达填 。
  3. 每轮：选最小的 dist 并标记（该格加粗/画框）→ 并入 → 更新其余各点。
  4. 最后一行写出每轮的 。
  5. 共 轮。

Floyd：写出 每一步的矩阵，第 步只允许以 为中转。

边界

说法判断说明
「最小生成树唯一」❌权值之和唯一，树形不一定唯一；各边权互不相等时才唯一
「MST 的边数不定」❌恒为
「MST 对有向图也有定义」❌只对连通无向图
「Prim 适合稀疏图」❌，适合稠密图；Kruskal 适合稀疏图
「Prim 的复杂度与边数有关」❌，不依赖
「Kruskal 每次选权最小的边就一定加入」❌还要判两端是否在不同连通分量
「Prim 可用于有向图」❌只能用于带权无向图（教材脚注 iii）
「Dijkstra 只能用于有向图」❌有向无向都可以
「Dijkstra 能处理负权边」❌要求权值非负
「Dijkstra 每轮确定一个顶点的最短路径」✅被并入 的那个顶点的 dist 此后不再变
「Dijkstra 与 Prim 的区别只是目的不同」❌还有思路和适用图两条（教材脚注给了三条）
「Floyd 不能有负权边」❌允许负权边，但不允许负权回路
「Floyd 只能用于有向图」❌无向图也可以
「BFS 可求带权图最短路径」❌只对无权图（6.3）

口径差异：

算竞里这四个算法的写法和 408 差得很远：

算竞408 / 王道
Prim堆优化，朴素 ，且要画出每轮的树形
Kruskal并查集 + 排序同上，但要列出每条边的取舍
Dijkstra优先队列，朴素 ，且要逐轮填 dist/路径表
负权上 SPFA / Bellman-Ford只考「Dijkstra 不能有负权、Floyd 不能有负权回路」这个结论

最关键的差别：408 要的是过程表，不是复杂度。 用堆优化 Dijkstra 的思路去做题，会答不出「第 2 轮 dist[3] 是多少」这种问题—— 因为堆优化版本根本不维护一张按轮次演进的完整 dist 表。

对照速查

算法解决时间适用图负权
Prim最小生成树带权无向图，稠密—
Kruskal最小生成树带权无向图，稀疏—
Dijkstra单源最短路径带权有向或无向图不允许负权边
Floyd每对顶点最短路径带权有向或无向图允许负权边，不允许负权回路
Prim vs DijkstraPrimDijkstra
比什么一条边的权从源点累计的距离
产物最小生成树最短路径树
适用仅无向有向或无向

考点

  • Prim 算法构造最小生成树的实例（2015、2017、2018 命题追踪）——画每轮树形。
  • Dijkstra 算法求解最短路径的实例（2012、2014、2016、2021 命题追踪）——逐轮填表。
  • Prim 与 Dijkstra 的三点区别（教材脚注），尤其适用图不同。
  • MST 权值之和唯一、树形不一定唯一。
  • Prim 适合稠密图，Kruskal 适合稀疏图。
  • Dijkstra 不允许负权边；Floyd 允许负权边但不允许负权回路。
  • Floyd 的递推式与 。

链接

反向链接