某数据结构课程设计公园导游图.doc

实验四:图(内容:某公园导游图)
一、问题描述:
公园导游系统:给出一张某公园的导游图,游客通过终端询问可知︰从某一景到另一景点的最短路径。游客从公园大门进入,选一条最佳路线,使游客可以不重复地游览各景点,最后回到出口(出口就在入口旁边)。
二、设计描述:
(存储方法).本程序特地设计函数void initgraph()用于实现键盘输入图的结构;
vist(GraphMatrix graph)用于实现访问任一景点的信息;
。利用floyd算法-实现每一对景点间的最短路径。
并利用void outgraph()函数实现显示起始点和终点间的最短路径和其长度;
三、程序清单:
#include<iostream>
using namespace std;
#include<>
#define MAXVEX 100
#define MAX 999
typedef char VexType;
typedef float AdjType;
typedef struct //定义图结构
{
int n; /* 图的顶点个数*/
VexType vexs[MAXVEX]; /* 顶点信息*/
AdjType arcs[MAXVEX][MAXVEX]; /* 边信息*/
} GraphMatrix;
GraphMatrix graph; //定义一个图graph
typedef struct //定义最短路径ShortPath结构
{
AdjType a[MAXVEX][MAXVEX]; /* 关系矩阵A,存放每对顶点间最短路径长度*/
int nextvex[MAXVEX][MAXVEX];
/* nextvex[i][j]存放vi到vj最短路径上vi的后继顶点的下标值*/
} ShortPath;
ShortPath path; //定义路径path
void floyd(GraphMatrix * pgraph, ShortPath * ppath) //floyd算法-用于实现每一对景点间的最短路径
{
int i, j, k;
for (i = 0; i < pgraph->n; i++)
for (j = 0; j < pgraph->n; j++) {
if (pgraph->arcs[i][j] != MAX)
ppath->nextvex[i][j] = j;
else ppath->nextvex[i][j] = -1;
ppath->a[i][j] = pgraph->arcs[i][j];
}
for (k = 0; k < pgraph->n; k++)
for (i = 0; i < pgraph->n; i++)
for (j = 0; j < pgraph->n; j++) {
if ( ppath->a[i][k] >= MAX || ppath->a[k][j] >= MAX )
continue;
if ( ppath->a[i][j] > ppath->a[i][