景区旅游信息管理系统

　校园 旅游信息管理系统 1 、1 项目需求 分析 在旅游景区,经常会遇到游客打听从一个景点到另一个景点的最短路径与最短距离,这类游客不喜欢按照导游图的线路来游览,而就是挑选自己感兴趣的景点游览。为于帮助这类游客信息查询,就需要计算出所有景点之间最短路径与最短距离。算法采用迪杰斯特拉算法或弗洛伊德算法均可。建立一个景区旅游信息管理系统,实现的主要功能包括制订旅游景点导游线路策略与制订景区道路铺设策略。

　任务中景点分布就是一个无向带权连通图,图中边的权值就是景点之间的距离。

　1)景区旅游信息管理系统中制订旅游景点导游线路策略,首先通过遍历景点,给出一个入口景点,建立一个导游线路图,导游线路图用有向图表示。遍历采用深度优先策略,这也比较符合游客心理。

　 (2)为了使导游线路图能够优化,可通过拓朴排序判断图中有无回路,若有回路,则打印输出回路中的景点,供人工优化。

　 (3)在导游线路图中,还为一些不愿按线路走的游客提供信息服务,比如从一个景点到另一个景点的最短路径与最短距离。在本线路图中将输出任意景点间的最短路径与最短距离。

　 (4)在景区建设中,道路建设就是其中一个重要内容。道路建设首先要保证能连通所有景点,但又要花最小的代价,可以通过求最小生成树来解决这个问题。本任务中假设修建道路的代价只与它的里程相关。

　因此归纳起来,本任务有如下功能模块:

　 创建景区景点分布图;

　 输出景区景点分布图(邻接矩阵)

　 输出导游线路图;

　 判断导游线路图有无回路;

　 求两个景点间的最短路径与最短距离;

　 输出道路修建规划图。

　 主程序用菜单选项供用户选择功能模块。

　1 、2 项目设计流程

　1 、2 、1 项目总体框架

　 1 、2 、2 项目数据结构 校园 旅游信息管理系统 创 建 景 区 景 点 分 布 图 输 出 景 区 景 点 分 布 图 输 出 景 区 导 游 线 路 图 导 游 线 路 图 有 无 回 路 两 个 景 点 间 的 最 短 路 径输 出 道 路 修 建 规 划 图

　#ifndef SUCCESS

　// 标志位成功 #define SUCCESS

　1 #endif #ifndef FAILURE

　// 标志位失败 #define FAILURE

　0 #endif #ifndef INF

　// 标志位无穷 #define INF

　0x3f3fffff #endif #ifndef MAXNUM

　#define MAXNUM

　20 #endif typedef bool STATUS;

　// 定义函数状态数据类型 typedef char VERTEXTYPE[MAXNUM][11];

　// 定义顶点向量数据类型 typedef int

　ADJMATRIX[MAXNUM][MAXNUM];

　// 定义邻接矩阵数据类型 typedef struct GRAPH

　// 定义图数据类型 {

　VERTEXTYPE Vexs;

　// 图的顶点向量

　ADJMATRIX

　Arcs;

　// 图的邻接矩阵

　int VexNum;

　// 图的当前顶点

　int ArcNum;

　// 图的当前弧 }*PGRAPH;

　 // 定义图的指针数据类型 typedef struct CLOSEDGE

　// 定义辅助数组数据类型 {

　VERTEXTYPE Vexs;

　// 图的顶点向量

　int Lowcost[MAXNUM];

　 // }*PCLOSEDGE;

　// 定义辅助数组指针数据类型 1 、2 、3 项目模块设计 创建景区景点分布图 一.

　邻接矩阵 (Adjacency Matrix)( 二维数组表示法) 在图的邻接矩阵表示中,有一个记录各个顶点信息的顶点表,还有一个表示各个顶点之间关系的邻接矩阵。

　设图 A = (V, E)就是一个有 n 个顶点的图, 图的邻接矩阵就是一个二维数组 A、edge[n][n],定义(满足如下条件的 n 阶矩阵):

