实验 1 贪心算法实现最小生成树
实验一 用贪心算法实现最小生成树问题
一．实验目的
1.熟悉贪心算法的基本原理和使用范围。
二．实验内容及要求
内容：任选一种贪心算法（prim或Kruskal），求解最小生成树。对算法进行编程。
要求：使用贪心算法编程，求解最小生成树问题
三．程序列表
（1）prim算法
#include
#define INF 32766
#define max 40
void prim(int g[][max],int n)
{
int lowcost[max],closest[max];
int i,j,k,min;
for(i=2;i
{
lowcost[i]=g[1][i];
closest[i]=1;
}
lowcost[1]=0;
for(i=2;i
{
min=INF;
k=0;
for(j=2;j
{
if((lowcost[j]
{
min=lowcost[j];
k=j;
}
}
printf("(%d,%d)%d\t",closest[k],k,min);
lowcost[k]=0;
for(j=2;j
{
if(g[k][j]
{
lowcost[j]=g[k][j];
closest[j]=k;
}
}
printf("\n");
}
}
int adj(int g[][max])
{
int n,i,j,v1,v2,weight,m;
printf("输入顶点数 n=:");
scanf("%d",&n);
for(i=1;i
for(j=1;j
g[i][j]=INF;
while(v1!=0&&v2!=0&&weight!=0)//只要输入0 0 0就结束 {
printf("v1,v2,weight=");
scanf("%d %d %d",&v1,&v2,&weight);
g[v1][v2]=weight;
g[v2][v1]=weight;
}
return(n);
}
void prg(int g[][max],int n)
{
int i,j;
for(i=0;i
printf("%d\t",i);
for(i=1;i
{
printf("\n%d\t",i);
for(j=1;j
printf((g[i][j]==INF)?"\t":"%d\t",g[i][j]); }
printf("\n");
}
void main()
{
int g[max][max],n,i;
} n=adj(g); printf("输出无向图的邻接矩阵:\n"); prg(g,n); printf("输出最小生成树:\n"); prim(g,n);
四．实验结果