6.4.1 最小生成树

连通无向加权图的生成树含全部 V 个顶点和 V-1 条边。Prim 从一个顶点集合向外选最轻跨割边；Kruskal 按边权递增，若两端属于不同集合就选边并合并。权值相同可能有多棵最小树。

手工状态

边AB1,BC2,AC3,CD4：Kruskal选AB、BC，AC会成环跳过，再选CD，总权7。Prim从A也先选AB、再BC、再CD。

结构与代码

Kruskal配并查集 O(E log E)；Prim用堆和邻接表 O(E log V)。图不连通时只能得到最小生成森林。

正确性依据

割性质：任意割上的最轻边存在于某棵MST；环性质：环上严格最重边不可能属于任何MST。两算法都保持可扩展到最优解。

错解反馈

按最短路径理解MST；选了V-1条边却没检查连通；Kruskal不查成环。

迁移训练

边01:1,12:2,02:2,23:5，MST权多少？答案8，前3点选两条权1、2边，再接23。