　无向图数组表示法特点: 1)无向图邻接矩阵就是对称矩阵,同一条边表示了两次; 2)顶点v的度:在无向图中等于二维数组对应行(或列)中1的个数;在有向图中, 统计第 i 行 1   otherwiseor if0,)

　E j) (i,

　> , (<

　 , 1] ][ [ . AE j ij i Edge

　的个数可得顶点 i 的出度,统计第 j 列 1 的个数可得顶点 j 的入度。

　3)判断两顶点 v、u 就是否为邻接点:只需判二维数组对应分量就是否为 1; 4)顶点不变,在图中增加、删除边:只需对二维数组对应分量赋值 1 或清 0; 5)设存储顶点的一维数组大小为 n(图的顶点数 n), G 占用存储空间:n+n 2 ;G 占用存储空间只与它的顶点数有关,与边数无关;适用于边稠密的图;

　流程图: 初始化图的顶点数scanf("%d",&pGraph->VexNum);if(pGraph->VexNum>20)初始化图的弧数scanf("%d",&pGraph->ArcNum);if(pGraph->ArcNum>20)初始化图的顶点名称初始化图的弧权值为最大值输入弧的信息终止 程序: //创建景区景点分布图 STATUS CreateGraph(PGRAPH pGraph) {

　printf("\t\t\t_________________________________\n");

　printf("\n\t\t\t$\t 创建景区景点分布图\t$\n");

　printf("\t\t\t_________________________________\n");

　//初始化图的顶点数

　printf("\t\t\t 初始化顶点数与弧度数、、、、、、\n");

　printf("\t\t\t 请输入图的顶点数(<=20):");

　 scanf("%d",&pGraph->VexNum);

　//检查

　if(pGraph->VexNum>20)

　{

　printf("\t\t\t 警告:输入数据错误！！！\n");

　printf("\t\t\t 按任意键回主菜单！！！");

　getch();

　return FAILURE;

　 }

　//初始化图的弧数

　printf("\t\t\t 请输入图的弧度数(<=20):");

　scanf("%d",&pGraph->ArcNum);

　//检查

　if(pGraph->ArcNum>20)

　{

　printf("\t\t\t 警告:输入数据错误！！！\n");

　printf("\t\t\t 按任意键回主菜单！！！");

　getch();

　return FAILURE;

　}

　//初始化图的顶点名称

　printf("\t\t\t---------------------------------\n");

　printf("\t\t\t 初始化的顶点名称、、、、、、\n");

　for(int i=0;i<pGraph->VexNum;i++)

　{

　printf("\t\t\t 请输入第%d 个顶点名称:",i+1);

　scanf("%s",pGraph->Vexs[i]);

　}

　//初始化图的弧权值为最大值

　for(i=0;i<pGraph->VexNum;i++)

　for(int j=0;j<pGraph->VexNum;j++)

　pGraph->Arcs[i][j]=INF;

　//输入弧的信息

　printf("\t\t\t---------------------------------\n");

　printf("\t\t\t 初始化的弧的信息、、、、、、\n");

　printf("\t\t\t 请输入弧的信息(注:从 0 开始):\n");

　for(i=0;i<pGraph->ArcNum;i++)

　{

　int Stav,Endv,Weight;

　printf("\t\t\t 请输入第%d 条弧(格式:Vi Vj Weight):",i+1);

　scanf("%d%d%d",&Stav,&Endv,&Weight);

　pGraph->Arcs[Endv][Stav]=Weight;

　pGraph->Arcs[Stav][Endv]=Weight;

　}

　printf("\t\t\t 创建景区景点分布图成功！！！\n");

　printf("\t\t\t 按任意键回主菜单！！！");

　getch();

　return SUCCESS; }

