最小生成树：贪心算法的经典应用，Prim算法入门
本文介绍了生成树、最小生成树（MST）及Prim算法。生成树是连通无向图的无环子图，含所有顶点；MST是边权和最小的生成树，适合贪心算法（每步选局部最优得全局最优）。 Prim算法核心步骤：选起点，反复从已选和未选顶点间的边中选最小权边，将对应顶点加入已选集，直至所有顶点入集。关键是用邻接矩阵或邻接表记录图结构，算法伪代码中，`key`数组记录最小边权，`parent`记录父节点，时间复杂度邻接矩阵为O(n²)，优化后O(m log n)。 Prim算法基于贪心选择，安全边性质保证总权最小，应用于网络布线、电路设计等需最小成本连接所有节点的场景。总结：MST是贪心算法经典应用，Prim通过逐步扩展选最小边高效构建最优生成树。
阅读全文图：图的基本概念，邻接表表示法初学者指南
图由顶点（点）和边（连接关系）组成，顶点是基本单元，边可单向（有向图）或双向（无向图），有权图边带权重（如距离），无权图仅存连接关系。邻接表是高效表示法，解决邻接矩阵在稀疏图（边远少于顶点平方）中空间浪费问题，核心是每个顶点对应存储直接相连顶点的列表。无向图邻接表如顶点0连接1、2、3，邻接表为[1,2,3]；有权图可存“邻接点+权重”元组。邻接表空间复杂度O(V+E)（V顶点数，E边数），适合稀疏图，遍历邻接点方便，但判断两点是否有边需遍历邻接表。掌握邻接表为图遍历、最短路径等算法奠定基础。
阅读全文