图与景区管理系统
功能简介
| 序号 | 功能 | 实现原理 |
|---|---|---|
| 1 | 创建景区景点图 | 文件读写、结构体 |
| 2 | 查询景点信息 | 边的关系 |
| 3 | 旅游景点导航 | 链表、深度优先搜索 |
| 4 | 搜索最短路径 | Dijkstra算法、最短路径 |
| 5 | 铺设电路规划 | Prim算法、最小生成树 |
| 0 | 退出 | exit(0) |
源代码(Visual Studio 2017下)
数据结构头文件
Graph.h
#ifndef GRAPH_H
#define GRAPH_H
struct Vex
{
int num;//景点编号
char name[20];//景点名字
char desc[1024];//景点介绍
};
struct Edge
{
int vex1;//边的第一个顶点
int vex2;//边的第二个顶点
int weight;//权值
};
struct Graph
{
int m_aAdjMatrix[20][20];//邻接矩阵
Vex m_aVexs[20];//顶点信息组数
int m_nVexNum;//当前图的顶点个数
};
typedef struct Path
{
int vexs[20];//保存一条路径
Path *next;//下一条路径
}*PathList;//链表PathList用来保存所有路径
void Init(void);
bool InsertVex(Vex sVex);
bool InsertEdge(Edge sEdge);
Vex GetVex(int nVex);
int FindEdge(int nVex, Edge aEdge[]);
int GetVexnum(void);
void DFS(int nVex, bool isVisited[], int &nIndex, PathList &pList);
void DFSTraverse(int nVex,PathList &pList);
bool TraverseOrNot(int now[], int i);
int FindShortPath(int nVexStart, int nVexEnd, Edge aPath[]);
int FindMinTree(Edge aPath[]);
#endif GRAPH_H
数据结构源文件Graph.cpp
#include"Graph.h"
#include<iostream>
using namespace std;
Graph graph;
int EdgeNum;
Edge aEdge[100];
int allPath[20][20] = {0};
int PathNum=0;
//bool isVisited[20];
bool TraverseOrNot(int now[], int i)
{
for (int p = 0; p < PathNum; p++)
{
for (int q = 0; q < i; q++)
{
if (allPath[p][q] != now[q])
{
break;
}
if ((allPath[p][q] == now[q] && q == i))
return true;//曾被访问
}
}
return false;
}
void Init(void)
{
for (int i = 0; i < 20; i++)
{
for (int j = 0; j < 20; j++)
{
if (i == j)
graph.m_aAdjMatrix[i][j] = 0;
else
graph.m_aAdjMatrix[i][j] = 0xffff;
}
}
graph.m_nVexNum = 0;
}
bool InsertVex(Vex sVex)
{
if (graph.m_nVexNum >= 20)
{//顶点已满
return false;
}
graph.m_aVexs[graph.m_nVexNum++] = sVex;
return true;
}
bool InsertEdge(Edge sEdge)
{
if (sEdge.vex1 == sEdge.vex2)
return false;
graph.m_aAdjMatrix[sEdge.vex1][sEdge.vex2] = sEdge.weight;
graph.m_aAdjMatrix[sEdge.vex2][sEdge.vex1] = sEdge.weight;
return true;
}
Vex GetVex(int nVex)
{
return graph.m_aVexs[nVex];
}
/*
int FindEdge(int nVex, Edge aEdge[])
{
for (int i = 0; i < EdgeNum; i++)
{
if (aEdge[i].vex1 == nVex)
{
cout << graph.m_aVexs[aEdge[i].vex1].name << "->" << graph.m_aVexs[aEdge[i].vex2].name << " " << aEdge[i].weight << endl;
}
if(aEdge[i].vex2 == nVex)
cout << graph.m_aVexs[aEdge[i].vex2].name << "->" << graph.m_aVexs[aEdge[i].vex1].name << " " << aEdge[i].weight << endl;
}
return true;
}
*/
int FindEdge(int nVex, Edge aEdge[])
{
int k = 0;
for (int i = 0; i < graph.m_nVexNum; i++)
{
if (graph.m_aAdjMatrix[i][nVex] > 0 && graph.m_aAdjMatrix[i][nVex] < 0xffff)
{
aEdge[k].vex1 = nVex;
aEdge[k].vex2 = i;
aEdge[k].weight = graph.m_aAdjMatrix[i][nVex];
k++;
}
}
return k;
}
int GetVexnum(void)
{
return graph.m_nVexNum;
}
/*
//输出一行的深度优先搜索
void DFS(int nVex, bool isVisited[], int &nIndex, PathList &pList)
{//nIndex记录遍历的深度
if (nIndex == graph.m_nVexNum - 1)
pList->next = NULL;
isVisited[nVex] = true;
pList->vexs[nIndex++] = nVex;
for (int i = 0; i < graph.m_nVexNum; i++)
{
if (graph.m_aAdjMatrix[nVex][i] > 0 && graph.m_aAdjMatrix[nVex][i] < 0xffff && !isVisited[i]&&pList->next)
{
DFS(i, isVisited, nIndex, pList);//递归调用DFS
isVisited[i] = false;
nIndex--;
}
}
}
*/
void DFS(int nVex, bool isVisited[], int &nIndex, PathList &pList)
{//nIndex记录遍历的深度
//if (nIndex == graph.m_nVexNum -1 && TraverseOrNot(pList->vexs, graph.m_nVexNum))
//{
// nIndex--;
//}
isVisited[nVex] = true;
pList->vexs[nIndex++] = nVex;
//判断是否所有的顶点都已被访问过
int nVexNum = 0;
for (int i = 0; i < graph.m_nVexNum; i++)
{
if (isVisited[i])
nVexNum++;
}
if (nIndex == graph.m_nVexNum )
{
pList ->next= (PathList)malloc(sizeof(Path));
for (int i = 0; i < graph.m_nVexNum; i++)
{
pList->next->vexs[i] = pList->vexs[i];
}
pList = pList->next;
pList->next = NULL;
}
else
{
for (int i = 0; i < graph.m_nVexNum; i++)
{
if (graph.m_aAdjMatrix[nVex][i] > 0 && graph.m_aAdjMatrix[nVex][i] < 0xffff && !isVisited[i])
{
DFS(i, isVisited, nIndex, pList);//递归调用DFS
isVisited[i] = false;
nIndex--;
}
}
}
}
void DFSTraverse(int nVex, PathList &pList)
{
int nIndex = 0;
bool isVisited[20] = { false };
DFS(nVex, isVisited, nIndex, pList);
}
int FindShortPath(int nVexStart, int nVexEnd, Edge aPath[])
{
int nShortPath[20][20];//保存最短路径
int nShortDistance[20];//保存最短距离
bool isVisited[20];//判断某顶点是否已加入到最短路径
int v;
//初始化
for (v = 0; v < graph.m_nVexNum; v++)
{
isVisited[v] = false;
if (graph.m_aAdjMatrix[nVexStart][v])
{
//初始化该顶点到其他顶点的最短距离，默认为两顶点间的距离
nShortDistance[v] = graph.m_aAdjMatrix[nVexStart][v];
}
else
{
//如果两顶点v和nVexStart不相连，则最短距离为最大值
nShortDistance[v] = 0xffff;
}
nShortPath[v][0] = nVexStart;//起始点为nVexStart
for (int w = 1; w < graph.m_nVexNum; w++)
{
nShortPath[v][w] = -1;//初始化最短路径
}
}
//初始化，nVexStart顶点加入到集合中
isVisited[nVexStart] = true;
int min;
for (int i = 1; i < graph.m_nVexNum; i++)
{
min = 0xffff;
bool bAdd = false;//判断是否还有顶点可以加入集合
for (int w = 0; w < graph.m_nVexNum; w++)
{
if (!isVisited[w])
{
if (nShortDistance[w] < min)
{
v = w;//顶点离nVexStart最近
min = nShortDistance[w];//最短距离为min
bAdd = true;
}
}
}
//如果没有顶点可加入集合,则跳出循环
if (!bAdd)
{
break;
}
isVisited[v] = true;//将w顶点加入到集合
nShortPath[v][i] = v;
for (int w = 0; w < graph.m_nVexNum; w++)
{
if (!isVisited[w] && (min + graph.m_aAdjMatrix[v][w] < nShortDistance[w]) /*&& (min + graph.m_aAdjMatrix[v][w]) < 0xffff*/)
{
//更新当前最短路径及距离
nShortDistance[w] = min + graph.m_aAdjMatrix[v][w];
for (int i = 0; i < graph.m_nVexNum; i++)
{
//如果通过w到达顶点i的距离比较短，则将w的最短路径复制给i
nShortPath[w][i] = nShortPath[v][i];
}
}
}
for (int p = 0; p < graph.m_nVexNum; p++)
{
for (int j = 0; j < graph.m_nVexNum; j++)
{
cout<<nShortPath[p][j]<<" ";
}
cout << endl;
}
cout << endl;
}
int nNum=0;
int finalpath[20];
int onlypath[20] = { 0 };
int q = 0;
for (int i = 0; i < graph.m_nVexNum; i++)
{
finalpath[i] = nShortPath[nVexEnd][i];
}
for (int i = 0; i < graph.m_nVexNum; i++)
{
if (finalpath[i] != -1)
{
nNum++;
onlypath[q++] = finalpath[i];
}
}
for (int i = 0; i < nNum-1; i++)
{
aPath[i].vex1 = onlypath[i];
aPath[i].vex2 = onlypath[i + 1];
// aPath[i].weight = nShortDistance[onlypath[i+1]];
aPath[i].weight = graph.m_aAdjMatrix[aPath[i].vex1][aPath[i].vex2];
// if (i > 0)
// {
// aPath[i].weight = nShortDistance[onlypath[i + 1]] - nShortDistance[onlypath[i]];
// }
}
return nNum;
}
/*
int FindMinTree(Edge aPath[])
{
int before,after;//before为前一个已访问的点，after为下一个将要访问的点
int lowcost[20];//保存着未被访问即（V-U）中编号为k的顶点到U中所有顶点的最小权值
int closest[20];//保存着U中到V-U中编号为K的顶点权值最小的编号
int used[20];//保存某点是否已经被访问
int min;
for (int i = 0; i < graph.m_nVexNum; i++)
{
lowcost[i] = graph.m_aAdjMatrix[0][i];//到i点的最小距离即为a点到i点的距离
closest[i] = 0;//到i点最小距离的点是a点
used[i] = 0;//所有点都未被访问
}
used[0] = 1;//a点已被访问
before = 0;
after = 0;
for (int i = 0; i < graph.m_nVexNum - 1; i++)
{
min = 0xffff;
for (int k = 1; k < graph.m_nVexNum; k++)
{
if (used[k] == 0 && lowcost[k] < min)
{
min = lowcost[k];
after = k;
}
}
cout << "before = " << before << " after = " << after << endl;
used[after] = 1;//j点已加入U集合
aPath[i].vex1 = before;
aPath[i].vex2 = after;
aPath[i].weight = graph.m_aAdjMatrix[before][after];
for (int j = 0; j < graph.m_nVexNum; j++)
{
for (int k = 0; k < graph.m_nVexNum; k++)
{
if ((used[j]==1)&&(used[k] == 0) && (graph.m_aAdjMatrix[j][k] < lowcost[k]))
{
lowcost[k] = graph.m_aAdjMatrix[j][k];
closest[k] = after;
before = j;
}
}
}
}
for (int i = 0; i < graph.m_nVexNum - 1; i++)
{
cout << aPath[i].vex1 << " -> " << aPath[i].vex2 << " " << aPath[i].weight << endl;
}
int sum = 0;
for (int i = 0; i < graph.m_nVexNum - 1; i++)
{
cout << graph.m_aVexs[aPath[i].vex1].name << " - " << graph.m_aVexs[aPath[i].vex2].name << " " << aPath[i].weight << endl;
sum += aPath[i].weight;
}
cout << endl << endl << "pop stack!" << endl;
return 0;
}
*/
int FindMinTree(Edge aPath[])
{
int before, after;//before为前一个已访问的点，after为下一个将要访问的点
int used[20];//保存某点是否已经被访问
int min;
for (int i = 0; i < graph.m_nVexNum; i++)
{
used[i] = 0;//所有点都未被访问
}
used[0] = 1;//a点已被访问
before = 0;
after = 0;
for (int i = 0; i < graph.m_nVexNum - 1; i++)
{
min = 0xffff;
for (int j = 0; j < graph.m_nVexNum; j++)
{
for (int k = 0; k < graph.m_nVexNum; k++)
{
if ((used[j] == 1) && (used[k] == 0) && (graph.m_aAdjMatrix[j][k] < min))
{
min = graph.m_aAdjMatrix[j][k];
before = j;
after = k;
}
}
}
// cout << i << "." << "before = " << before << " after = " << after << endl;
used[after] = 1;//j点已加入U集合
aPath[i].vex1 = before;
aPath[i].vex2 = after;
aPath[i].weight = graph.m_aAdjMatrix[before][after];
}
return 0;
}
操作实现头文件Tourism.h
#ifndef TOURISM_H
#define TOURISM_H
void CreateGraph(void);
void GetSpotInfo(void);
void TravelPath(void);
void FindShortPath(void);
void DesignPath(void);
#endif
操作实现源文件Tourism.cpp
#include"Tourism.h"
#include"Graph.h"
#include<iostream>
using namespace std;
extern Graph graph;
extern int EdgeNum;
extern Edge aEdge[100];
//extern bool isVisited[20];
#pragma warning (disable : 4996)
void CreateGraph(void)
{
Init();
FILE *fp = NULL;
fp = fopen("Vex.txt", "r");
if (!fp)
{
printf("Failed to open the file!");
exit(-1);
}
int num;
Vex sVex;
fscanf(fp, "%d", &num);
cout << "===== 创建景区景点图 =====" << endl;
cout << "顶点数目：" << num<<endl;
cout << "----- 顶点 -----" << endl;
for (int i = 0; i < num; i++)
{
fscanf(fp, "%d", &sVex.num);
fscanf(fp, "%s", &sVex.name);
fscanf(fp, "%s", &sVex.desc);
cout << sVex.num << "-" << sVex.name << endl;
InsertVex(sVex);
}
fclose(fp);
fp = fopen("Edge.txt", "r");
if (!fp)
{
printf("Failed to open this file!");
exit(-1);
}
Edge sEdge;
cout << "----- 边 -----" << endl;
EdgeNum = 0;
while (!feof(fp))
{
// printf("!!!");
fscanf(fp, "%d", &sEdge.vex1);
fscanf(fp, "%d", &sEdge.vex2);
fscanf(fp, "%d", &sEdge.weight);
printf("<v%d,v%d> %d
", sEdge.vex1, sEdge.vex2, sEdge.weight);
InsertEdge(sEdge);
aEdge[EdgeNum++] = sEdge;
}
fclose(fp);
cout << endl << endl;
}
void GetSpotInfo(void)
{
cout << "===== 查询景点信息 =====" << endl;
for (int i = 0; i < graph.m_nVexNum; i++)
{
cout << graph.m_aVexs[i].num << "-" << graph.m_aVexs[i].name << endl;
}
int nVex;
cout << "输入想要查询的景点编号: ";
cin >> nVex;
Vex sVex=GetVex(nVex);
printf("%s
%s
", sVex.name,sVex.desc);
cout << "----- 周边景区 -----" << endl;
int k = FindEdge(nVex, aEdge);
for (int i = 0; i < k; i++)
{
cout << graph.m_aVexs[aEdge[i].vex1].name << "->" << graph.m_aVexs[aEdge[i].vex2].name << " " << aEdge[i].weight <<"m"<< endl;
}
cout << endl << endl;
}
void TravelPath(void)
{
PathList pList;
pList = (Path*)malloc(sizeof(Path));
PathList PHead;
PHead = pList;
// pList->next = (Path*)malloc(sizeof(Path));
cout << "===== 旅游景点导航 =====" << endl;
for (int i = 0; i < graph.m_nVexNum; i++)
{
cout << graph.m_aVexs[i].num << "-" << graph.m_aVexs[i].name << endl;
}
cout << "请输入起始点编号：";
int nVex;
cin >> nVex;
DFSTraverse(nVex, pList);
cout << "导航路线为: " << endl;
// cout << "路线1 : ";
// cout<<graph.m_aVexs[nVex].name;
pList = PHead;
int i = 1;
while (pList->next)
{
Vex sVex = GetVex(pList->vexs[0]);
cout << "路线" << i++ << ":" << sVex.name;
for (int j = 1; j<graph.m_nVexNum; j++)
{
printf(" -> %s", graph.m_aVexs[pList->vexs[j]].name);
// sVex = GetVex(pList->vexs[j]);
// cout << " -> " << sVex.name;
}
cout << endl;
Path *temp = pList;
pList = pList->next;
free(temp);
}
free(pList);
pList = NULL;
PHead = NULL;
cout << endl<<endl<<endl;
// free(pList);
// free(pList->next);
}
void FindShortPath(void)
{
cout << "===== 搜索最短路径 =====" << endl;
for (int i = 0; i < graph.m_nVexNum; i++)
{
cout << graph.m_aVexs[i].num << "-" << graph.m_aVexs[i].name << endl;
}
int nVexStart;
int nVexEnd;
cout << "请输入起点的编号: ";
cin >> nVexStart;
cout << "请输入终点的编号: ";
cin >> nVexEnd;
Edge aPath[20];
int nNum=FindShortPath(nVexStart, nVexEnd, aPath);
Vex sVex = GetVex(aPath[0].vex1);
int nLength = 0;
cout << "最短路线为: ";
cout << graph.m_aVexs[nVexStart].name;
for (int i = 0; i < nNum-1; i++)
{
sVex = GetVex(aPath[i].vex2);
cout << "->" << sVex.name;
nLength += aPath[i].weight;
}
cout << endl;
cout << "最短距离为： " << nLength << endl;
cout << endl << endl;
}
void DesignPath(void)
{
cout << "===== 铺设电路规划 =====" << endl;
cout << "在以下两个景点之间铺设电路：" << endl;
Edge aPath[20];
FindMinTree(aPath);
int sum=0;
for (int i = 0; i < graph.m_nVexNum - 1; i++)
{
cout << graph.m_aVexs[aPath[i].vex1].name << " - " << graph.m_aVexs[aPath[i].vex2].name << " " << aPath[i].weight << endl;
sum += aPath[i].weight;
}
cout << "铺设电路的总长度为：" << sum;
cout << endl << endl << endl;
}
主函数源文件Main.cpp
#include<iostream>
#include"Tourism.h"
using namespace std;
#pragma warning( disable : 4996)
int main()
{
while (true)
{
//输出界面
cout << "====景区信息管理系统====" << endl;
cout << "1.创建景区景点图" << endl;
cout << "2.查询景点信息" << endl;
cout << "3.旅游景点导航" << endl;
cout << "4.搜索最短路径" << endl;
cout << "5.铺设电路规划" << endl;
cout << "0.退出" << endl;
int choice;
cout << "请输入操作编号<0~5>: ";
cin >> choice;
switch (choice)
{
case 1:
{
CreateGraph();
break;
}
case 2:
{
GetSpotInfo();
break;
}
case 3:
{
TravelPath();
break;
}
case 4:
{
FindShortPath();
break;
}
case 5:
{
DesignPath();
break;
}
case 0:
{
cout << "退出系统!" << endl;
exit(0);
}
default:
{
cout << "请输入操作编号<0~5>: ";
break;
}
}
}
return 0;
}