　输出景区景点分布图 流程图: 景区景点名称i=0i<pGraph->VexNumprintf("%s\t",pGraph->Vexs[i]);i++景区景点信息i=0i<pGraph->VexNumj=0j<pGraph->VexNumif(pGraph->Arcs[i][j]==INF)printf("∞\t");printf("%d\t",pGraph->Arcs[i][j]);j++i++终止 程序: //输出景区景点分布图 STATUS PrintGraph(const PGRAPH pGraph) {

　printf("\t\t\t_________________________________\n");

　printf("\n\t\t\t$\t 显示景区景点分布图\t$\n");

　printf("\t\t\t_________________________________\n\n");

　//

　printf("\t 景区景点名称、、、、、、\n\t");

　for(int i=0;i<pGraph->VexNum;i++)

　 printf("%s\t",pGraph->Vexs[i]);

　printf("\n\n\t 景区景点信息、、、、、、\n");

　for(i=0;i<pGraph->VexNum;i++)

　{

　printf("\t___________________________________________________________\n\t");

　for(int j=0;j<pGraph->VexNum;j++)

　if(pGraph->Arcs[i][j]==INF)

　printf("∞\t");

　else

　printf("%d\t",pGraph->Arcs[i][j]);

　printf("\n");

　}

　printf("\t___________________________________________________________\n\t");

　printf("按任意键回主菜单！！！");

　getch();

　return SUCCESS; }

　输出景区导游线路图 图的遍历 从图中某一顶点出发访遍图中所有的顶点,且使每个顶点仅被访问一次,这一过程就叫做图的遍历 (Traversing Graph)。

　图中可能存在回路,且图的任一顶点都可能与其它顶点相通,在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。

　为了避免重复访问,可设置一个标志顶点就是否被访问过的辅助数组 visited [ ]。

　辅助数组 visited [ ] 的初始状态为 0, 在图的遍历过程中, 一旦某一个顶点 i

　被访问, 就立即让 visited [i] 为 1, 防止它被多次访问。

　两种图的遍历方法: 深度优先搜索

　 DFS (Depth First Search) 广度优先搜索

　 BFS (Breadth First Search) 广度优先搜索遍历图(BFS) 对连通图,从起始点 V 到其余各顶点必定存在路径。

　 其中,V->w 1 , V->w 2 , V->w 8

　的路径长度为 1;

　V->w 7 , V->w 3 , V->w 5

　的路径长度为 2;

　V->w 6 , V->w 4

　的路径长度为 3

　从图中的某个顶点 V 0 出发,并在访问此顶点之后依次访问 V 0 的所有未被访问过的邻接点,之后按这些顶点被访问的先后次序依次访问它们的邻接点,直至图中所有与 V 0 有路径相通的顶点都被访问到。

　若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止。

　流程图:

　定义访问标志数组初始化访问标志数组为false定义队列、并初始化队列if(InitQueue(&Queue,pGraph->VexNum)==FAILURE)否if(!Visit[Vertex])printf("\t\t\t%s景点......\n",pGraph->Vexs[Vertex]);标志访问过Visit[Vertex]=true;出队DeQueue(&Queue,&Vertex);i=0i<pGraph->VexNumif(Visit[i]==false&&pGraph->Arcs[Vertex][i]!=INF)是EnQueue(&Queue,i);是i++ 否while(QueueLen(&Queue));终止程序:

　//输出景区导游线路图(注:广度优先遍历) STATUS TraverseGraph(const PGRAPH pGraph) {

　printf("\t\t\t_________________________________\n");

　printf("\n\t\t\t$\t 输出景区导游线路图\t$\n");

　printf("\t\t\t_________________________________\n\n");

　//定义访问标志数组

　bool* Visit=(bool*)malloc(pGraph->VexNum*sizeof(bool));

　//初始化访问标志数组为 false

　for(int i=0;i<pGraph->VexNum;i++)

　Visit[i]=false;

　 //定义队列、并初始化队列

　QUEUE Queue;

　if(InitQueue(&Queue,pGraph->VexNum)==FAILURE)

　{

　printf("\t\t\t 警告:创建队列失败！！！\n");

　printf("\t\t\t 按任意键回主菜单！！！");

　getch();

　return FAILURE;

　}

