普利姆最小生成树算法 c++

普里姆（Prim）算法是一种用于在加权连通无向图中查找最小生成树（MST, Minimum Spanning Tree）的贪心算法。最小生成树是一个子图，它包括图中的所有顶点，并且边的总权重最小。该算法的基本思想是从一个顶点开始，逐步扩展生成树，直到包括所有顶点。

算法步骤

1. 初始化：

   • 从一个起始顶点 u 开始。
   • 初始化一个 closedge 数组，其中 closedge[i] 保存了从生成树到顶点 i 的最小权重的边和对应的生成树中的顶点。
   • 将所有顶点的初始权重设置为无穷大（INF），表示这些顶点还没有连接到生成树。

2. 选择最小权重的边：

   • 在每一步中，从 closedge 数组中选择具有最小权重的边，这条边将连接一个在生成树内的顶点和一个不在生成树内的顶点。
   • 将这个顶点和边加入生成树。

3. 更新 closedge 数组：

   • 以新加入生成树的顶点为基础，更新 closedge 数组中的边权重。如果新加入顶点与其他未加入生成树的顶点之间的边权重小于当前记录的权重，则更新它。

4. 重复步骤2和3：

   • 重复以上步骤，直到所有顶点都被加入生成树。