景区旅游信息管理系统

校园旅游信息管理系统1.1项目需求分析在旅游景区，经常会碰到游客打听从一个景点到另一个景点的最短途径和最短距离，这类游客不喜欢按照导游图的线路来游览，而是挑选自己感爱好的景点游览。为于帮助这类游客信息查询，就需要计算出所有景点之间最短途径和最短距离。算法采用迪杰斯特拉算法或弗洛伊德算法均可。建立一个景区旅游信息管理系统，实现的重要功能涉及制订旅游景点导游线路策略和制订景区道路铺设策略。任务中景点分布是一个无向带权连通图，图中边的权值是景点之间的距离。

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

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

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

（4）在景区建设中，道路建设是其中一个重要内容。道路建设一方面要保证能连通所有景点，但又要花最小的代价，可以通过求最小生成树来解决这个问题。本任务中假设修建道路的代价只与它的里程相关。因此归纳起来，本任务有如下功能模块：

创建景区景点分布图；

输出景区景点分布图（邻接矩阵）

输出导游线路图；

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

求两个景点间的最短途径和最短距离；

输出道路修建规划图。

主程序用菜单选项供用户选择功能模块。1.2项目设计流程1.2.1项目总体框架校园旅游信息管理系统校园旅游信息管理系统创建景区景点分布图输出景区景点分布图输出景区导游线路图导游线路图有无回路两个景点间的最短路径输出道路修建规划图1.2.2项目数据结构#ifndefSUCCESS //标志位成功#defineSUCCESS 1#endif#ifndefFAILURE //标志位失败#defineFAILURE 0#endif#ifndefINF //标志位无穷#defineINF 0x3f3fffff#endif#ifndefMAXNUM#defineMAXNUM 20#endiftypedefboolSTATUS; //定义函数状态数据类型typedefcharVERTEXTYPE[MAXNUM][11]; //定义顶点向量数据类型typedefintADJMATRIX[MAXNUM][MAXNUM]; //定义邻接矩阵数据类型typedefstructGRAPH //定义图数据类型{ VERTEXTYPEVexs; //图的顶点向量 ADJMATRIXArcs; //图的邻接矩阵 intVexNum; //图的当前顶点 intArcNum; //图的当前弧}*PGRAPH; //定义图的指针数据类型typedefstructCLOSEDGE //定义辅助数组数据类型{ VERTEXTYPEVexs; //图的顶点向量 intLowcost[MAXNUM]; //}*PCLOSEDGE; //定义辅助数组指针数据类型1.2.3项目模块设计创建景区景点分布图邻接矩阵(AdjacencyMatrix)(二维数组表达法）在图的邻接矩阵表达中，有一个记录各个顶点信息的顶点表，尚有一个表达各个顶点之间关系的邻接矩阵。设图A=(V,E)是一个有n个顶点的图,图的邻接矩阵是一个二维数组A.edge[n][n]，定义(满足如下条件的n阶矩阵)：无向图数组表达法特点：1）无向图邻接矩阵是对称矩阵，同一条边表达了两次；2）顶点v的度：在无向图中档于二维数组相应行（或列）中1的个数；在有向图中,记录第i行1的个数可得顶点i的出度，记录第j列1的个数可得顶点j的入度。3）判断两顶点v、u是否为邻接点：只需判二维数组相应分量是否为1；4）顶点不变，在图中增长、删除边：只需对二维数组相应分量赋值1或清0；5）设存储顶点的一维数组大小为n(图的顶点数n),G占用存储空间：n+n2；G占用存储空间只与它的顶点数有关，与边数无关；合用于边稠密的图； 流程图：程序：//创建景区景点分布图STATUSCreateGraph(PGRAPHpGraph){ 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(); returnFAILURE; } //初始化图的弧数 printf("\t\t\t请输入图的弧度数(<=20)："); scanf("%d",&pGraph->ArcNum); //检查 if(pGraph->ArcNum>20) { printf("\t\t\t警告：输入数据错误！！！\n"); printf("\t\t\t按任意键回主菜单！！！"); getch(); returnFAILURE; } //初始化图的顶点名称 printf("\t\t\t---------------------------------\n"); printf("\t\t\t初始化的顶点名称......\n"); for(inti=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(intj=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++) { intStav,Endv,Weight; printf("\t\t\t请输入第%d条弧(格式：ViVjWeight)：",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(); returnSUCCESS;}输出景区景点分布图流程图：程序：//输出景区景点分布图STATUSPrintGraph(constPGRAPHpGraph){ printf("\t\t\t_________________________________\n"); printf("\n\t\t\t$\t显示景区景点分布图\t$\n"); printf("\t\t\t_________________________________\n\n"); // printf("\t景区景点名称......\n\t"); for(inti=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(intj=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(); returnSUCCESS;} 输出景区导游线路图图的遍历从图中某一顶点出发访遍图中所有的顶点，且使每个顶点仅被访问一次，这一过程就叫做图的遍历(TraversingGraph)。图中也许存在回路，且图的任一顶点都也许与其它顶点相通，在访问完某个顶点之后也许会沿着某些边又回到了曾经访问过的顶点。为了避免反复访问，可设立一个标志顶点是否被访问过的辅助数组visited[]。辅助数组visited[]的初始状态为0,在图的遍历过程中,一旦某一个顶点i被访问,就立即让visited[i]为1,防止它被多次访问。两种图的遍历方法:深度优先搜索DFS(DepthFirstSearch)广度优先搜索BFS(BreadthFirstSearch)广度优先搜索遍历图(BFS)对连通图，从起始点V到其余各顶点必然存在途径。其中，V->w1,V->w2,V->w8的途径长度为1;V->w7,V->w3,V->w5的途径长度为2;V->w6,V->w4的途径长度为3从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问过的邻接点，之后按这些顶点被访问的先后顺序依次访问它们的邻接点，直至图中所有和V0有途径相通的顶点都被访问到。若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点，反复上述过程，直至图中所有顶点都被访问到为止。流程图：程序：//输出景区导游线路图(注：广度优先遍历)STATUSTraverseGraph(constPGRAPHpGraph){ 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(inti=0;i<pGraph->VexNum;i++) Visit[i]=false; //定义队列、并初始化队列 QUEUEQueue; if(InitQueue(&Queue,pGraph->VexNum)==FAILURE) { printf("\t\t\t警告：创建队列失败！！！\n"); printf("\t\t\t按任意键回主菜单！！！"); getch(); returnFAILURE; } //定义访问顶点变量，并初始值为0 intVertex=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(); returnSUCCESS;}有向图的拓扑排序何谓“拓扑排序”？对有向图进行如下操作:假设G=(V，E)是一个具有n个顶点的有向图，V中顶点序列vl，v2，…，vn称做一个拓扑序列(TopologicalOrder)，当且仅当该顶点序列满足下列条件：若在有向图G中存在从顶点vi到vj的一条途径，则在顶点序列中顶点vi必须排在顶点vj之前。通常，在AOV网中，将所有活动排列成一个拓扑序列的过程叫做拓扑排序(TopologicalSort)。在AOV网中不应当出现有向环。由于环的存在意味着某项活动将以自己为先决条件，显然无法形成拓扑序列。鉴定网中是否存在环的方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都出现在它的拓扑有序序列中，则该AOV网中一定不存在环。例如：对于有向图可求得拓扑有序序列：ABCD或ACBDBBcDA cDA例如,对学生选课工程图进行拓扑排序,得到的拓扑有序序列为C1,C2,C3,C4,C5,C6,C8,C9,C7或C1,C8,C9,C2,C5,C3,C4,C7,C6反之，对于下列有向图不能求得它的拓扑有序序列。由于图中存在一个回路{B,C,D}如何进行？输入AOV网络。令n为顶点个数。（1）在AOV网络中选一个没有直接前驱的顶点，并输出之；（2）从图中删去该顶点,同时删去所有它发出的有向边；反复以上环节，直到所有顶点均已输出，拓扑有序序列形成，拓扑排序完毕；或图中尚有未输出的顶点，但已跳出解决循环。这说明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了。这时AOV网络中必然存在有向环。在实现拓扑排序的算法中，采用邻接表作为有向图的存储结构，每个顶点设立一个单链表，每个单链表有一个表头结点，在表头结点中增长一个存放顶点入度的域count，这些表头结点构成一个数组。为了避免反复检测入度为0的点，另设一栈存放所有入度为0的点。对于有n个顶点和e条边的有向图而言，for循环中建立入度为0的顶点栈时间为O（n）；若在拓扑排序过程中不出现有向环，则每个顶点出栈、入栈和入度减1的操作在while循环语句中均执行e次，因此拓扑排序总的时间花费为O(n+e)。流程图:程序://有向图的拓扑排序STATUSTopologicalSort(constPGRAPHpGraph){ printf("\t\t\t_________________________________\n"); printf("\n\t\t\t$\t导游线路图有无回路\t$\n"); printf("\t\t\t_________________________________\n\n"); //定义入度数组,记录每个顶点的入度，初始化为0 intIndegree[MAXNUM]={0}; //定义桟、并初始化桟 STACKStack; if(InitStack(&Stack,pGraph->VexNum)==FAILURE) { printf("\t\t\t警告：创建桟失败！！！\n"); printf("\t\t\t按任意键回主菜单！！！"); getch(); returnFAILURE; } printf("\t\t\t计算各顶点的入度.....\n"); for(intj=0;j<pGraph->VexNum;j++) { //求各个顶点的入度 for(inti=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的顶点个数 intCount=0,k; while(StackLen(&Stack)) { //出桟、并访问 PopStack(&Stack,&k); printf("%s\t",pGraph->Vexs[k]); Count++; //对出栈的顶点所指向的顶点减一，并且将入度为0的顶点入栈 for(inti=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(); returnSUCCESS;}求两个景点间的最短途径最短途径定义

