1.问题
在一个连通无向图G=(V, E)中，对于其中的每条边(u,v)∈E，赋予其权重w(u, v)，若存在 T 为 E 的子集（即）且为无循环图，使得的 w(T) 最小，则此 T 为 G 的最小生成树。
2.解析
以上图为例具体计算步骤如下：
①图中有6个顶点，任意选择一个顶点作为起始点，一般都选择v1作为起始点。现在我们设集合U为当前所找到最小生成树的顶点，TE集合为边，则：U={v1}； TE={}；
②现在找一个顶点在U，另一个顶点在V-U中的最小权值，即在边v1v2、v1v3、v1v4中找最小值。通过图中可知，边v1v3的权值最小，为1，则将顶点v3加入到集合U，（v1，v3）加入到TE，状态如下：U={v1，v3}； TE={（v1，v3）}；
③继续寻找，即在边v1v2、v1v4、v2v3、v3v4、v3v5、v3v6中招最小值。通过图中可知，边v3v6的权值最小，为4，则将顶点v6加入到集合U，（v3，v6）加入到TE，状态如下：U={v1，v3，v6}； TE={（v1，v3），（v3，v6）}；
④如此循环一下直到找到所有顶点为止。
下图展示了生成最小生成树的全过程：
3.设计
在构造过程中，设置了两个辅助数组：lowcost[]存放生成树顶点集合U内顶点到生成树外V-U各顶点的各边上的当前最小权值；nearvex[]记录生成树顶点集合外各顶点距离集合内哪个顶点最近（即权值最小）.
void Prim(MGraph &G,MST &T,int u)
{
int i,j;
int *lowcost=new int[G.n];
int *nearvex=new int[G.n];
for(i=0;i<G.n;i++)
{
lowcost[i]=G.edges[u][i]; //u到各点的代价
nearvex[i]=u; //最短带权路径
}
nearvex[u]=-1; //加入到生成树顶点集合
int k=0;
for(i=0;i<G.n;i++)
if(i!=u)
{
int min=MaxValue;
int v=u;
for(j=0;j<G.n;j++)
if(nearvex[j]!=-1 && lowcost[j]<min) //等于-1时不参选
{
v=j;
min=lowcost[j]; //求生成树外顶点到生成树内顶点具有最小权值的边
//v是当前具有最小权值的边
}
if(v!=u)
{
T[k].tail=nearvex[v];
T[k].head=v;
T[k++].cost=lowcost[v];
nearvex[v]=-1; //该边加入生成树标记
for(j=0;j<G.n;j++)
if(nearvex[j]!=-1 && G.edges[v][j]<lowcost[j])
{
lowcost[j]=G.edges[v][j]; //修改
nearvex[j]=v;
}
}
} //循环n-1次，加入n-1条边
}4.源码
https://github.com/Wang-2333/Prim/blob/master/Prim/Prim.cpp