文章作者：甘航 文章来源：http://www.cnblogs.com/ganhang-acm/转载请注明，谢谢合作。
由于数据结构老师布置的一道题 ，我看prim算法看了半天还是一知半解。
在浏览过n多大神博客后半copy半自动补脑完成了这道渣渣题。、、
题目就是从老师给的两个文件中读取数据求最小生成树。
第一个城市文件
北京 , 上海 , 天津 , 石家庄 , 太原 , 呼和浩特 , 沈阳 , 长春 ,哈尔滨 ,
济南 , 南京 , 合肥 , 杭州 , 南昌 , 福州 , 台北 , 郑州 , 武汉 ,
长沙 , 广州 , 海口 , 南宁 , 西安 , 银川 , 兰州 , 西宁 ,
乌鲁木齐 , 成都 , 贵阳 , 昆明 , 拉萨 , * -,
city.txt
第二个各城市之间距离文件
distance.txt
要求是根据这两个文件数据 求个城市最小生成树；
下面给出具体代码
代码的注释我写得很详细，方便理解，有几点需要说明一下。
1、2个for循环都是从1开始的，因为一般我们默认开始就把第0个节点加入生成树，因此之后不需要再次寻找它。
2、lowcost[i]记录的是以节点i为终点的最小边权值。初始化时因为默认把第0个节点加入生成树，因此lowcost[i] = graph[0][i]，即最小边权值就是各节点到0号节点的边权值。
3、mst[i]记录的是lowcost[i]对应的起点，这样有起点，有终点，即可唯一确定一条边了。初始化时mst[i] = 0，即每条边都是从0号节点出发。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define inf 1<<30
#define node_num 31// 图的节点数
struct node
{
char s[];//存城市名字
int id;//这个可以不要，可以用c的下标表示
} c[node_num];
int G[node_num][node_num];//图的矩阵表示
int Prim()
{
int lowcost[node_num];/* lowcost[i]记录以i为终点的边的最小权值，当lowcost[i]=0时表示终点i加入生成树 */
int mst[node_num];/* mst[i]记录对应lowcost[i]的起点，当mst[i]=0时表示起点i加入生成树 */
int i,j,min,minid,sum=; for(i=; i<node_num; i++)/* 默认选择0号节点加入生成树，从1号节点开始初始化 */
{
lowcost[i]=G[][i];/* 最短距离初始化为其他节点到0号节点的距离 */
mst[i]=;/* 标记所有节点的起点皆为默认的0号节点 */
}
mst[]=;/* 标记0号节点加入生成树 */
for(i=; i<node_num; i++)/* n个节点至少需要n-1条边构成最小生成树 */
{
min=inf;
minid=;
for(j=; j<node_num; j++)/* 找满足条件的最小权值边的节点minid */
{
if(lowcost[j]<min&&lowcost[j]!=)/* 边权值较小且不在生成树中 */
{
min=lowcost[j];
minid=j;
}
}
printf("%s -- %s: %d\n",c[mst[minid]].s,c[minid].s,min);/* 输出生成树边的信息:起点，终点，权值 */ sum+=min;/* 累加权值 */ lowcost[minid]=;/* 标记节点minid加入生成树 */
for(j=; j<node_num; j++)/* 更新当前节点minid到其他节点的权值 */
{
if(G[minid][j]<lowcost[j])/* 发现更小的权值 */
{
lowcost[j]=G[minid][j];/* 更新权值信息 */
mst[j]=minid;/* 更新最小权值边的起点 */
}
}
}
return sum;/* 返回最小权值和 */
}
int main()
{
int i,j,w;
for(i=; i<node_num; i++)
for(j=; j<node_num; j++)
{
G[i][j]=G[j][i]=inf;/* 初始化图，所有节点间距离为无穷大 */
}
//读取城市信息
freopen("city.txt","r",stdin);
for(i=; i<node_num; i++)
{
scanf("%s",c[i].s);
scanf("%d,",&c[i].id);
}
//读取各城市之间的距离(权值)
freopen("distance.txt","r",stdin);
for(i=; i<node_num; i++)
for(j=; j<=i; j++)
{
scanf("%d",&w);
if(w!=)
G[i][j]=G[j][i]=w;
} int sum=Prim();//求最小生成树
printf("总长度：%d",sum);//输出最小权值和
return ;
}
Prim_v1.1
