最小生成树：贪心算法的经典应用，Prim算法入门

本文介绍了生成树、最小生成树（MST）及Prim算法。生成树是连通无向图的无环子图，含所有顶点；MST是边权和最小的生成树，适合贪心算法（每步选局部最优得全局最优）。 Prim算法核心步骤：选起点，反复从已选和未选顶点间的边中选最小权边，将对应顶点加入已选集，直至所有顶点入集。关键是用邻接矩阵或邻接表记录图结构，算法伪代码中，`key`数组记录最小边权，`parent`记录父节点，时间复杂度邻接矩阵为O(n²)，优化后O(m log n)。 Prim算法基于贪心选择，安全边性质保证总权最小，应用于网络布线、电路设计等需最小成本连接所有节点的场景。总结：MST是贪心算法经典应用，Prim通过逐步扩展选最小边高效构建最优生成树。