prim最小生成树解法

Prim 算法是求解无向连通图的最小生成树的一种贪心算法。它的基本思想是：从图中任选一点作为起点，然后从与该点相邻的边中选取一条权值最小的边，将其与该点形成的子图连接。接着，再从与该子图相邻的边中选取一条权值最小的边，将其加入生成树中。重复此过程，直到所有顶点都被加入生成树为止。

下面是 Prim 算法的伪代码：

1. 初始化：将起点加入生成树中，标记起点已访问

2. 重复以下步骤，直到所有顶点都被加入生成树：

   a. 遍历当前已访问的顶点，找到与其相邻的未访问顶点中权值最小的边

   b. 将选中的顶点和边加入生成树中，标记其为已访问

3. 输出生成树

Prim 算法的实现需要借助数据结构——优先队列。优先队列用于存储当前已访问顶点的相邻未访问顶点，以及它们之间的边。每次从优先队列中选取权值最小的边加入生成树中。这样可以保证每次加入的边都是目前为止权值最小的边，从而得到最小生成树。

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