数据结构图综合实验实验报告宁波工程学院

图综合实验实验报告

一、实验目的

1）熟悉图的基本操作。

2）掌握求图的最短路径算法。

3）加深对图的理解，逐步培养解决实际问题的编程能力。

班级：计科12-1 学号： 124010101 姓名： 实验日期：2013.12.4

二、实验环境

装有Visual C＋＋6.0的计算机。 本次实验共计4学时。

三、实验内容

【基本要求】

给定n个村庄之间的交通图。若村庄i和j之间有路可通，则i和j用边连接，边上的权值Wij表示这条道路的长度。现打算在这n个村庄中选定一个村庄建一所医院。编写如下算法： （1） 求出该医院应建在哪个村庄，才能使距离医院最远的村庄到医院的路程最短。 （2） 求出该医院应建在哪个村庄，能使其它所有村庄到医院的路径总和最短。 【提示】

? 对于问题（1），可以先求出每个村庄到其它所有村庄的最短路径，保存其最大值（表示

假设医院建在该村庄，距离医院最远的村庄的路径长度）；然后在这些最大值中找出一个最小值。 ? 对于问题（2），可以先求出每个村庄到其它所有村庄的最短路径，保存其累加和（表示

假设医院建在该村庄，其它所有村庄距离医院的路径总和）；然后在这些和中找出一个最小值。

? 自己设定n个村庄的交通图。例如下图所示：

四、 重要数据结构

typedef struct /*图的定义*/

{ int edges[MAXV][MAXV]; /*邻接矩阵*/ int n,e; /*顶点数，弧数*/

} MGraph; /*图的邻接矩阵类型*/

五、 实现思路分析

void Dijkstra(MGraph g,int v); //狄克斯特拉算法

void Dispath(int dist[],int path[],int s[],int n,int v); void Ppath(int path[],int i,int v); void He(MGraph g,int v);//情况一 void Slove(MGraph g,int v);//情况二

六、 程序调试问题分析

狄克斯特拉算法输出的dist【i】总为0，在主函数对g.edges[i][j]先赋值即可。

七、 实验总结

通过这次实验，我对最小生成树有了更好的认识。在实验过程中，我掌握了最短路径的构造方法，学会了如何将理论知识转换为实际应用。同时，在解决程序中遇到的一些问题的同时，我也对调试技巧有了更好的掌握，分析问题的能力也略有提高。

在实验中，我遇到了许多难点，这就需要我们有扎实的基础，需要有灵活的头脑，只有不断的练习，不断的训练，我们才能处理各种问题。在以后的学习中，我要不断的努力，多联系，多思考，我相信我能有所进步的。

#include #include #include #include using namespace std; #define MAXV 100 int s[MAXV]; int dist[MAXV]; int path[MAXV]; //int dist[MAXV]; //typedef int InfoType; //typedef struct //{

int no;

/*顶点编号*/

// InfoType info;

/*顶点其他信息*/

/*最大顶点个数*/

#define INF 32767 /*INF表示∞*/

//} VertexType;

typedef struct

/*顶点类型*/

/*图的定义*/

/*邻接矩阵*/

/*图的邻接矩阵类型*/

{ int edges[MAXV][MAXV]; } MGraph;

typedef struct {

int n,e; /*顶点数，弧数*/

int u; //边的起始顶点 int v; //边的终止顶点 int w; //边的权值

} Edge;

void Dijkstra(MGraph g,int v); //狄克斯特拉算法

void Dispath(int dist[],int path[],int s[],int n,int v); void Ppath(int path[],int i,int v); void He(MGraph g,int v);//情况一 void Slove(MGraph g,int v);

int main() {

MGraph g; int i,u,v,w,j,n;

freopen(\,\,stdin); g.n = 6;g.e = 10; for( i=0;i

{

scanf(\,&u,&v,&w); g.edges[u][v] = w; g.edges[v][u] = w; }

for(i = 0; i < g.n; i++)

Dijkstra(g,i);

for( j=0;j

if(i!=j)g.edges[i][j]=INF; else g.edges[i][j]=0;

for (i = 0; i < g.e; i++)

printf(\);

He(g,0);

printf(\);

// for(i = 0; i < g.n; i++) Slove(g,i); }

void Ppath(int path[],int i,int v) {

int k; k = path[i]; if(k == v)

return;

Ppath(path,k,v); printf(\,k); }

void Dispath(int dist[],int path[],int s[],int n,int v) { }

void Dijkstra(MGraph g,int v) //狄克斯特拉算法 {

int dist[MAXV],path[MAXV]; int s[MAXV]; int mindis,i,j,u;

for(i = 0; i < g.n; i ++) {

dist[i] = g.edges[v][i]; s[i] = 0;

if(g.edges[v][i]

path[i] = v; path[i] = -1; else int i;

for(i = 0; i < n; i++) if(s[i] == 1 && i != v)

{ }

printf(\从%d到%d的最短路径长度为：%d\\t路径为：\,v,i,dist[i]); printf(\,v); Ppath(path,i,v); printf(\,i);

return 0;

}

}

s[v] = 1;path[v] = 0; for(i = 0; i

Dispath(dist,path,s,g.n,v);

mindis = INF;

for(j = 0;j

if(s[j] == 0 && dist[j] < mindis) { }

s[u] = 1; if(s[j] == 0)

if(g.edges[u][j] < INF && dist[u] + g.edges[u][j] < dist[j]) { }

dist[j] = dist[u] + g.edges[u][j]; path[j] = u; u = j;

mindis = dist[j];

for(j = 0; j < g.n; j++)

void He(MGraph g,int v) {

int i,j,max,min,k = -1; max = -INF; min = INF;

for(i = 0; i < g.n; i++) { }

printf(\医院建在%d能使距离医院最远的村庄到医院的路程最短，最短路程为%d\\n\,k,min);

for(j = 0; j < g.n; j++) { }

if(max < min){ }

printf(\出发最远距离：%d\\n\,i,max);

min = max; k = i;

if(g.edges[i][j] > max && i != j && g.edges[i][j] != INF) max = g.edges[i][j];

printf(\);