　//定义访问顶点变量,并初始值为 0

　int Vertex=0;

　do

　{

　if(!Visit[Vertex])

　{

　printf("\t\t\t%s 景点、、、、、、\n",pGraph->Vexs[Vertex]);

　//标志访问过

　Visit[Vertex]=true;

　//遍历与 Vertex 相连的顶点并进队

　for(i=0;i<pGraph->VexNum;i++)

　if(Visit[i]==false&&pGraph->Arcs[Vertex][i]!=INF)

　EnQueue(&Queue,i);

　}

　//出队

　DeQueue(&Queue,&Vertex);

　}while(QueueLen(&Queue));

　//销毁队列

　DestroyQueue(&Queue);

　printf("\t\t\t 按任意键回主菜单！！！");

　getch();

　return SUCCESS; } 有向图的拓扑排序 何谓“拓扑排序”？

　对有向图进行如下操作: 假设 G=(V,E)就是一个具有 n 个顶点的有向图,V 中顶点序列 vl,v2,„,vn 称做一个拓扑序列(Topological Order),当且仅当该顶点序列满足下列条件:若在有向图 G 中存在从顶点 vi 到 vj 的一条路径,则在顶点序列中顶点 vi 必须排在顶点 vj 之前。通常,在 AOV 网中,将所有活动排列成一个拓扑序列的过程叫做拓扑排序(Topological Sort)。

　在 AOV 网中不应该出现有向环。因为环的存在意味着某项活动将以自己为先决条件,显然无法形成拓扑序列。

　判定网中就是否存在环的方法:对有向图构造其顶点的拓扑有序序列,若网中所有顶点都出现在它的拓扑有序序列中,则该 AOV 网中一定不存在环。

　例如:对于有向图

　可求得拓扑有序序列: A B C D

　或

　A C B D

　 例如,

　对学生选课工程图进行拓扑排序,

　得到的拓扑有序序列为

　C 1

　, C 2

　, C 3

　, C 4

　, C 5

　, C 6

　, C 8

　, C 9

　, C 7 或

　 C 1

　, C 8

　, C 9

　, C 2 , C 5

　, C 3 , C 4

　, C 7

　, C 6

　反之,对于下列有向图

　 不能求得它的拓扑有序序列。

　因为图中存在一个回路 {B, C, D}

　如何进行 ？ 输入 AOV 网络。令 n 为顶点个数。

　(1)在 AOV 网络中选一个没有直接前驱的顶点,并输出之;

　(2)从图中删去该顶点, 同时删去所有它发出的有向边; 重复以上步骤,直到全部顶点均已输出,拓扑有序序列形成,拓扑排序完成;或图中还有未输出的顶点,但已跳出处理循环。这说明图中还剩下一些顶点,它们都有直接前驱,再也找不到没有前驱的顶点了。这时 AOV 网络中必定存在有向环。

　在实现拓扑排序的算法中,采用邻接表作为有向图的存储结构,每个顶点设置一个单链表,每个单链表有一个表头结点,在表头结点中增加一个存放顶点入度的域 count,这些表头结点构成一个数组。

　B A D c

　为了避免重复检测入度为 0 的点,另设一栈存放所有入度为 0 的点。

　对于有n个顶点与e条边的有向图而言,for循环中建立入度为0的顶点栈时间为O(n);若在拓扑排序过程中不出现有向环,则每个顶点出栈、入栈与入度减 1 的操作在 while 循环语句中均执行 e 次,因此拓扑排序总的时间花费为 O (n+e)。

　流程图: 计算各顶点的入度j=0j<pGraph->VexNumi=0i<pGraph->VexNumif(pGraph->Arcs[i][j]!=INF)Indegree[j]++;if(!Indegree[j])PushStack(&Stack,j);i++j++ while(StackLen(&Stack))出桟、并访问PopStack(&Stack,&k);i=0if(pGraph->Arcs[k][i]!=INF)if(!(--Indegree[i]))PushStack(&Stack,i);i++i<pGraph->VexNum 程序: //有向图的拓扑排序 STATUS TopologicalSort(const PGRAPH pGraph)

