贪心算法设计实验报告(2)

**************************************************************************************/

void Prim(int **Graph,int num_v)//转化为对上三角的维护 { int i,j,leap=0,temp; int m,n,min;

int *a=(int *)malloc(sizeof(int)*num_v); for(i=0;i<num_v;i++)

a[i]=0;

a[0]=1;

while(leap!=num_v-1) { min=INF;

for(i=0;i<num_v;i++)//搜索上三角中的最小值 { if(a[i]==1) { for(j=i+1;j<num_v;j++)//行中搜索 { if(min>Graph[i][j]&&Graph[i][j]>0) { min=Graph[i][j]; m=j; n=i; temp=0;

}

}

for(j=0;j<i;j++)//列中搜索 { if(min>Graph[j][i]&&Graph[j][i]>0) {

min=Graph[j][i];

/* for(i=0;i<num_v;i++)//检查矩阵中在那些行（列）可以选择最小值（即那些列和行是候选行和列）

printf("%-4d",a[i]);

}

}

}

}

m=j; n=i; temp=1;

if(temp==0)//为了区别出是在行还是在列中搜索到的元素 else

Graph[m][n]=-1; Graph[n][m]=-1;

for(i=0;i<m;i++)//去掉行中回路边 { }

for(i=m+1;i<num_v;i++)//去掉列中回路边 { } a[m]=1;

if(a[i]==1&&Graph[m][i]>0) { }

Graph[m][i]=INF; if(a[i]==1&&Graph[i][m]>0) { }

Graph[i][m]=INF;

printf("\n");*/

/* for(i=0;i<num_v;i++)//检验对上三角的维护，和下三角是否修改了（下三角保存了原树和用于输出最小生成树） }

void main() {

Graph=(int**)malloc(sizeof(int*)*num_v);//动态生成二维数组用来存储图（邻接矩阵） for(i=0;i<num_v;i++)

for(i=0;i<num_v;i++)//初始化矩阵

for(j=0;j<num_v;j++)

}

{ }*/ leap++;

for(j=0;j<num_v;j++)

printf("%-4d\t",Graph[i][j]);

printf("\n");

int i,j;

int num_v,num_e; int **Graph=NULL; char *V=NULL; char ch_1,ch_2; int weight; int m,n;

printf("请输入图的顶点数："); scanf("%d",&num_v);

V=(char*)malloc(sizeof(char)*num_v);

Graph[i]=(int*)malloc(sizeof(int)*num_v);

Graph[i][j]=INF;

for(i=0;i<num_v;i++)

Graph[i][i]=0;

for(i=0;i<num_v;i++) { printf("请输入第%d个顶点:",i+1); scanf(" %c",&V[i]); }

printf("请输入图的边数："); scanf("%d",&num_e); for(i=0;i<num_e;i++) { printf("请输入第%d条边的顶点和权值:",i+1); scanf(" %c %c%d",&ch_1,&ch_2,&weight); for(j=0;j<num_v;j++) { if(V[j]==ch_1)

m=j;

if(V[j]==ch_2)

n=j;

}

Graph[m][n]=weight; Graph[n][m]=weight;

}

//以上是对图用邻接矩阵存储

//------------------------------------------------------------------------------------ Prim(Graph,num_v);

printf("最小生成树如下：\n");

}

printf("顶点----------------顶点-----------------权值\n"); weight=0;

for(i=0;i<num_v;i++)

for(j=i+1;j<num_v;j++) { }

if(Graph[i][j]==-1) { }

printf(" %-2c ---------------- %-2c ----------------- %-2d\n",V[i],V[j],Graph[j][i]); weight=weight+Graph[j][i];

printf("最小生成树的权重是：%d\n",weight);

六、实验结果与分析

Kruskal算法适用于边稀疏的情形，而Prim算法适用于边稠密的情形