数据结构实验五图子系统
实验五
实验题目:图子系统
指导老师:王春红
专业班级:计算机科学与技术系1105班姓名:李慧2011100521杜丽20111005122
白莹2011100523王媛2011100529
2013年 5月23日
实验类型综合实验室_软件实验室一__
一、实验题目
1
图子系统
二、实验目的和要求
,(掌握图的存储思想及其存储实现
,(掌握图的深度、广度优先遍历算法思想及其程序实现
,(掌握图的常见应用算法的思想及其程序实现。
三、实验内容
实验内容二:所有顶点对的最短路径
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
2
{
vextype ver[4];
edgetype edge[4][4];
int edgenum,vernum; }Mgraph;
void juzhen(Mgraph *G) {
int i,j;
printf("四个村庄的邻接矩阵为:\n"); for(i=0;i<4;i++)
for(j=0;j<4;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;i<4;i++)
{
a[0]=0;a[1]=0;a[2]=0;a[3]=0;
a[i]=1;
for(j=0;j<4;j++)
{
b[j]=G->edge[i][j];
}
t=max;
for(k=0;k<4;k++)
{
if(b[k]<t&&a[k]==0)
{
t=b[k];
p=k;
}
}
a[p]=1;
printf("%d到%d的最短路径为:%d\n",i,p,t); q=2;
while(q>0)
{
for(k=0;k<4;k++)
{
if(a[k]==0)
if(b[k]>(b[p]+G->edge[p][k]))
b[k]=b[p]+G->edge[p][k];
3
}
t=max;
for(k=0;k<4;k++)
{
if(b[k]<t&&a[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;k<4;k++)
{
if(t2<b[k]&&(k!=i))
{
t2=b[k];
}
c[i]=t2;
}
}//i的循环结束
t=max;
for(k=0;k<4;k++)
{
if(t>c[k])
{
t=c[k];
n=k;
}
}
switch(n)
{
case 0:
printf("医院设在0村庄!");
printf("0到最远村庄的最近距离为:%d\n",t); break;
case 1:
printf("医院设在1村庄!");
printf("1到最远村庄的最近距离为:%d\n",t); break;
case 2:
4
printf("医院设在2村庄!");
printf("2到最远村庄的最近距离为:%d\n",t); break;
case 3:
printf("医院设在3村庄!");
printf("3到最远村庄的最近距离为:%d\n",t);
break;
}
}
main()
{
Mgraph *G;
G=(Mgraph*)malloc(sizeof(Mgraph));
juzhen(G);
panduan(G);
}
实验结果如下:
五、实验总结
这次实验和之前的实验相比有一定的难度，需要对实验的思路特别清晰，在其中设定的变量有些多，要特别注意，其中遇到了很多的问题，通过请教同学老师最终得出了结果～
5。