最小生成树：贪心算法的经典应用，Prim算法入门
本文介绍了生成树、最小生成树（MST）及Prim算法。生成树是连通无向图的无环子图，含所有顶点；MST是边权和最小的生成树，适合贪心算法（每步选局部最优得全局最优）。 Prim算法核心步骤：选起点，反复从已选和未选顶点间的边中选最小权边，将对应顶点加入已选集，直至所有顶点入集。关键是用邻接矩阵或邻接表记录图结构，算法伪代码中，`key`数组记录最小边权，`parent`记录父节点，时间复杂度邻接矩阵为O(n²)，优化后O(m log n)。 Prim算法基于贪心选择，安全边性质保证总权最小，应用于网络布线、电路设计等需最小成本连接所有节点的场景。总结：MST是贪心算法经典应用，Prim通过逐步扩展选最小边高效构建最优生成树。
阅读全文贪心算法：贪心算法是什么？找零钱问题实例讲解
贪心算法是每步选择当前最优（局部最优）以期望全局最优的算法，核心是满足“贪心选择性质”——每步局部最优能导致全局最优。经典应用如找零钱：以25、10、5、1分硬币为例，找67分时，按从大到小逐步取25×2（50分）、10×1（10分）、5×1（5分）、1×2（2分），共6枚，验证为最优。其局限性在于，若问题不满足贪心选择性质（如硬币面额[1,3,4]找6分），贪心可能失效（贪心取4+1+1=3枚，最优为3+3=2枚）。适用场景包括硬币面额合理（如25、10、5、1）、活动安排（选最早结束活动）等。总之，贪心算法简单直观高效，但仅适用于满足贪心选择性质的问题，不保证所有问题全局最优。
阅读全文