#include
#include
#include
#defineMaxVertexNum25
#defineINF32767
typedefintEdgeType;
typedefstruct
{
charcitys[MaxVertexNum][10];
EdgeTypeedges[MaxVertexNum][MaxVertexNum];
intn,e;
}MGraph;
intCityID(MGraph*G,charCityName[])
{
inti;
for(i=0;in;i++)
{
if(strcmp(CityName,G->citys)==0)
break;
}
if(i==G->n)
return-1;
else
returni;
}
voidCreatMGraph(MGraph*G)
{
inti,j,k,l;
chart[10],m[10];
printf("\n请输入地铁信息，输入q退出：\n");
for(i=0;;i++)
{
printf("\n地铁站点名称%d:",i);
scanf("%s",t);
if(strcmp(t,"q")==0)
break;
if(CityID(G,t)>=0)
{
printf("\n已有此站点！\n");
i--;
continue;
}
strcpy(G->citys,t);
G->n=i+1;
}
printf("\n请输入地铁路线的信息，输入q退出：\n");
for(i=0;;i++)
{
printf("\n起始站点：");
scanf("%s",t);
if(strcmp(t,"q")==0)
break;
printf("终止站点：");
scanf("%s",m);
if(strcmp(m,"q")==0)
break;
printf("站点距离：");
scanf("%d",&l);
if(strcmp(t,"q")==0)
break;
j=CityID(G,t);
k=CityID(G,m);
if(-1==j||-1==k)
{
printf("\n站点名称输入有误！\n");
continue;
}
G->edges[j][k]=1;
G->edges[k][j]=1;
}
G->e=i;
}
typedefstruct
{
intadjvex;
intlowcost;
}Closedge;
voidPrim(MGraph*G,intv)
{
intk,i,j,minCost;
Closedgeclosedge[MaxVertexNum];
closedge[v].lowcost=0;
for(j=0;jn;j++)
{
closedge[j].adjvex=v;
closedge[j].lowcost=G->edges[v][j];
}
for(i=1;in;i++)
{
for(j=0;jn;j++)
if(closedge[j].lowcost!=0)
{
k=j;
break;
}
minCost=closedge[k].lowcost;
for(j=0;jn;j++)
if(closedge[j].lowcostcitys[closedge[k].adjvex],
G->citys[k]);
closedge[k].lowcost=0;
for(j=0;jn;j++)
{
if(G->edges[k][j]edges[k][j];
}
}
getchar();
}
}
voiddispath(MGraph*G,intdist[],intpath[],ints[],intv)
{
inti,k;
for(i=0;in;i++)
if(s==1)
{k=i;
printf("\n%s到%s的最短路径为:",G->citys[v],G->citys);
while(k!=v)
{printf("%scitys[k]);
k=path[k];
}
printf("%s需要经过的站点数目为：%d\n",G->citys[v],dist);
}
else
printf("%scitys,G->citys[v]);
}
voiddijkstra(MGraph*G,intv)
{
intdist[MaxVertexNum],path[MaxVertexNum];
ints[MaxVertexNum];
intmindis;
inti,j,k;
for(i=0;in;i++)
{
dist=G->edges[v];
s=0;
if(G->edges[v]n;i++)
{
mindis=INF;
k=v;
for(j=0;jn;j++)
{
if(s[j]==0&&dist[j]n;j++)
{
if(s[j]==0&&G->edges[k][j]edges[k][j]edges[k][j];
path[j]=k;
}
}
}
dispath(G,dist,path,s,v);
}
voidconsult(MGraph*G)
{
charc[10];
inti;
printf("\n请输入出发站点：");
scanf("%s",c);
i=CityID(G,c);
if(-1==i)
{
printf("\n找不到此站点！");
getchar();
return;
}
dijkstra(G,i);
getchar();
}
intmenu()
{
intn;
charc;
printf("\n\n\t\t城市地铁交通系统：\n");
printf("\n\t\t\t1建立城市地铁交通图");
printf("\n\t\t\t2所有站点的最小生成树");
printf("\n\t\t\t3地铁站点咨询");
printf("\n\t\t\t0退出");
do
{
fflush(stdin);
printf("\n\n\t\t请输入0~3选择功能：");
c=getchar();
n=c-48;
if(n3)
printf("\t\t\t输入选项错误！请重新输入选项");
}while(n3);
returnn;
}
intmain()
{
intselect,i,j;
charc[10];
MGraph*G;
G=(MGraph*)malloc(sizeof(MGraph));
G->n=0;
G->e=0;
for(i=0;iedges[j]=INF;
else
G->edges[j]=0;
do
{
system("cls");
select=menu();
switch(select)
{
case1:CreatMGraph(G);break;
case2:Prim(G,0);break;
case3:consult(G);break;
case0:printf("\n\n\n\t\t\t谢谢使用！再见。。。\n");
getchar();
exit(0);
}
getchar();
}while(select!=0);
}
分 --> |
