最小生成树：Prim与Kruskal

考点定位

本课深化 最小生成树：Prim与Kruskal。408作答必须同时给出数据结构表示、算法过程、不变量、复杂度和边界条件。

结构与取舍

MST连接全部顶点、无环、含n-1条边且总权最小。Prim扩展一个顶点集合；Kruskal按边权排序并用并查集拒绝成环。

算法推演

Kruskal不变量：已选边构成森林，并能扩展为某棵MST；跨越不同连通分量的当前最小边是安全边。

把算法写成“初始化—循环条件—状态更新—终止输出”。若使用递归、队列、堆或并查集，要指出其中保存的状态及何时失效。

正确性不变量

任何时刻已选边无环；连通图选满n-1条边后即为生成树。

初始化时不变量成立；一次迭代保持它；循环结束时它与终止条件共同推出答案。这是算法题证明的最短主线。

复杂度与边界

时间复杂度必须按输入规模和存储结构计算，不能只报结论。严格边界：MST最小化总边权，不保证任意两点在树上的路径都是原图最短路。

随课应用

三角形三条边权分别1、2、5，其最小生成树总权是多少？

先独立计算或编码，再完成单选与多选。代码题从标准输入读取并写到标准输出，不得硬编码样例；数值题需写出中间状态。