　{

　printf("\t\t\t_________________________________\n");

　printf("\n\t\t\t$\t 导游线路图有无回路\t$\n");

　printf("\t\t\t_________________________________\n\n");

　//定义入度数组,记录每个顶点的入度,初始化为 0

　int Indegree[MAXNUM]={0};

　//定义桟、并初始化桟

　STACK Stack;

　if(InitStack(&Stack,pGraph->VexNum)==FAILURE)

　{

　printf("\t\t\t 警告:创建桟失败！！！\n");

　printf("\t\t\t 按任意键回主菜单！！！");

　getch();

　return FAILURE;

　}

　printf("\t\t\t 计算各顶点的入度、、、、、\n");

　for(int j=0;j<pGraph->VexNum;j++)

　{

　//求各个顶点的入度

　for(int i=0;i<pGraph->VexNum;i++)

　if(pGraph->Arcs[i][j]!=INF)

　Indegree[j]++;

　//入度为 0 的顶点入栈

　 if(!Indegree[j])

　PushStack(&Stack,j);

　}

　printf("\t\t\t 进行拓扑排序、、、、、\n");

　//Count 用来指示入度为 0 的顶点个数

　int Count=0,k;

　while(StackLen(&Stack))

　{

　//出桟、并访问

　PopStack(&Stack,&k);

　printf("%s\t",pGraph->Vexs[k]);

　Count++;

　//对出栈的顶点所指向的顶点减一 ,并且将入度为 0 的顶点入栈

　for(int i=0;i<pGraph->VexNum;i++)

　if(pGraph->Arcs[k][i]!=INF)

　if(!(--Indegree[i]))

　PushStack(&Stack,i);

　}

　//销毁桟

　DestroyStack(&Stack);

　//判断就是否就是拓扑排序

　 if(Count<pGraph->VexNum)

　printf("\t\t\t 结果:导游线路图有回路\n");

　else

　printf("\t\t\t 结果:导游线路图无回路\n");

　printf("\t\t\t 按任意键回主菜单！！！");

　getch();

　return SUCCESS; } 求两个景点间的最短路径 最短路径定义

　 所谓最短路径问题就是指:如果从图中某一顶点(源点)到达另一顶点(终点)的路径可能不止一条,如何找到一条路径似的沿此路径上各边的权值总与(称为路径长度)达到最小。

　迪杰斯特拉 (Dijkstra) 算法求单源最短路径 由 Dijkstra 提出的一种按路径长度递增序产生各顶点最短路径的算法。

　(1) 按路径长度递增序产 生各顶点最短路径 若按长度递增的次序生成从源点 s 到其它顶点的最短路径,则当前正在生成的最短路径上除终点以外,其余顶点的最短路径均已生成(将源点的最短路径瞧作就是已生成的源点到其自身的长度为 0 的路径)。

　(2) 具体做法

　 一开始第一组只包括顶点 v 1 ,第二组包括其她所有顶点, v 1 对应的距离值为 0 ,第二组的顶点对应的距离值就是这样确定的:若图中有边 <v 1 , v j >, 则 v j 的距离为此边所带的权值,否则 v j 的距离值为一个很大的数 ( 大于所有顶点间的路径长度 ) ,然后每次从第二组的顶点中选一个其距离值为最小的 v m 加入到第一组中。每往第一组加入一个顶点 v m ,就要对第二组的各个顶点的距离值进行一次修正。若加进 v m 做中间顶点,使从 v 1 到 v j 的最短路径比不加 v m 的路径为短,则要修改 v j 的距离值。修改后再选距离最小的顶点加入到第一组中。如此进行下去,直到图中所有顶点都包括在第一组中,或再也没有可加入到第一组中的顶点存在为止。

