1. 问题
设G=(V,E)是无向联通带权图，E中的每一条边（u,v）的权为w(u,v);如果G的一个子图G1是一颗包含G中所有顶点的树，则称G1为G的生成树。生成树上各边权的总和称为该生成树的耗费。在G的所有生成树中，耗费最小的生成树称之为最小生成树。
2. 解析
3. 设计
void Prime(int Vnum, int start){
for(i = 1; i <= Vnum; i++){
lowcost[i] = Vi到Vstart的权值；
visited[i] = -1;//标记点的访问状态，-1为未访问，1为访问过
}
visited[start] = 1;
for(剩下的点){
minWg = 999;
for(j = 0; j <= Vnum; j++){
if(第j个点到已经标记点的集合的距离最小且这个点还没有被标记){
minWg = lowcost[j];
下一个要标记的点 = j;
}
}
visited[下一个要标记的点] = 1;
for(j = 0; j <= Vnum; j++)
{
更新lowcost[],使其存放各个点到已标记点的集合的最短距离；
}
}
}
4. 源码
https://github.com/tangsongbbb/AlgorithmsLearning/blob/master/作业一/1.1.c