北京大学暑期课：最小生成树(MST)算法解析

"最小生成树(MST)问题——北京大学暑期课《ACM/ICPC竞赛训练》" 最小生成树(MST)问题在图论中占据重要地位，尤其在计算机科学领域内的算法设计和网络优化中应用广泛。这主要涉及到对带权连通图的处理，寻找一个边的集合，使得这个集合构成的树连接了所有顶点，同时这些边的权重之和最小。 生成树是图的一个子集，包含图的所有顶点但没有形成环路。对于任何含有n个顶点的连通图，其生成树必然含有n-1条边。在带权连通图中，可能存在多棵生成树，但它们的权重可能各不相同。最小生成树则是所有可能的生成树中边权重总和最小的那一棵。 解决最小生成树问题有多种算法，其中包括Prim算法和Kruskal算法。Prim算法由Jarník在1930年提出，后来由Prim改进。该算法从一个初始顶点开始，逐步扩展生成树，每次都选择当前未被包含在生成树中且与已包含顶点相连的边中权重最小的一条。这个过程持续到所有顶点都被包含在生成树内为止。Prim算法通常采用优先队列（如二叉堆）来实现，以O(E log V)的时间复杂度完成，其中E是边的数量，V是顶点的数量。 在Prim算法的具体实现中，通常会维护一个表示当前生成树的集合T，以及一个Dist数组，记录每个顶点到T的最短距离。算法开始时，Dist数组被初始化为无穷大，除了起始顶点的距离设为0。之后，每次选取Dist数组中最小的未加入T的顶点，并更新与其相邻的顶点在T之外的Dist值。这个过程不断迭代，直至T包含了所有顶点。 关键在于找到连接T内外顶点的最短边。如果图用邻接矩阵表示，那么查找最短边的时间复杂度将是O(V^2)。但如果使用邻接表，可以显著减少时间复杂度。邻接表只存储与每个顶点直接相连的边，因此在查找和更新最短边时更加高效。 另一经典算法是Kruskal算法，它按边的权重升序排序，然后依次添加边，只要不形成环路。Kruskal算法同样需要O(E log E)或O(E log V)的时间复杂度，取决于排序算法的效率。 最小生成树在实际问题中有着诸多应用，比如网络设计、交通规划、电路板布线等，都是通过求解最小生成树来优化成本或路径。在ACM/ICPC等编程竞赛中，理解和熟练运用最小生成树算法是必不可少的技能之一。