　 假设有向图 G 的 n 个顶点为 1 到 n, 并用邻接矩阵 cost 表示 , 若 < v i , v j > 就是图 G 中的边,则 cost[i][j] 的值等于边所带的权 ; 若 <v i , v j > 不就是图 G 中的边,则 cost[i][j] 等于一个很大的数;若 i=j, 则 cost[i][j]=0 。另外 , 设置三个数组 S[n] 、 dist[n] 、 pre[n] 。

　S 用以标记那些已经找到最短路径的顶点,若 S[i-1]=1, 则表示已经找到源点到顶点 i 的最短路径 , 若 S[i-1]=0, 则表示从源点到顶点 i 的最短路径尚未求得。

　dist[i-1] 用来记录源点到顶点 i 的最短路径。

　pre[i-1] 表示从源点到顶点 i 的最短路径上该点的前趋顶点,若从源点到该顶点无路径,则用 0 作为其前一个顶点序号。

　流程图: 定义路径矩阵、距离矩阵ADJMATRIX PathMatrix,DisMatrix;初始化路径矩阵、距离矩阵i=0i<pGraph->VexNumj=0j<pGraph->VexNumDisMatrix[i][j]=pGraph->Arcs[i][j];PathMatrix[i][j]=-1;j++i++ 求PathMatrix矩阵K=0k<pGraph->VexNumi=0i<pGraph->VexNumj=0j<pGraph->VexNumif(DisMatrix[i][j]>DisMatrix[i][k]+DisMatrix[k][j])DisMatrix[i][j]=DisMatrix[i][k]+DisMatrix[k][j];PathMatrix[i][j]=k;j++i++K++

　程序: //求两个景点间的最短路径 STATUS MinShortPath(const PGRAPH pGraph) {

　printf("\t\t\t_________________________________\n");

　printf("\n\t\t\t$\t 景点之间的最短路径\t$\n");

　printf("\t\t\t_________________________________\n\n");

　//定义路径矩阵、距离矩阵

　ADJMATRIX PathMatrix,DisMatrix;

　 //定义辅助变量

　int i,j,k;

　//初始化路径矩阵、距离矩阵

　for(i=0;i<pGraph->VexNum;i++)

　for(j=0;j<pGraph->VexNum;j++)

　{

　DisMatrix[i][j]=pGraph->Arcs[i][j];

　PathMatrix[i][j]=-1;

　}

　//求 PathMatrix 矩阵

　for(k=0;k<pGraph->VexNum;k++)

　for(i=0;i<pGraph->VexNum;i++)

　for(j=0;j<pGraph->VexNum;j++)

　if(DisMatrix[i][j]>DisMatrix[i][k]+DisMatrix[k][j])

　{

　DisMatrix[i][j]=DisMatrix[i][k]+DisMatrix[k][j];

　PathMatrix[i][j]=k;

　}

　 //定义起点、终点

　int Stav=-1,Endv=-1;

　//定义起点、终点名称

　char StaNam[MAXNUM],EndNam[MAXNUM];

　printf("\t\t\t 输入起始点与终点名称(格式:Sta End):");

　scanf("%s%s",StaNam,EndNam);

　for(i=0;i<pGraph->VexNum;i++)

　{

　if(!strcmp(pGraph->Vexs[i],StaNam))

　//起始点名称下标

　Stav=i;

　if(!strcmp(pGraph->Vexs[i],EndNam))

　//终点名称下标

　Endv=i;

　}

　//判断起始点名称与终点名称就是否存在

　if(Stav==-1||Endv==-1)

　 return FAILURE;

　//定义桟、并初始化

　STACK Stack;

　if(InitStack(&Stack,pGraph->VexNum)==FAILURE)

　{

　printf("\t\t\t 警告:创建桟失败！！！\n");

　printf("\t\t\t 按任意键回主菜单！！！");

　getch();

　}

　//将所有路径入桟

　while(Endv!=-1)

　{

　PushStack(&Stack,Endv);

　Endv=PathMatrix[Stav][Endv];

　}

　//将所有路径出桟、并输出

