最小生成树prim

最小生成树（Minimum Spanning Tree，简称MST）是一种在连通图中找到最小权重的生成树的算法。Prim算法是一种常用的求解最小生成树的贪心算法。

Prim算法的基本思想是从一个顶点开始，逐步扩展生成树，直到覆盖所有的顶点。具体步骤如下：
1. 选择一个起始顶点作为生成树的根节点。
2. 在剩余的顶点中选择与当前生成树距离最近的顶点，并将其加入生成树中。
3. 更新生成树与剩余顶点之间的距离，如果有更短的路径，则更新。
4. 重复步骤2和步骤3，直到所有顶点都被加入生成树。

Prim算法的关键在于如何选择与当前生成树距离最近的顶点。一种常用的方法是使用优先队列（最小堆）来存储顶点与生成树之间的距离，每次选择距离最小的顶点加入生成树。

Prim算法的时间复杂度为O(ElogV)，其中V为顶点数，E为边数。