最小生成树

• 定义：连通图的极小连通子图，包含所有 $n$ 个顶点，只有 $n-1$ 条边，且权值之和最小。
• 算法对比 (必考)：

特性	Prim算法 (普里姆)	Kruskal算法 (克鲁斯卡尔)
核心思想	加点法。从一个顶点出发，不断找连接已选集合与未选集合的最小边。	加边法。按权值从小到大排序，若不构成环则加入。
适用场景	稠密图 (边多)	稀疏图 (边少)
时间复杂度	$O(n^2)$	$O(e\log e)$
关键操作	更新 lowcost 数组	并查集 (Union-Find) 检测环