#include
#include
#include
#define INFINITY 32768 //
#define MAX_VERTEX_NUM 11 //
typedef struct ArCell
{
int adj; // ， 0-1- ，
}ArCell;
typedef struct // ， 、 、 ，
{
char name[30]; //
int num; //
char introduction[100];//
}VertexDat; //
typedef struct
{
VertexDat vexs[MAX_VERTEX_NUM]; //
ArCell arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//
int vexnum,arcnum; // ，
}MGraph;//
MGraph *G; // ，
/*
， for ， ， ，
*/
MGraph *CreatUDN(MGraph *G)// ，
{
int i,j,k,w;//i,j,k,w
char s[10] = "A";
#if 0
printf(" , :");
scanf("%d%d",&G->vexnum,&G->arcnum); //
printf(" :、 、 :
"); // ， ，
for(i=1;i<=G->vexnum;i++)
{
printf(" :");
scanf("%d",&G->vexs[i].num);
printf(" :");
scanf("%s",G->vexs[i].name);
printf(" :");
scanf("%s",G->vexs[i].introduction);
}
for(i=1;i<=G->vexnum;i++)
for(j=1;j<=G->vexnum;j++)
G->arcs[i][j].adj=INFINITY;
printf(" :
"); // （ ）
for(k=1;k<=G->arcnum;k++)
{
printf(" %d :
",k);
printf(" (i,j):"); //
scanf("%d",&i);
scanf("%d",&j);
printf(" :"); //
scanf("%d",&w);
G->arcs[i][j].adj=w; // G
G->arcs[j][i]=G->arcs[i][j];// ， ，
// 。
}
#else
G->vexnum = 6;
G->arcnum = 14;
for(i=1;i<=G->vexnum;i++)
{
G->vexs[i].num = i;
strcpy(G->vexs[i].name, s);
strcpy(G->vexs[i].introduction, s);
*s += 1;
}
for(i=1;i<=G->vexnum;i++)
for(j=1;j<=G->vexnum;j++)
G->arcs[i][j].adj=INFINITY;
i = 1;j=2;
G->arcs[i][j].adj=1; // G
G->arcs[j][i]=G->arcs[i][j];// ， ，
// 。
i = 2;j=1;
G->arcs[i][j].adj=1; // G
G->arcs[j][i]=G->arcs[i][j];
i = 1;j=3;
G->arcs[i][j].adj=1; // G
G->arcs[j][i]=G->arcs[i][j];
i = 3;j=1;
G->arcs[i][j].adj=1; // G
G->arcs[j][i]=G->arcs[i][j];
i = 2;j=3;
G->arcs[i][j].adj=1; // G
G->arcs[j][i]=G->arcs[i][j];
i = 3;j=2;
G->arcs[i][j].adj=1; // G
G->arcs[j][i]=G->arcs[i][j];
i = 3;j=4;
G->arcs[i][j].adj=1; // G
G->arcs[j][i]=G->arcs[i][j];
i = 4;j=3;
G->arcs[i][j].adj=1; // G
G->arcs[j][i]=G->arcs[i][j];
i = 3;j=5;
G->arcs[i][j].adj=1; // G
G->arcs[j][i]=G->arcs[i][j];
i = 5;j=3;
G->arcs[i][j].adj=1; // G
G->arcs[j][i]=G->arcs[i][j];
i = 4;j=6;
G->arcs[i][j].adj=1; // G
G->arcs[j][i]=G->arcs[i][j];
i = 6;j=4;
G->arcs[i][j].adj=1; // G
G->arcs[j][i]=G->arcs[i][j];
i = 5;j=6;
G->arcs[i][j].adj=1; // G
G->arcs[j][i]=G->arcs[i][j];
i = 6;j=5;
G->arcs[i][j].adj=1; // G
G->arcs[j][i]=G->arcs[i][j];
#endif
printf("\t !
");
return G;
}
/* ( )
1. v0 ： Dist[i]=G->arcs[v0][vi].adj;{vi V-S}
2. vk， Dist[i]=min(Dist[i]|vi V-S)
vk v0
3. vk S
4. v0 V-S vi ： v0 V-S vi Dist[i]
v0 ， S vk， V-S vi ：
Dist[k]+G->arcs[v][w].adj
Dist[k]+G->arcs[v][w].adjarcs[k][i].adj;
n-1 v0
O(n*n).
*/
long int Dist[MAX_VERTEX_NUM]; //
int p[MAX_VERTEX_NUM ][MAX_VERTEX_NUM]; //
void ShortestPath_DIJ(MGraph *G,int v0)// ,v0
{
int v,w,i,min,x; //v,w,i,x ，min
int path[MAX_VERTEX_NUM]; //
for(v=1;v<=G->vexnum;v++)
{
path[v]=0; // v0 v
Dist[v]=G->arcs[v0][v].adj; // D
for(w=1;w<=G->vexnum;w++)
p[v][w]=0; //
if(Dist[v]vexnum;i++) // ， v0 ， S
{
min=INFINITY; // v0
for(w=1;w<=G->vexnum;w++)
if(!path[w]) //w v-s
if(Dist[w]vexnum;w++)
if(!path[w]&&(min+G->arcs[v][w].adjarcs[v][w].adj; // s ，
for(x=1;x<=G->vexnum;x++)
p[w][x]=p[v][x];
p[w][w]=1;
}
}
}//ShortestPath_DIJ end
void output(int sight1,int sight2) //
{
int a,b,c,d,q=0;
a=sight2; /* a */
if(a!=sight1) /* ， ... */
{
printf("
\t %s %s ",G->vexs[sight1].name,G->vexs[sight2].name);/* */
printf("\t( %dm.)
\t",Dist[a]); /* sight1 sight2 ， D[] */
printf("\t%s",G->vexs[sight1].name); /* */
d=sight1; /* d */
for(c=1;c<=MAX_VERTEX_NUM;c++)
{
gate:; /* ， goto */
p[a][sight1]=0;
for(b=1;b<=MAX_VERTEX_NUM;b++)
{
if(G->arcs[d][b].adj%s",G->vexs[b].name); /* */
p[a][b]=0;
d=b; /* b ， */
goto gate;
}
}
}
}
}
int FindInformation(MGraph *G,char a[])//
{
int i;
for(i=1;i<=G->vexnum;i++)
{
if(strcmp(G->vexs[i].name,a)==0)
break;
}
if(i==(G->vexnum+1))
{
return -1;
}
else
return G->vexs[i].num;
}
void Floyd(MGraph *G)
{
int v,u,i,w,k,j=0,flag=1,p[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM],D[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
char A[10],B[10];
for(v=1;v<=G->vexnum;v++)
for(w=1;w<=G->vexnum;w++)
{
D[v][w]=G->arcs[v][w].adj;
for(u=1;u<=G->vexnum;u++)
p[v][w][u]=0;
if(D[v][w]vexnum;u++)
for(v=1;v<=G->vexnum;v++)
for(w=1;w<=G->vexnum;w++)
if(D[v][u]+D[u][w]vexnum;i++)
p[v][w][i]=p[v][u][i]||p[u][w][i];
}
printf("\t :
");
scanf("%s",&A);
k=FindInformation(G,A);
if(k==-1){
printf("\t !
");
return ;
}
printf("\t :
");
scanf("%s",&B);
k=FindInformation(G,B);
if(j==-1){
printf("\t !
");
return ;
}
printf("%s",G->vexs[k].name);
for(u=1;u<=G->vexnum;u++)
if(p[k][j][u]&&k!=u&&j!=u)
printf("-->%s",G->vexs[u].name);
printf("-->%s",G->vexs[j].name);
printf(" %dm
",D[k][j]);
}//Floyd end
int a=0;/* ， */
int visited[MAX_VERTEX_NUM];/* ， */
int v[MAX_VERTEX_NUM];/* ， */
void path(MGraph *G,int i,int j,int k)
/* k+1 */
{int s;
if(v[k]==j)/* */
{
a++;/* 1*/
printf(" %d :",a);
for(s=1;s",G->vexs[v[s]].name);
printf("%s
",G->vexs[v[s]].name);
}
s=1;
while(s<=G->vexnum)
{if(s!=i)/* */
{
if(G->arcs[v[k]][s].adj!=INFINITY&&visited[s]==0)
/* vk vs vs */
{visited[s]=1;/* 1, */
v[k+1]=s;/* s v */
path(G,i,j,k+1);/* */
visited[s]=0;/* 0， ， */
}}
s++;
}
}
void disppath(MGraph *G,int i,int j)
{
int k;
v[1]=i;
for(k=1;k<=G->vexnum;k++)
visited[i]=0;/* ， */
a=0;/* */
path(G,i,j,1);/* path ， vi vj */
}
void SearchAllpath(MGraph *G)/* */
{ int i,j;
char b[10],c[10];
printf(" :");
scanf("%s",&b);
i=FindInformation(G,b);
getchar();
if(i==-1)
{
printf(" !
");
return;
}
printf(" :");
scanf("%s",&c);
j=FindInformation(G,c);
getchar();
if(j==-1)
{
printf(" !
");
return;
}
printf(" %s %s :
",G->vexs[i].name,G->vexs[j].name);/* */
disppath(G,i,j);/* disppath , */
}
char SearchMenu() /* */
{
char c;
int flag;
do{
flag=1;
system("cls");
printf("
\t\t┏━━━━━━━━━━━━━━━┑
");
printf("\t\t\t┃ ┃
");
printf("\t\t\t┃ 1、 ┃
");
printf("\t\t\t┃ 2、 ┃
");
printf("\t\t\t┃ 0、 ┃
");
printf("\t\t\t┃ ┃
");
printf("\t\t\t┗━━━━━━━━━━━━━━━┛
");
printf("\t\t\t\t ：");
scanf("%c",&c);
if(c=='1'||c=='2'||c=='0')
flag=0;
}while(flag);
return c;
}
void search(MGraph *G) /* */
{
int num;
int i;
char c;
char name[20];
do
{
system("cls");
c=SearchMenu();
switch (c)
{
case '1':
system("cls");
printf("
\t\t ：");
scanf("%d",&num);
for(i=1;i<=MAX_VERTEX_NUM;i++)
{
if(num==G->vexs[i].num)
{
printf("┏━━┳━━━━━━━━┳━━━━━━━━━━━━━━━━━━┓
");
printf("┃ ┃ ┃ ┃
");
printf("┃%-4d %-16s┃%-56s┃
",G->vexs[i].num,G->vexs[i].name,G->vexs[i].introduction);
printf("┗━━┻━━━━━━━━┻━━━━━━━━━━━━━━━━━━┛
");
printf("
\t\t\t ...");
getchar();
getchar();
break;
}
}
if(i==MAX_VERTEX_NUM)
{
printf("
\t\t\t ！");
printf("
\t\t\t ...");
getchar();
getchar();
}
break;
case '2':
system("cls");
printf("
\t\t ：");
scanf("%s",&name);
for(i=1;i<=MAX_VERTEX_NUM;i++)
{
if(!strcmp(name,G->vexs[i].name))
{
printf("┏━━┳━━━━━━━━┳━━━━━━━━━━━━━━━━━━━┓
");
printf("┃ ┃ ┃ ┃
");
printf("┃%-4d %-16s┃%-56s┃
",G->vexs[i].num,G->vexs[i].name,G->vexs[i].introduction);
printf("┗━━┻━━━━━━━━┻━━━━━━━━━━━━━━━━━━━┛
");
printf("
\t\t\t ...");
getchar();
getchar();
break;
}
}
if(i==MAX_VERTEX_NUM)
{
printf("
\t\t\t ！");
printf("
\t\t\t ...");
getchar();
getchar();
}
break;
}
}while(c!='0');
}
void Menu()
{
printf("
");
printf(" ┏━━━━━━━━━━━━━━━━━━━━┓
");
printf(" ┃ 1. ┃
");
printf(" ┃ 2. ┃
");
printf(" ┃ 3. ┃
");
printf(" ┃ 4. ┃
");
printf(" ┃ 5. ┃
");
printf(" ┗━━━━━━━━━━━━━━━━━━━━┛
");
printf(" :");
}
void Browser(MGraph *G)
{
int i;
printf("┏━━┳━━━━━━━━┳━━━━━━━━━━━━━━━━━━━┓
");
printf("┃ ┃ ┃ ┃
");
for(i=1;i<=G->vexnum;i++)
printf("┃%-4d┃%-16s┃%-56s┃
",G->vexs[i].num,G->vexs[i].name,G->vexs[i].introduction);
printf("┗━━┻━━━━━━━━┻━━━━━━━━━━━━━━━━━━━┛
");
}
void main(void)
{
int i;
int v0,v1;
G=(MGraph *)malloc(sizeof(MGraph));
G=CreatUDN(G);
Menu();
scanf("%d",&i);
while(i!=5)
{
switch(i)
{
case 1:system("cls");Browser(G);Menu();break;
case 2:system("cls");
printf("
\t\t\t ：");
scanf("%d",&v0);
printf("\t\t\t ：");
scanf("%d",&v1);
ShortestPath_DIJ(G,v0); /* */
output(v0,v1); /* */
Menu();break;
case 3:system("cls");
// Floyd(G);
SearchAllpath(G);
Menu();break;
case 4:system("cls");search(G);Menu();break;
case 5:exit(1);break;
default:break;
}
scanf("%d",&i);
}
}