据结构实验五图子系统.docVIP

数据结构实验报告 实验五 实验题目：图子系统 指导老师：王春红 专业班级：计算机科学与技术系1105班 姓 名：李慧2011100521杜丽20111005122 白莹2011100523王媛2011100529 2013年 5月23日 实验类型 综合 实验室_软件实验室一__ 一、实验题目 图子系统 二、实验目的和要求 １．掌握图的存储思想及其存储实现 ２．掌握图的深度、广度优先遍历算法思想及其程序实现 ３．掌握图的常见应用算法的思想及其程序实现 。 三、实验内容 实验内容二：所有顶点对的最短路径 1．设置4个村庄之间的交通，村庄之间的距离用各边上的权值来表示。现在要求从这4个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院最近。 2．设计分析 用有向加权图表示的交通图中，有向边vi,vj表示第i个村庄和第j个村庄之间有道路，边上的权表示这条道路的长度。该问题的实质是求解任意两顶点间的最短路径问题。即求出每个顶点到其他顶点的最短路径的最大值，最大值最小的顶点作为医院所在村庄。 3．结构类型定义 typedef char vextype;/*顶点数据类型*/ typedef int edgetype;/*边数据类型*/ typedef struct{?vextype vex[maxsize]; ?edgetype arc[maxsize][maxsize]; int vexnum,arcnum; }Mgraph; 小组分工： 组长：王媛 定义结构体和主函数 组员：李慧 void juzhen(Mgraph *G) 白莹、杜丽void panduan(Mgraph *G) 实验步骤 程序如下： #include stdio.h #include malloc.h #define max 100 #define min 0 typedef int edgetype; typedef char vextype; typedef struct { vextype ver[4]; edgetype edge[4][4]; int edgenum,vernum; }Mgraph; void juzhen(Mgraph *G) { int i,j; printf(四个村庄的邻接矩阵为:\n); for(i=0;i4;i++) for(j=0;j4;j++) scanf(%d,G-edge[i][j]); } void panduan(Mgraph *G) { int a[4],b[4],c[4]; int i,j,t,t2,p,q,n,k; for(i=0;i4;i++) { a[0]=0;a[1]=0;a[2]=0;a[3]=0; a[i]=1; for(j=0;j4;j++) { b[j]=G-edge[i][j]; } t=max; for(k=0;k4;k++) { if(b[k]ta[k]==0) { t=b[k]; p=k; } } a[p]=1; printf(%d到%d的最短路径为：%d\n,i,p,t); q=2; while(q0) { for(k=0;k4;k++) { if(a[k]==0) if(b[k](b[p]+G-edge[p][k])) b[k]=b[p]+G-edge[p][k]; } t=max; for(k=0;k4;k++) { if(b[k]ta[k]==0) { t=b[k]; p=k; } } a[p]=1; q--; printf(%d到%d的最短路径为：%d\n,i,p,b[p]); } t2=min; for(k=0;k4;k++) { if(t2b[k](k!=i)) { t2=b[k]; } c[i]=t2; } }//i的循环结束 t=max; for(k=0;k4;k++) { if(tc[k]) { t=c[k];