学习动机

Kruskal 会对所有边进行全局排序，并使用并查集；Prim 则维护一棵不断生长的树，并反复连接最近的树外顶点。

为什么要学习 Prim？

• 稠密图：使用合适的数据结构时，Prim 在边很多的图中效率很高。
• 割性质：它直观地说明了为什么连接当前树与外部的最小边总是可以安全添加。
• 同一问题的两种视角：比较 Prim 和 Kruskal 能加深你对最小生成树的理解。

由于图中所有最小生成树的边权总和相同，Prim 和 Kruskal 得出的总权重始终相同。