问题介绍及算法思想参考
求最小生成树-普里姆算法
最小生成树Prim算法理解
代码实现
#include<stdio.h>
#include <stdlib.h>
#define MAX 100
#define Maxcost 0x7fffffff
int graph[MAX][MAX];
void prim(int graph[][MAX],int n){
int i,j,k;
int lowcost[MAX];
int closeset[MAX],used[MAX];
int mmin;
int sumcost=0;
printf("最小生成树的边为:\n");
for(i=1;i<=n;i++){
lowcost[i]=graph[1][i];
//printf("lowcost[%d]=%d\n",i,lowcost[i]);
closeset[i]=1;
used[i]=0;
}
used[1]=1;
for(i=2;i<=n;i++){
j=1;
mmin=Maxcost;
for(k=2;k<=n;k++){
if((!used[k])&&(lowcost[k]<mmin)){
mmin=lowcost[k];
j=k;
}
}
printf("%d %d\n",j,closeset[j]);
sumcost+=graph[j][closeset[j]];
used[j]=1;
for(k=2;k<=n;k++){
if(!used[k]&&(graph[j][k]<lowcost[k])){
lowcost[k]=graph[j][k];
closeset[k]=j;
}
//printf("lowcost[%d]=%d\n",k,lowcost[k]);
}
}
printf("最小造价为:%d\n",sumcost);
}
int main(){
FILE *fr;
int s,e;
int i,j,weight;
fr=fopen("input.txt","r");
if(!fr){
printf("openning file failed!\n");
exit(1);
}
fscanf(fr,"%d %d",&s,&e);
printf("共%d个点 %d条边\n",s,e);
for(i=0; i<=e; i++)
for(j=0; j<=e; j++)
graph[i][j] = Maxcost;
while(e--){
fscanf(fr,"%d%d%d",&i,&j,&weight);
printf("%d %d %d\n",i,j,weight);
graph[i][j]=weight;
graph[j][i]=weight;
}
prim(graph,s);
return 0;
}
input
6 10
1 2 6
1 3 1
1 4 5
2 3 5
2 5 3
3 4 5
3 5 6
3 6 4
4 6 2
5 6 6
output