Prim 算法
从单个点出发,每次把连接已选集合的最小边加入,逐步扩展出最小生成树。时间 O((n + m) log n),空间 O(n + m) · 标签 图论 / 最小生成树 / 贪心 / 优先队列
核心思想
维护已选顶点集合 (初始只含起点),以及每个未选顶点到 的最短边权 dist。
每次从尚未选入的顶点中取出 dist 最小的 ,把对应的边加入生成树,并把 并入 。 重复 次,就得到一棵最小生成树。
正确性
当前已选集合 与剩余顶点构成一个割。由割性质,横跨这个割的最小边一定属于某棵 MST;Prim 每轮选的正是这条边,所以每次加入都是安全的。重复 次后得到一棵 MST。
与 Dijkstra 的区别
- Dijkstra 的
dist[v]是源点到 的路径长度,松弛是dist[v] = min(dist[v], dist[u] + w)。 - Prim 的
dist[v]是 到集合 的最短边权,松弛是dist[v] = min(dist[v], w)。
两者都“每次取最小”,但比较的对象不同。把 Prim 写成 Dijkstra 的松弛,得到的是最短路树,不是 MST。
易错点
- 图不连通时没有 MST:最后检查访问点数是否为 ,否则返回无解。
- 起点可以任选;连通图从任意点出发都能得到某棵 MST。
与 Kruskal 的取舍
- Prim 从点扩展,适合稠密图;邻接矩阵 很稳。
- Kruskal 从边扩展,适合稀疏图;需要排序和并查集。
- 两者都基于割性质,总权值相同;MST 不唯一时可能得到不同的树。
变式
- 最小生成森林:对每个未访问的连通块各跑一次 Prim。
- 完全图上的 Prim:边不显式给出,而是在扩展时用公式计算边权。
- 虚拟源点:把“自建”方案连到虚拟点后再求 MST。