今天看到了贪心算法,于是就用贪心思想实现了改算法,以下为要实现的无向图:
以下为C语言代码:
#include<stdio.h> #include<stdlib.h> #define M 3277 #define maxint 9 int n=9,v=0,sum=0; int c[maxint][maxint]= { M,4,M,M,M,M,2,5,4, 4,M,3,5,M,M,3,M,M, M,3,M,1,M,M,M,M,M, M,5,1,M,5,M,M,M,M, M,M,M,5,M,2,M,1,M, M,M,M,M,2,M,7,3,3, 2,3,M,M,M,7,M,M,M, 5,M,M,M,1,3,M,M,6, 4,M,M,M,M,3,M,6,M, }; void prim() { int lowcost[M]; int closest[M]; int s[M]; int i,k; for(i=1;i<n;i++) { lowcost[i]=c[v][i]; closest[i]=v; s[i]=0; } s[0]=1; for(i=0;i<n;i++) { int min=inf; int j=0; for(k=1;k<=n;k++) { if(!(s[k])&&(lowcost[k]<min)){min=lowcost[k];j=k;} } s[j]=1; for(k=1;k<=n;k++) { if(!(s[k])&&c[j][k]<lowcost[k]) { lowcost[k]=c[j][k]; closest[k]=j; } } } for(i=0;i<n;i++) { sum+=lowcost[i]; } } void main() { prim(); printf("%d",sum); getch(); }
运行结果为:16