普里姆算法：构建加权连通图最小生成树

数据结构之最小生成树Prim算法是一种经典的图论算法，用于在加权连通图中找到一棵权值和最小的树，即最小生成树。该算法由罗恩·普里姆（Ronald Prim）提出，其核心思想是逐步构建最小生成树，通过迭代的方式选择每一步添加到最小生成树中的节点和连接这些节点的边。 算法的基本步骤如下： 1. 初始阶段： - 选择图G的一个顶点作为起点，通常是任意一个。 - 初始化两个集合：U代表已加入最小生成树的顶点，T存储边，开始时U中只有一个起点。 2. 增长阶段： - 对于每个不在U中的顶点v，计算它到U中所有顶点的边的权重。 - 选择具有最小权重的边(u, v)，其中u在U中，v不在，将v加入U，并将这条边加入T。 - 更新U和T，重复此过程，直到U包含图G的所有顶点。 3. 终止条件： - 当U等于顶点集V时，算法停止。此时，T中的边构成了图G的最小生成树。 4. 代码实现： - 使用数组或哈希表记录顶点和它们到起点的权重，如`weights[]`数组。 - 在每次迭代中，遍历所有非起点顶点，更新最小权重，找到下一个最小权重的顶点。 - `cPrims[]`数组用于存储最小生成树的顶点顺序，`Prim()`函数中通过`nMinWeightIndex`跟踪最小权重顶点的索引。 普里姆算法的时间复杂度为O((E+V)logV)，其中E是边的数量，V是顶点数量。由于该算法是贪心策略，虽然不能保证全局最优，但在实际应用中效果良好，适用于求解大规模图的最小生成树问题。 在编程实现时，需要注意处理特殊情况，如无连接的情况、权重为负值或零的情况等。通过这些步骤，Prim算法能够在数据结构和算法的框架下，高效地找到加权连通图的最小生成树。