Prim 最小生成树
图算法 · 最小生成树（MST）
什么是最小生成树
在一张无向带权连通图里，选若干条边把所有点连起来、不成环、总权重最小——就是最小生成树（MST）。Prim 和 Kruskal 是求它的两大经典算法，思路不同、结果一致。
Prim 怎么做
Prim 从一个起点开始，把它当作一棵只有一个点的树，然后让树一点点长大：每一步，在所有「一端在树里、一端在树外」的横切边里挑权重最小的那条，把它和它连接的树外点并入树。重复 V−1 次，就把所有点接进来了。
下面固定一张 6 个点的无向带权图，从 A 起。点「下一步」逐步看：当前选中的最小横切边黄色高亮，加入后变绿、新点也并进绿色的树。走到底得到 5 条边、总权重最小的生成树。右侧代码随每一步同步高亮。
从起点 A 开始，树里只有它一个点
为什么每步「贪心取最小横切边」是对的？由切分定理保证：把已在树里的点和其余点看成一种分割，横跨它的最小边一定属于某棵最小生成树。用堆维护候选横切边，复杂度约 O(E log V)——在稠密图上通常比 Kruskal 更省。
Prim vs Kruskal：同一问题，两种思路
Prim（本页）：从一个点生长，每步选「树↔树外」的最小横切边——始终维护一棵连通的树。稠密图更优。
Kruskal：把边按权全局排序，从小到大逐条尝试，用并查集判环——过程中是一片森林，最后才连成一棵。稀疏图更优。
两者在同一张图上得到相同的 MST（本页与 Kruskal 页正是同一张图，可对照：边集一样、加入顺序不同）。
Kruskal：把边按权全局排序，从小到大逐条尝试，用并查集判环——过程中是一片森林，最后才连成一棵。稀疏图更优。
两者在同一张图上得到相同的 MST（本页与 Kruskal 页正是同一张图，可对照：边集一样、加入顺序不同）。
想看按权选边 + 并查集判环的另一种建法，去看 Kruskal 最小生成树；判环背后的并查集，可回看 数据结构 · 并查集。