Question

构造可以使n个城市连接的最小生成树

(是数据结构实验，要求C语言编写）
[问题]给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。
[要求]城市间的距离网采用邻接矩阵表示，若两个城市之间不存在道路，则将相应的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。
[输入]表示城市间距离网的邻接矩阵（要求至少6个城市，10条边）
[输出]最小生成树中包括的边及其权值，并显示得到的最小生成树的代价。

Answer 1

/*普里姆算法构造最小生成树*/
#define MAXVEX 30
#define MAXCOST 1000
void prim(int c[MAXVEX][MAXVEX],int n)
/*己知图的顶点为{1,2,...,n},c[i][j]和c[j][i]为边(i,j)的权,打印最小生成树
的每条边*/
{
int i,j,k,min,lowcost[MAXVEX],closest[MAXVEX];;
for (i=2;i<=n;i++) /*从顶点1开始*/
{
lowcost[i]=c[1][i];
closest[i]=1;
}
closest[1]=0;
for (i=2;i<=n;i++) /*从U之外求离U中某一顶点最近的顶点*/
{
min=MAXCOST;
j=1;k=i;
while (j<=n)
{
if (lowcost[j]<min && closest[j]!=0)
{
min=lowcost[j];
k=j;
}
j++;
}
printf("(%d,%d) ",closest[k],k); /*打印边*/
closest[k]=0; /*k加入到U中*/
for (j=2;j<=n;j++)
if (closest[j]!=0 && c[k][j]<lowcost[j])
{
lowcost[j]=c[k][j];
closest[j]=k;
}
}
}
main()
{
int n=7,i,j,mx[MAXVEX][MAXVEX];
for (i=0;i<=n;i++)
for (j=0;j<=n;j++)
mx[i][j]=MAXCOST;
mx[1][2]=50;
mx[1][3]=60;
mx[2][4]=65;
mx[2][5]=40;
mx[3][4]=52;
mx[3][7]=45;
mx[4][5]=50;
mx[5][6]=70;
mx[4][6]=30;
mx[4][7]=42;
printf("最小生成树边集:\n ");
prim(mx,n);
}
数据结构导学上的，
/*克鲁斯卡尔算法构造最小生成树*/
#define MAXEDGE 30 /*MAXEDGE为最大的边数*/
struct edges /*边集类型,存储一条边的起始顶点bv、终止顶点tv和权w*/
{
int bv,tv,w;
};
typedef struct edges edgeset[MAXEDGE];
int seeks(int set[],int v)
{
int i=v;
while (set[i]>0) i=set[i];
return(i);
}
kruskal(edgeset ge,int n,int e)
/*ge表示的图是按权值从小到大排列的*/
{
int set[MAXEDGE],v1,v2,i,j;
for (i=1;i<=n;i++) set[i]=0; /*给set中的每个元素赋初值*/
i=1; /*i表示待获取的生成树中的边数,初值为1*/
j=1; /*j表示ge中的下标,初值为1*/
while (j<n && i<=e) /*按边权递增顺序,逐边检查该边是否应加入到生成树中*/
{
v1=seeks(set,ge[i].bv); /*确定顶点v所在的连通集*/
v2=seeks(set,ge[i].tv);
if (v1!=v2) /*当v1,v2不在同一顶点集合,确定该边应当选入生成树*/
{
printf("(%d,%d) ",ge[i].bv,ge[i].tv);
set[v1]=v2;
j++;
}
i++;
}
}
main()
{
int n=7,e=10;
edgeset mx;
mx[1].bv=4;mx[1].tv=6;mx[1].w=30;
mx[2].bv=2;mx[2].tv=5;mx[2].w=40;
mx[3].bv=4;mx[3].tv=7;mx[3].w=42;
mx[4].bv=3;mx[4].tv=7;mx[4].w=45;
mx[5].bv=1;mx[5].tv=2;mx[5].w=50;
mx[6].bv=4;mx[6].tv=5;mx[6].w=50;
mx[7].bv=3;mx[7].tv=4;mx[7].w=52;
mx[8].bv=1;mx[8].tv=3;mx[8].w=60;
mx[9].bv=2;mx[9].tv=4;mx[9].w=65;
mx[10].bv=5;mx[10].tv=6;mx[10].w=70;
printf("最小生成树边集:\n ");
kruskal(mx,n,e);
}