#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MaxVertexNum 25
#define INF 32767
typedef int EdgeType;
typedef struct
{
char citys[MaxVertexNum][10];
EdgeType edges[MaxVertexNum][MaxVertexNum];
int n,e;
}MGraph;
int CityID(MGraph *G,char CityName[])
{
int i;
for(i=0;i<G->n;i++)
{
if(strcmp(CityName,G->citys[i])==0)
break;
}
if(i==G->n)
return -1;
else
return i;
}
void CreatMGraph(MGraph *G)
{
int i,j,k,l;
char t[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[i],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;
}
typedef struct
{
int adjvex;
int lowcost;
}Closedge;
void Prim(MGraph*G,int v)
{
int k,i,j,minCost;
Closedge closedge[MaxVertexNum];
closedge[v].lowcost=0;
for(j=0;j<G->n;j++)
{
closedge[j].adjvex=v;
closedge[j].lowcost=G->edges[v][j];
}
for(i=1;i<G->n;i++)
{
for(j=0;j<G->n;j++)
if(closedge[j].lowcost!=0)
{
k=j;
break;
}
minCost=closedge[k].lowcost;
for(j=0;j<G->n;j++)
if(closedge[j].lowcost<minCost&&closedge[j].lowcost!=0)
{
minCost=closedge[j].lowcost;
k=j;
}
printf("(%s,%s)\n",G->citys[closedge[k].adjvex],
G->citys[k]);
closedge[k].lowcost=0;
for(j=0;j<G->n;j++)
{
if(G->edges[k][j]<closedge[j].lowcost)
{
closedge[j].adjvex=k;
closedge[j].lowcost=G->edges[k][j];
}
}
getchar();
}
}
void dispath(MGraph*G,int dist[],int path[],int s[],int v)
{
int i,k;
for(i=0;i<G->n;i++)
if(s[i]==1)
{k=i;
printf("\n%s到%s的最短路徑為:",G->citys[v],G->citys[i]);
while(k!=v)
{printf("%s<-",G->citys[k]);
k=path[k];
}
printf("%s需要經過的站點數目為：%d\n",G->citys[v],dist[i]);
}
else
printf("%s<-%s不存在路徑\n",G->citys[i],G->citys[v]);
}
void dijkstra(MGraph*G,int v)
{
int dist[MaxVertexNum],path[MaxVertexNum];
int s[MaxVertexNum];
int mindis;
int i,j,k;
for(i=0;i<G->n;i++)
{
dist[i]=G->edges[v][i];
s[i]=0;
if(G->edges[v][i]<32767)
path[i]=v;
else
path[i]=-1;
}
s[v]=1;
for(i=0;i<G->n;i++)
{
mindis=INF;
k=v;
for(j=0;j<G->n;j++)
{
if(s[j]==0&&dist[j]<mindis)
{
k=j;
mindis=dist[j];
}
}
s[k]=1;
for(j=0;j<G->n;j++)
{
if(s[j]==0&&G->edges[k][j]<32767&&dist[k]+G->edges[k][j]<dist[j])
{
dist[j]=dist[k]+G->edges[k][j];
path[j]=k;
}
}
}
dispath(G,dist,path,s,v);
}
void consult(MGraph*G)
{
char c[10];
int i;
printf("\n請輸入出發站點：");
scanf("%s",c);
i=CityID(G,c);
if(-1==i)
{
printf("\n找不到此站點！");
getchar();
return;
}
dijkstra(G,i);
getchar();
}
int menu()
{
int n;
char c;
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(n<0||n>3)
printf("\t\t\t輸入選項錯誤！請重新輸入選項");
}while(n<0||n>3);
return n;
}
int main()
{
int select,i,j;
char c[10];
MGraph*G;
G=(MGraph*)malloc(sizeof(MGraph));
G->n=0;
G->e=0;
for(i=0;i<MaxVertexNum;i++)
for(j=0;j<MaxVertexNum;j++)
if(i!=j)
G->edges[i][j]=INF;
else
G->edges[i][j]=0;
do
{
system("cls");
select=menu();
switch(select)
{
case 1:CreatMGraph(G);break;
case 2:Prim(G,0);break;
case 3:consult(G);break;
case 0:printf("\n\n\n\t\t\t謝謝使用！再見。。。\n");
getchar();
exit(0);
}
getchar();
}while(select!=0);
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/195491.html
標籤：C語言