　printf("\t\t\t");

　while(1)

　{

　printf("%s-->",pGraph->Vexs[Stav]);

　if(!StackLen(&Stack))

　break;

　PopStack(&Stack,&Stav);

　}

　printf("终点");

　//销毁桟

　DestroyStack(&Stack);

　printf("\n\t\t\t 按任意键回主菜单！！！");

　getch();

　return SUCCESS; } 输出道路修建规划图 prim 算法 在无向加权图中,n 个顶点的最小生成树有 n-1 条边,这些边使得 n 个顶点之间可达,且总的代价最小。

　prim 算法就是一种贪心算法,将全部的顶点划分为 2 个集合,每次总在 2 个集合之间中找最小的一条边,局部最优最终达到全局最优,这正就是贪心的思想。

　具体的描述参见相关书籍: 描述 从单一顶点开始,普里姆算法按照以下步骤逐步扩大树中所含顶点的数目,直到遍及连通图的

　所有顶点。

　1、输入:一个加权连通图,其中顶点集合为 V,边集合为 E;

　2、初始化:Vnew = {x},其中 x 为集合 V 中的任一节点(起始点),Enew = {};

　3、重复下列操作,直到 Vnew = V:

　1、在集合 E 中选取权值最小的边(u, v),其中 u 为集合 Vnew 中的元素,而 v 则不就是(如果存在有多条满足前述条件即具有相同权值的边,则可任意选取其中之一);

　2、将 v 加入集合 Vnew 中,将(u, v)加入集合 Enew 中;

　4、输出:使用集合 Vnew 与 Enew 来描述所得到的最小生成树。

　例如:

　流程图:

　定义辅助数组变量CLOSEDGE Closedge;i=1i<pGraph->VexNumClosedge.Lowcost[i]=pGraph->Arcs[Min][i];strcpy(Closedge.Vexs[i],pGraph->Vexs[Min]);i++i=1i<pGraph->VexNum保存辅助数组中Closedge.Lowcost权值最小值查找第一个权值不是0的位置查找辅助数组中最小值输出信息选择最小边j=0j<pGraph->VexNumif(pGraph->Arcs[Min][j]<Closedge.Lowcost[j])Closedge.Lowcost[j]=pGraph->Arcs[Min][j];strcpy(Closedge.Vexs[j],pGraph->Vexs[Min]);j++i++

　程序: //输出道路修建规划图(注:最小生成树) STATUS MininumCST(const PGRAPH pGraph) {

　printf("\t\t\t_________________________________\n");

　printf("\n\t\t\t$\t 输出道路修建规划图\t$\n");

　printf("\t\t\t_________________________________\n\n");

　//定义辅助数组变量

　CLOSEDGE Closedge;

　int Min=0;

　//初始化辅助数组,从第一个顶点开始

　for(int i=1;i<pGraph->VexNum;i++)

　{

　Closedge、Lowcost[i]=pGraph->Arcs[Min][i];

　strcpy(Closedge、Vexs[i],pGraph->Vexs[Min]);

　}

　Closedge、Lowcost[Min]=0;

　//选这其余的 pGraph->VexNum-1 个点

　for(i=1;i<pGraph->VexNum;i++)

　{

　//保存辅助数组中 Closedge、Lowcost 权值最小值

　//查找第一个权值不就是 0 的位置

　for(int j=0;j<pGraph->VexNum;j++)

　if(Closedge、Lowcost[j]!=0)

　break;

　Min=j;

　//查找辅助数组中最小值

　for(j=0;j<pGraph->VexNum;j++)

　if(Closedge、Lowcost[j]&&Closedge、Lowcost[j]<Closedge、Lowcost[Min])

　Min=j;

　//输出信息

　printf("\t\t\t\t%s---->%s\n",Closedge、Vexs[Min],pGraph->Vexs[Min]);

　//

　Closedge、Lowcost[Min]=0;

　//选择最小边

　for(j=0;j<pGraph->VexNum;j++)

　if(pGraph->Arcs[Min][j]<Closedge、Lowcost[j])

　{

　Closedge、Lowcost[j]=pGraph->Arcs[Min][j];

　strcpy(Closedge、Vexs[j],pGraph->Vexs[Min]);

　}

　}

