| 发表于：2007-06-12 13:25:16 楼主 |
#include <stdio.h>
#include <stdlib.h>
#define maxlen 10
#define large 999
#define null 0
typedef struct
{ int a[maxlen],b[maxlen],w[maxlen];
char vexs[maxlen];
int vexnum,arcnum;
int arcs[maxlen][maxlen];
}graph;
graph g;
void print_graph（graph g)
{
int i,j;
printf（ "邻接矩阵:\n ");
printf（ "vertex\t ");
for（i=0;i <g.vexnum;i++)
printf（ "%4c ",g.vexs[i]);
printf（ "\n ");
for（i=0;i <g.vexnum;i++)
{
printf（ "%4c\t ",g.vexs[i]);
for（j=0;j <g.vexnum;j++)
printf（ "%4d ",g.arcs[i][j]);
printf（ "\n ");
}
}
graph cre_grah（graph g)
{
int i,j,k,c=999;
for（i=0;i <g.vexnum;i++)
for（j=0;j <g.vexnum;j++)
g.arcs[i][j]=c;
for（k=0;k <g.arcnum;k++)
{
g.arcs[g.a[k]][g.b[k]]=g.w[k];
g.arcs[g.b[k]][g.a[k]]=g.w[k];
}
print_graph（g);
return g;
}
void prim（graph g)
{ int i,j,k,min;
int lowcost[maxlen];
int closet[maxlen];
printf（ "最小生成树的边为：\n ");
for（i=1;i <g.vexnum;i++)
{
lowcost[i]=g.arcs[0][i];
closet[i]=1;
}
closet[1]=0;
j=1;
for（i=1;i <g.vexnum;i++)
{
min=lowcost[j];
k=i;
for（j=1;j <g.vexnum;j++)
if（lowcost[j] <min&&closet[j]!=0)
{ min=lowcost[j];
k=j;}
printf（ "（%c,%c), ",g.vexs[closet[k]],g.vexs[k]);
closet[k]=0;
for（j=1;j <g.vexnum;j++)
if（g.arcs[k][j] <lowcost[j]&&closet[j]!=0)
{ lowcost[j]=g.arcs[k][j];
closet [j]=k;
}
}
}
void main（)
{int i,j,k;
system（ "cls ");
printf（ "请输入城市的个数，城市间道路的条数： ");
scanf（ "%d,%d ",&i,&j);
g.vexnum=i;
g.arcnum=j;
for（i=0;i <g.vexnum;i++)
{
getchar（);
printf（ "\n 第%d个顶点的信息： ",i+1);
g.vexs[i]=getchar（);
}
for（k=0;k <g.arcnum;k++)
{
printf（ "\t 请输入第%d条边的起点： ",k);
scanf（ "%d ",&g.a[k]);
printf（ "\n 请输入第%d条边的终点： ",k);
scanf（ "%d ",&g.b[k]);
printf（ "\n 请输入第%d条边的权值： ",k);
scanf（ "%d ",&g.w[k]);
}
cre_grah（g);
prim（g);
}
|
|
|
|
|
