使用Prim算法构造最小生成树

Prim算法是一种贪心算法，用于构造无向加权图的最小生成树。其基本思想是从一个起始顶点开始，不断寻找与当前生成树相邻的最小边，并将其加入生成树中，直到生成树包含了所有顶点。

具体步骤如下：

1. 选取一个起始顶点，将其加入生成树中。

2. 将与起始顶点相邻的所有边加入一个优先队列中，按照边权从小到大排序。

3. 从优先队列中取出权值最小的边，如果边的另一个端点不在生成树中，则将其加入生成树中，并将与该点相邻的所有边加入优先队列中。

4. 重复步骤3，直到生成树包含了所有顶点。

下面是一个示例：

给定以下无向加权图：

     5
  (0)---(1)
   | \   |
  6|  8\ |7
   |    \|
  (2)---(3)
     9

从顶点0开始构造最小生成树：

1. 将顶点0加入生成树中。

2. 将与顶点0相邻的所有边加入优先队列中，得到 (0, 1, 5), (0, 2, 6), (0, 3, 9)。

3. 取出权值最小的边 (0, 1, 5)，将顶点1加入生成树中，并将与顶点1相邻的所有边加入优先队列中，得到 (1, 3, 7), (1, 0, 5)。

4. 取出权值最小的边 (1, 0, 5)，由于顶点0已经在生成树中，跳过这条边。

5. 取出权值最小的边 (1, 3, 7)，将顶点3加入生成树中，并将与顶点3相邻的所有边加入优先队列中，得到 (3, 2, 9), (3, 1, 7), (3, 0, 9)。

6. 取出权值最小的边 (3, 1, 7)，由于顶点1已经在生成树中，跳过这条边。

7. 取出权值最小的边 (3, 2, 9)，将顶点2加入生成树中。

8. 由于生成树已经包含了所有顶点，算法结束，得到最小生成树 {(0, 1, 5), (1, 3, 7), (3, 2, 9)}。

最小生成树的权值为5+7+9=21