0001：图的操作和应用之景区信息管理系统（C++版数据结构课程设计）
现有一个景区，景区里面有若干个景点，景点之间满足以下条件：
(1) 某些景点之间铺设了道路（相邻）
(2) 这些道路都是可以双向行驶的（无向图）
(3) 从任意一个景点出发都可以游览整个景区（连通图）
开发景区信息管理系统，对景区的信息进行管理。使用图的数据结构来保存景区景点信息，为用户提供创建图、查询景点信息、旅游景点导航、搜索最短路径、铺设电路规划等功能。
@TOC
前言
数据结构是计算机学科实践性很强的一门核心课程。课程设计是加强学生实践能力的一个强有力手段，要求学生掌握数据结构的应用、算法的编写、类C语言的算法转换成C/C++/Java程序并上机调试的基本方法，还要求学生在完成程序设计的同时能够写出比较规范的设计报告。严格实施课程设计这一环节，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将起到显著的促进作用。
一、设计要求
1.景区信息路线图
景区路线图
景区信息
2.设计要求
(1) 读文件创建图
输入：从Vex.txt文件中读取景点信息，从Edge.txt文件中读取道路信息。
处理：根据读取的景区信息创建景区景点图。
(2) 查询景点
输入：想要查询的景点的编号。
处理：根据输入的景点编号，查询该景点及相邻景点的信息。
输出：
① 景点名字
② 景点介绍
③ 相邻景区的名字
④ 到达相邻景区的路径长度
(3) 旅游景点导航
输入：起始景点的编号。
处理：使用深度优先搜索(DFS)算法，查询以该景点为起点，无回路游览整个景区的路线。
输出：所有符合要求的导航路线。
(4) 搜索最短路径
输入：
① 起始景点的编号
② 终点的编号。
处理：使用迪杰斯特拉(Dijkstra)算法，求得从起始景点到终点之间的最短路径，计算路径总长度。
输出：
① 最短路线
② 路径总长度
(5) 铺设电路规划
处理：根据景区景点图使用普里姆(Prim)算法构造最小生成树，设计出一套铺设线路最短，但能满足每个景点都能通电的方案。
输出：
① 需要铺设电路的道路
② 每条道路铺设电路的长度
③ 铺设电路的总长度
(6) 修改图保存文件
插入、删除、修改顶点、边的信息，注意顶点和边的关系，之后保存文件，重新读取文件建立图的存储结构并显示。
重点注意顶点和边的关系，考虑边是否重复？顶点是否存在？……
二、关键代码
1.类的设计
点的类 Node.h：
#ifndef NODE_H_INCLUDED #define NODE_H_INCLUDED #include <iostream> #include <sstream> #include <string> using namespace std; class Node { public: bool visited; Node(int number=-1,string name=" ",string introduction=" "); int m_number; string m_name; string m_introduction; //void SeekNode(int number); }; #endif // NODE_H_INCLUDED
边的类 Edge.h：
#ifndef EDGE_H_INCLUDED #define EDGE_H_INCLUDED #include <iostream> class Edge { public: Edge(int nodeIndexA=0,int nodeIndexB=0,int weightValue=0); int m_iNodeIndexA; int m_iNodeIndexB; int m_iWeightValue; bool m_bSelected; }; #endif // EDGE_H_INCLUDED
图的类 Map.h：
#ifndef MAP_H_INCLUDED #define MAP_H_INCLUDED #include <vector> #include "Node.h" #include "Edge.h" using namespace std; class Map { public: Map(int capacity); ~Map(); bool addNode(Node *pNode);// 向图中添加顶点 void resetNode();//重置顶点 bool setValueToMatrixForUndirectedGraph(int row,int cli,int val=1);//设置邻接矩阵 void printMatrix();//打印邻接矩阵 void DFS(int nodeIndex,int beginNum);//深度优先遍历 void seekNode(int number);//查询景点 void mapDFS(int nodeIndex);//旅游景点导航 void primTree(int nodeIndex);//普利姆算法生成树 void Dijkstra(int v0,int v1);//迪杰斯特拉算法 bool hasNode(string nodeName); bool hasEdge(int NodeAnum,int NodeBnum); private: bool getValueFromMatricx(int row,int col,int &val);//从矩阵中获取权值 void breadthFirstTraverseImpl(vector <int> preVec);//广度优先遍历实现函数 int getMinEdge(vector<Edge> edgeVec); private: int m_iCapacity;//最多可以容纳的顶点数 int m_iNodeCount; //已经添加的顶点个数 Node *m_pNodeArray;//用来存放顶点数组 int *m_pMatrix; //用来存放邻接矩阵 Edge *m_pEdge;//用来存放边数组 }; #endif // MAP_H_INCLUDED
2.重要算法
迪杰斯特拉（Dijkstra）算法函数：
void Map::Dijkstra(int v0,int v1) { int dist[m_iCapacity]; int path[m_iCapacity]; bool final[m_iCapacity]; dist[v0]=0; path[v0]=v0; for(int i=1;i<m_iCapacity;i++) { if(m_pMatrix[v0*m_iCapacity+i]!=0) { dist[i]=m_pMatrix[v0*m_iCapacity+i]; } else { dist[i]=100000; } path[i]=v0; final[i]=false; } for(int i=0;i<m_iCapacity;i++) { int minds=100000; int ind=10000; for(int j=0;j<m_iCapacity;j++){//寻找目前的路径距离中最小的一个 if(!final[j]&&dist[j]<minds){ minds=dist[j]; ind=j; } } final[ind]=true; for(int j=0;j<m_iCapacity;j++) {//更新dist if(m_pMatrix[ind*m_iCapacity+j]!=0&&!final[j]&&(minds+m_pMatrix[ind*m_iCapacity+j])<dist[j]) { dist[j]=minds+m_pMatrix[ind*m_iCapacity+j]; path[j]=ind; } } } //路线规划 倒置的 int endNum=v1; vector <int> ewayNum; while(1) { if(path[endNum]!=v0) { ewayNum.push_back(endNum); endNum=path[endNum]; } if(path[endNum]==v0) { ewayNum.push_back(endNum); break; } } //转换成正置路线 int wayNum[ewayNum.capacity()]; for(int i=0;i<(int)ewayNum.capacity();i++) { wayNum[i]=ewayNum[ewayNum.capacity()-1-i]; } //输出正置路线 cout<<v0<<endl; for(int i=0;i<(int)ewayNum.capacity();i++) { cout<<wayNum[i]<<endl; } cout<<dist[v1]<<endl; }
普利姆（Prim）算法函数：
void Map::primTree(int nodeIndex) { int AllWeightValue=0; int value=0; int edgeCount=0; vector <int> nodeVec; vector <Edge> edgeVec; //cout<<m_pNodeArray[nodeIndex].m_name<<endl; nodeVec.push_back(nodeIndex); m_pNodeArray[nodeIndex].visited=true; while(edgeCount<m_iCapacity-1) { int temp=nodeVec.back(); for(int i=0;i<m_iCapacity;i++) { getValueFromMatricx(temp,i,value); if(value!=0) { if(m_pNodeArray[i].visited) { continue; } else { Edge edge(temp,i,value); edgeVec.push_back(edge); } } } //从可选边集合中选出最小边 int edgeIndex=getMinEdge(edgeVec); edgeVec[edgeIndex].m_bSelected=true; cout<<edgeVec[edgeIndex].m_iNodeIndexA<<"---"<<edgeVec[edgeIndex].m_iNodeIndexB<<" "; cout<<edgeVec[edgeIndex].m_iWeightValue<<endl; AllWeightValue+=edgeVec[edgeIndex].m_iWeightValue; m_pEdge[edgeCount]=edgeVec[edgeIndex]; edgeCount++; int nextNodeIndex=edgeVec[edgeIndex].m_iNodeIndexB; nodeVec.push_back(nextNodeIndex); m_pNodeArray[nextNodeIndex].visited=true; // cout<<m_pNodeArray[nextNodeIndex].m_introduction<<endl; } cout<<AllWeightValue<<endl; for(int j=0;j<m_iCapacity-1;j++) { m_pNodeArray[j].visited=false; } }
三、运行截图
1.主界面
在这里插入图片描述
2.输出邻接矩阵
在这里插入图片描述
3.查询景点
在这里插入图片描述
4.旅游景点导航（路径搜索）
在这里插入图片描述
5.搜索最短路径（迪杰斯特拉算法）
在这里插入图片描述
6.铺设电路规划（普利姆算法求最小生成树）
在这里插入图片描述
7.动态操作（对景点或者边增删改）
如需要本资源下载也可以直接添加作者QQ，并可以获取资源预览、软件安装、工程导入、协助运行、算法解释、报告协助撰写等售后服务
随时在线，欢迎交流
QQ：2215991436（心源易码 派大星）
备用QQ：402501817（心源易码 佩奇）
