最短村庄报告.doc

《最短村庄报告.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数据结构实验报告实验五实验题目：图子系统指导老师：专业班级：2013年5月23日实验类型__综合__实验室_软件实验室一__一、实验题目图子系统二、实验目的和要求１．掌握图的存储思想及其存储实现２．掌握图的深度、广度优先遍历算法思想及其程序实现３．掌握图的常见应用算法的思想及其程序实现三、实验内容实验内容二：所有顶点对的最短路径1．设置4个村庄之间的交通，村庄之间的距离用各边上的权值来表示。现在要求从这4个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院最近。2

2、．设计分析用有向加权图表示的交通图中，有向边表示第i个村庄和第j个村庄之间有道路，边上的权表示这条道路的长度。该问题的实质是求解任意两顶点间的最短路径问题。即求出每个顶点到其他顶点的最短路径的最大值，最大值最小的顶点作为医院所在村庄。3．结构类型定义typedefcharvextype;/*顶点数据类型*/typedefintedgetype;/*边数据类型*/typedefstruct{ vextypevex[maxsize]; edgetypearc[maxsize][maxsi

3、ze];intvexnum,arcnum;}Mgraph;四、实验步骤实验代码：#include#definemaxvertexnum100//将maxvertexnum的值赋为100typedefcharvertextype;//将char类型用vertextype表示typedefintedgetype;//将int用edgetype表示typedefstruct{vertextypevexs[maxvertexnum];//定义一维数组顶点vexs，用来存储图的顶点字母ed

4、getypeedges[maxvertexnum][maxvertexnum];//定义二维数组用来存放边的值intn,e;//n表示顶点的数目，e表示边的数目}mgrgh;mgrghM;voidcreatemgrgh(mgrgh*g);voidshortlu(mgrgh*g);voidcreatemgrgh(mgrgh*g)//初始化图{inti,j,k,m;printf("*********************************************************")

5、;printf("请输入村庄的个数和到各村庄的道路数");scanf("%d%d",&g->n,&g->e);getchar();printf("*********************************************************");printf("请输入各个村庄的字母表示");for(i=0;in;i++){g->vexs[i]=getchar();}for(i=0;in;i++)//将村庄到各个村庄的路径都赋初值为0for(j=0;j

6、n;j++){g->edges[i][j]=0;}printf("*********************************************************");printf("输入各个村庄到各村庄的路径大小值，其中输入的第三个值为权值");for(k=0;ke;k++)//将村庄到各个村庄的路径都都表示到矩阵上{scanf("%d%d%d",&i,&j,&m);g->edges[i][j]=m;g->edges[j][i]=m;}}voidshor

7、tlu(mgrgh*g)//求出最短路径{inti,j,min,k,x;inta[100]={0};i=0;//利用循环，将各个村庄到各村庄的距离求出for(j=0;jn;j++){a[i]=a[i]+g->edges[i][j];}i=1;for(j=0;jn;j++){a[i]=a[i]+g->edges[i][j];}i=2;for(j=0;jn;j++){a[i]=a[i]+g->edges[i][j];}i=3;for(j=0;jn;j++){a[i]=a

8、[i]+g->edges[i][j];}printf("*********************************************************");for(i=0;in;i++){printf("村庄%c到各村庄之间的距离为%d",g->vexs[i],a[i]);}min=10000;for(j=0;jn;j++){if(a[j]