prim算法求最小生成树

Prim算法是一种常见的求解最小生成树的算法，它的基本思想是通过不断地选取当前与已选顶点集合相邻的最小边来构造最小生成树。下面是Prim算法的具体步骤：

1. 选取一个起点，将其加入已选顶点集合S，并将与该顶点相邻的边加入边集T。

2. 从边集T中选取一条最小边连接已选顶点集合S和未选顶点集合V-S，将其加入已选边集合T，并将该边连接的顶点加入已选顶点集合S。

3. 重复步骤2，直到已选顶点集合S包含所有顶点为止。

完成以上步骤后，已选边集合T所连接的所有顶点及边就组成了最小生成树。

Prim算法的时间复杂度为O(V^2)，其中V是图中的顶点数。如果使用堆等数据结构来优化选取最小边的过程，时间复杂度可以优化到O(ElogV)，其中E是图中的边数。