使用prim算法求带权无向图的最小生成树

Prim算法是一种贪心算法，用于求带权无向图的最小生成树。其基本思想是从一个顶点开始，不断将与当前最小生成树相邻的边加入最小生成树，直到所有顶点都被加入为止。具体实现步骤如下：

1. 随机选择一个顶点作为起点，将其加入最小生成树中。

2. 找到与当前最小生成树相邻的边中权值最小的边，将其加入最小生成树中。

3. 重复步骤2，直到所有顶点都被加入最小生成树为止。

下面是Prim算法的伪代码：

MST-Prim(G, w, r)
1 for each u in V[G]
2     do key[u] ← ∞
3        π[u] ← NIL
4 key[r] ← 0
5 Q ← V[G]
6 while Q ≠ ∅
7     do u ← EXTRACT-MIN(Q)
8        for each v in Adj[u]
9            do if v ∈ Q and w(u, v) < key[v]
10                  then π[v] ← u
11                       key[v] ← w(u, v)
12 return T = {(π[v],v): v ∈ V[G] - {r}}

其中，G表示带权无向图，w表示边权值函数，r表示起始顶点，key表示每个顶点到最小生成树的距离，π表示每个顶点的父节点，Q表示未加入最小生成树的顶点集合，EXTRACT-MIN(Q)表示从Q中取出key值最小的顶点。最终返回的T即为最小生成树。

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