graph.cpp

来自「图的应用-铁路最短路径的源码以及实验报告！」· C++ 代码 · 共 228 行

#include <string.h>
#include <stdio.h>
#include <stdlib.h>

#define INFINITY 10000
#define MAX_VERTAX_NUM 100
#define FALSE 0
#define TRUE 1
#define NULL 0

typedef struct ArcCell{
	int adj;		/*相邻接的城市路径长度*/
}ArcCell;			/*定义边的类型*/
 
typedef struct VertexType{
	int number;			/*城市序号*/
	char city[20];		/*城市名称*/
}VertexType;			/*顶点类型*/

typedef struct MGraph{
    VertexType vexs[MAX_VERTAX_NUM];		/*图中的顶点，即为城市*/
    ArcCell arcs[MAX_VERTAX_NUM][MAX_VERTAX_NUM];		/*图中的边，即为城市间的距离*/
    int vexnum,arcnum;		/*顶点数，边数*/
}MGraph;		/*定义图的类型*/

//函数定义
void Save(char filename[10],MGraph G);
int LocateVex(MGraph G,char u[20]);
void CreateUDN();
void Save(char filename[10],MGraph G);
void ShortestPath(int v0);
void displaycity();

//全局变量
MGraph G; 
int P[MAX_VERTAX_NUM][MAX_VERTAX_NUM];
long D[MAX_VERTAX_NUM];

void CreateUDN()		//造图函数
{
	char v1[20],v2[20],c;
	int i,j,w;
	printf("请输入城市数:");
	scanf("%d",&G.vexnum);
	printf("\n");
	printf("请输入%d个城市:\n",G.vexnum);
	for(i=0;i<G.vexnum;i++)
	{
		scanf("%s",G.vexs[i].city);
		G.vexs[i].number=i;
	}
	for(i=0;i<G.vexnum;i++)
		for(j=0;j<G.vexnum;j++)
			G.arcs[i][j].adj=INFINITY;
q:		printf("输入要添加路线的两城市名:\n");
		scanf("%s",v1);
		scanf("%s",v2);
		i=LocateVex(G,v1);
		j=LocateVex(G,v2);
		printf("输入%s和%s之间的长度",v1,v2);
		scanf("%d",&w);
		G.arcs[j][i].adj=G.arcs[i][j].adj=w;
		G.arcnum++;
		printf("继续添加?(y\\n)");
		scanf("%c",&c);
		if(getchar()=='y')
			goto q;
 }

void displaycity()			//显示城市
{
	int i,k=0;
	printf("\n****************城市列表如下**************\n\n");
	for(i=0;i<G.vexnum;i++)
	{
		printf("(%2d)%-15s",i,G.vexs[i].city);		//输出城市列表
		if(++k%4==0) printf("\n");
	}
}
 
void ShortestPath(int v0)		//最短路径函数
{
	int v,w,i,t;
	int final[MAX_VERTAX_NUM];
	int min;
	for(v=0;v<G.vexnum;++v)
	{
		final[v]=FALSE;
		D[v]=G.arcs[v0][v].adj;
        for(w=0;w<G.vexnum;++w)
			P[v][w]=FALSE;
        if(D[v]<INFINITY)
		{
			P[v][v0]=TRUE;
			P[v][v]=TRUE;
		}
    }
    D[v0]=0;final[v0]=TRUE;
    for(i=1;i<G.vexnum;++i)//error
    {
        min=INFINITY;
        for(w=0;w<G.vexnum;++w)
            if(!final[w])
                if(D[w]<min){v=w;min=D[w];}
        final[v]=TRUE;
        for(w=0;w<G.vexnum;++w)
            if(!final[w]&&((min+G.arcs[v][w].adj)<D[w]))
			{
				D[w]=min+G.arcs[v][w].adj;
				for(t=0;t<25;t++) P[w][t]=P[v][t];
				P[w][w]=TRUE;
            }
    }
}

void output(int city1,int city2) //输出函数
{
	int a,b,d,q=0,c;
	a=city2;
	if(a!=city1)
	{
		printf("\n从%s到%s的最短路径是",G.vexs[city1].city,G.vexs[city2].city);
		printf("(最短距离为 %dkm。)\n\t",D[a]);
		printf("%s",G.vexs[city1].city);
		d=city1;
        for(c=0;c<G.vexnum;++c)
        {
			P[a][city1]=0;
			for(b=0;b<G.vexnum;b++)
			{
				if(G.arcs[d][b].adj<INFINITY && P[a][b])
				{
					printf("-->%s",G.vexs[b].city);
					P[a][b]=0;
					d=b;
				}
			}
		}
	}
}

void Save(char filename[10],MGraph G){
	FILE *fp;
	if((fp=fopen(filename,"wb"))==NULL){
		printf("cannot open file\n");
	}//if
	if(fwrite(&G,sizeof(struct MGraph),1,fp)!=1)
		printf("file write error\n");
	fclose(fp);
}//Save

int LocateVex(MGraph G,char u[20])
{
	int i;
	for(i =0; i< G.vexnum;i++)
	{
		if(!strcmp(G.vexs[i].city,u))
			return i;
	}
	return -1;
}

void main()		//主函数
{
	char v0[20],v1[20];
	int i,j;
	char filename[10];
	FILE *fp;
S:	printf("\t*******欢迎使用最优路径导航系统*******\n");
	printf("\t*                                    *\n");
	printf("\t*             1.新建地图：           *\n");
	printf("\t*           2.打开已有地图：         *\n");
	printf("\t*             3.退出系统：           *\n");
	printf("\t*                                    *\n");
	printf("\t**************************************\n");
	printf("请输入要执行的操作:");
	switch(getchar())
	{
	case '1':
		printf("请输入新建地图的文件名:");
	p:	scanf("%s",filename);
		if(fp=fopen(filename,"rb"))
		{
			printf("该文件已存在，请重新输入其他名:");
			fclose(fp);
			goto p;
		}
		printf("\n");
		CreateUDN();
		Save(filename,G);
		printf("\n");
		break;

	case '2':
		printf("请输入文件名:");
	R:	scanf("%s",filename);
		if((fp=fopen(filename,"rb"))==NULL){
			printf("该文件不存在，请重新输入其他名:");
			goto R;
		}//if
		printf("\n");
		fp=fopen(filename,"rb");
		fread(&G,sizeof(struct MGraph),1,fp);
		break;
	case '3':
		exit(1);
		break;
	}
	displaycity();
	printf("\n\n输入出发城市和目的地:");
	scanf("%s%s",v0,v1);
	printf("\n");
	i=LocateVex(G,v0);
	j=LocateVex(G,v1);
	ShortestPath(i);
	output(i,j);
	printf("\n\n");
	printf("是否继续?(y\\n)");
	getchar();
	if(getchar()=='y')
	{
		goto S;
		getchar();
	}
	fclose(fp);
}