所谓最短途径问题是指：假如从图中某一顶点（源点）到达另一顶点（终点）的途径也许不止一条，如何找到一条途径似的沿此途径上各边的权值总和（称为途径长度）达成最小。迪杰斯特拉(Dijkstra)算法求单源最短途径

由Dijkstra提出的一种按途径长度递增序产生各顶点最短途径的算法。

（1）按途径长度递增序产生各顶点最短途径

若按长度递增的顺序生成从源点s到其它顶点的最短途径，则当前正在生成的最短途径上除终点以外，其余顶点的最短途径均已生成（将源点的最短途径看作是已生成的源点到其自身的长度为0的途径）。（2）具体做法

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

假设有向图G的n个顶点为1到n,并用邻接矩阵cost表达,若<vi,vj>是图G中的边，则cost[i][j]的值等于边所带的权;若<vi,vj>不是图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作为其前一个顶点序号。流程图:程序://求两个景点间的最短途径STATUSMinShortPath(constPGRAPHpGraph){ printf("\t\t\t_________________________________\n"); printf("\n\t\t\t$\t景点之间的最短途径\t$\n"); printf("\t\t\t_________________________________\n\n"); //定义途径矩阵、距离矩阵 ADJMATRIXPathMatrix,DisMatrix; //定义辅助变量 inti,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; } //定义起点、终点 intStav=-1,Endv=-1; //定义起点、终点名称 charStaNam[MAXNUM],EndNam[MAXNUM]; printf("\t\t\t输入起始点和终点名称(格式：StaEnd)："); 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) returnFAILURE; //定义桟、并初始化 STACKStack; 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(); returnSUCCESS;}输出道路修建规划图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来描述所得到的最小生成树。例如:流程图:程序://输出道路修建规划图(注：最小生成树)STATUSMininumCST(constPGRAPHpGraph){ printf("\t\t\t_________________________________\n"); printf("\n\t\t\t$\t输出道路修建规划图\t$\n"); printf("\t\t\t_________________________________\n\n"); //定义辅助数组变量 CLOSEDGEClosedge; intMin=0; //初始化辅助数组,从第一个顶点开始 for(inti=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(intj=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(); returnSUCCESS;}1.3项目编码实现#include<stdio.h>#include<stdlib.h>#include"Graph.h"intFrame(){ 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