　printf("\n\t\t\t 按任意键回主菜单！！！");

　getch();

　 return SUCCESS; } 1 、3 项目编码实现 #include <stdio、h> #include <stdlib、h> #include "Graph、h" int Frame() {

　printf("\t\t\t_________________________________\n");

　printf("\n\t\t\t$\t 景区旅游信息管理系统\t$\n");

　printf("\t\t\t_________________________________\n\n");

　printf("\t\t\t1、创建景区景点分布图\n\n");

　printf("\t\t\t2、保存景区景点分布图\n\n");

　printf("\t\t\t3、读取景区景点分布图\n\n");

　printf("\t\t\t4、输出景区景点分布图\n\n");

　printf("\t\t\t5、输出景区导游线路图\n\n");

　printf("\t\t\t6、导游线路图有无回路\n\n");

　printf("\t\t\t7、景点之间的最短路径\n\n");

　printf("\t\t\t8、输出道路修建规划图\n\n");

　printf("\t\t\t9、退出信息管理系统\n\n");

　printf("\t\t\t 请选择相应功能:");

　return 0; } int Menu() {

　GRAPH Graph;

　int Select;

　while(1)

　{

　system("cls");

　Frame();

　scanf("%d",&Select);

　system("cls");

　switch(Select)

　{

　case 1:

　 CreateGraph(&Graph);

　 break;

　case 2:

　 SaveGraph(&Graph);

　 break;

　 case 3:

　 ReadGraph(&Graph);

　 break;

　case 4:

　 PrintGraph(&Graph);

　 break;

　case 5:

　 TraverseGraph(&Graph);

　 break;

　case 6:

　 TopologicalSort(&Graph);

　 break;

　case 7:

　 MinShortPath(&Graph);

　 break;

　case 8:

　 MininumCST(&Graph);

　 break;

　case 9:

　 return 0;

　default:

　 break;

　}

　} } int main() {

　Menu();

　return 0; } 主界面:

　 创建景区景点分布图:

　输出景区景点分布图:

　 输出景区导游线路图:

　有向图的拓扑排序:

　 求两个景点间的最短路径:

　输出道路修建规划图:

　 1 、3 项目心得体会 通过本次景区旅游管理系统的开发,我对数据结构的图有了基本的了解、我对图这章的知识有了一个结构的框架,对于一些以前自己从未见过的算法有了一定的了解,并能够自己写出来,这就是对我能力的一种提高在编码方面、在开发这个系统时,遇到了很多的难题,例如:求最短路径等比较有难度的算法时不得不上网查大量的资料,结合书本上写的慢慢的理解,这真就是一个漫长的过程,可能有时一天也不能弄懂一个算法的本质、我凭着不放弃的心态,最终还就是克服了重重困难,解决了自己从未解决过的难题、这也就是自己的一个突破、在系统开发的过程中依然有一些本质性的问提没有解决,我现在没有过多的深究,但我相信我会在以后的学习中一一解决这些难题、例如:求顶点之间的最短路径我一直还不懂求 PATH 数组、 在系统开发的过程中我学到了很多的新的知识,最重要的就就是学会了一种思想、模块化思想,以前老师总就是提到我们以后写代码不必写那么多,拿来用就行,我一直不懂她的意思,原来就是当您的模块被集成之后,以后这些模块就可以不必写了可以直接引用、例如:这次我用到了桟与队列的知识,我以前就写过,如果我要就是重新去写又得花一定的时间,这并不就是一个好的习惯,我以前写过集成了我拿来用不就行了不,这样提高了编码的速度提高了效率、不过代码重用的考虑很多的东西,要求比较高、 总的来说这次系统开发我学到了很多、

推荐访问:管理系统 景区 旅游信息