#include<stdio.h>
#define MAX 10
#define INFINITY 32768
typedef struct st1
{
int adj;
int info;
}ArcNode;
typedef struct st2
{
char ver[MAX];
ArcNode arc[MAX][MAX];
int Arcnum;
int Vernum;
}graph;
typedef struct st3
{
int lowcost;
char adjvex;
}closedge;
void creat(graph *G);
int LocateVertex(graph *G,char v);
void miniSpanTree(graph *);
int local(graph *G,closedge *p);
int main()
{
graph p;
creat(&p);
miniSpanTree(&p);
return 0;
}
void creat(graph *G)
{
int i,j,k,weight;
char v1,v2;
printf("please input number to vernum and arcnum:\n");
scanf("%d%d",&G->Vernum,&G->Arcnum);
getchar();
for(i=0;i<G->Vernum;i++)
{
G->ver[i]=getchar();
}
for(i=0;i<G->Vernum;i++)
{
for(j=0;j<G->Vernum;j++)
{
G->arc[i][j].adj=INFINITY;
}
}
printf("请输入值:\n");
for(k=0;k<G->Arcnum;k++)
{
scanf(" %1c %1c%1d",&v1,&v2,&weight);
i=LocateVertex(G,v1);
j=LocateVertex(G,v2);
G->arc[i][j].adj=weight;
G->arc[j][i].adj=weight;
}
}
int LocateVertex(graph *G,char v)
{
int j=-1,k;
for(k=0;k<G->Vernum;k++)
{
if(G->ver[k]==v)
{
j=k;
break;
}
}
return j;
}
void miniSpanTree(graph *G)
{
closedge close[MAX];
int i,j,k;
char v1,v2;
printf("请输入0到%d之间的整数值：\n",G->Vernum);
scanf("%d",&k);
close[k].lowcost=0;
for(i=0;i<G->Vernum;i++)
{
if(i!=k)
{
close[i].adjvex=G->ver[k];
close[i].lowcost=G->arc[k][i].adj;
}
}
for(j=1;j<G->Vernum;j++)
{
k=local(G,close);
v1=close[k].adjvex;
v2=G->ver[k];
printf("%c%c\n",v1,v2);
close[k].lowcost=0;
for(i=0;i<G->Vernum;i++)
{
if(G->arc[k][i].adj<close[i].lowcost&&close[i].lowcost!=0)
{
close[i].lowcost=G->arc[k][i].adj;
close[i].adjvex=G->ver[k];
}
}
}
}
int local(graph *G,closedge *p)
{
int k,i;
int val=INFINITY;
for(k=0;k<G->Vernum;k++)
{
if(p[k].lowcost!=0&&p[k].lowcost<val)
{
val=p[k].lowcost;
i=k;
}
}
return i;
}
|
|
收藏
淘帖
踩
