数据结构与算法综合实验—图与景区信息管理系统实践

这是武汉理工大学计算机学院数据结构与算法综合实验课程的第二次综合实验：图与景区信息管理系统实践的源代码。运行环境：VS2017。

#include
#include“Graph.h“
using namespace std;

//m_Graph图结构已经在主函数中定义，此处调用其
extern Graph m_Graph;

//初始化图结构
int Init（）
{
	for （int i = 0; i < 20; i++） {
		for （int j = 0; j < 20; j++） {
			m_Graph.m_aAdjMatrix[i][j] = 0;	//邻接矩阵置零
		}
		m_Graph.m_nVexNum = 0;				//景点数目置零
	}
	return OK;
}

//将顶点添加到数组中
int InsertVex（Vex sVex）
{ 
	//顶点已满
	if （m_Graph.m_nVexNum == 20）
		return ERROR;      
	//
	m_Graph.m_aVexs[m_Graph.m_nVexNum++] = sVex;
	return OK;
}

//将边保存到邻接矩阵中
int InsertEdge（Edge sEdge）
{ 
	//下标越界
	if （sEdge.vex1<0 || sEdge.vex1 >= 20 || sEdge.vex2<0 || sEdge.vex2 >= 20）
		return ERROR;  
	m_Graph.m_aAdjMatrix[sEdge.vex1][sEdge.vex2] = sEdge.weight;
	m_Graph.m_aAdjMatrix[sEdge.vex2][sEdge.vex1] = sEdge.weight;

	return OK;
}

//查询指定顶点信息
Vex GetVex（int nVex）
{
	return m_Graph.m_aVexs[nVex];
}

//查询与指定顶点相连的边
int FindEdge（int nVex Edge aEdge[]）
{
	int flag = 0;  //与景点n相邻的边的条数
	//便利整个图的邻接矩阵
	for （int j = 0; j < 20; j++） {
		if （m_Graph.m_aAdjMatrix[nVex][j] != 0 && nVex!=j） {
			aEdge[flag].vex1 = nVex;
			aEdge[flag].vex2 = j;
			aEdge[flag].weight = m_Graph.m_aAdjMatrix[nVex][j];
			flag++;
		}
	}
	return flag;
}

//获取当前顶点数
int GetVexmun（）{
	return m_Graph.m_nVexNum;
}

//实现图的深度优先搜索遍历
void DFS（int nVex bool bVisited[] int & nIndex PathList & pList）
{
	bVisited[nVex] = true;				//改为已访问
	pList->vexs[nIndex++] = nVex;		//访问顶点nVex并赋值给链表，然后索引值自加

	//判断所有的顶点是否都已经被访问过									
	int v_num = 0;
	for （int i = 0; i	{
		//如果当前i节点被访问过，则V-Num自加
		if （bVisited[i]）
			v_num++;
	}
	
	//所有的顶点都已经被访问过新增链表结点保存此次的路径。必须保存，不然在后续的递归中会存在重复使用的vex，导致有的路径结点中vex没有值
	if （v_num == m_Graph.m_nVexNum）
	{		
		//创建一个新链表，将当前的pList中的数据保存起来
		pList->next = new Path;
		for （int i = 0; i		{
			pList->next->vexs[i] = pList->vexs[i];
		}
		pList = pList->next;		//pList指针继续往下移动，寻找下一条路径
		pList->next = NULL;			//next赋值为空
	}
	//并没有全部访问，则进行寻找下一个相邻节点的操作
	else
	{
		for （int i = 0; i		{
			//如果i是nVex的的邻接点  并且未被访问
			if （!bVisited[i] && m_Graph.m_aAdjMatrix[nVex][i]>0）	
			{
				DFS（i bVisited nIndex pList）;			//递归调用DFS
				bVisited[i] = false;						//改为未访问，回退
				nIndex--;									//索引值减一
			}
		}
	}
}

//深度优先遍历
void DFSTraverse（int nVex PathList & pList）
{
	int nIndex = 0;					//遍历深度
	bool bVisited[20] = { false };  //所有的景点起始均为未访问
	DFS（nVex bVisited nIndex pList）;

}

//寻找最短路径
int FindShortPath（int nVexStart int nVexEnd Edge aPath[]）
{
	int nShortPath[20][20];       //保存最短路径，其中行表示终点，列表示从起点到终点的最短路径的每一步
	int nShortDistance[20];       //保存最短距离，保存从起点到任一顶点的最短距离
	bool aVisited[20];            //判断某顶点是否已经加入到最短路径中
	int v;                        //在下面的循环中，表示每一次找到的可以加入集合的顶点，即已经找到了从起点到该顶点的最短路径

	//初始化工作
	for （v = 0; v	{
		aVisited[v] = false;
		if （m_Graph.m_aAdjMatrix[nVexStart][v] != 0） {
			//初始化该顶点到其他顶点的最短距离，默认为两顶点间的距离
			nShortDistance[v] = m_Gr

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2018-05-09 14:06  GraphCPro\
     目录           0  2018-05-09 14:02  GraphCPro\.vs\
     目录           0  2018-05-09 14:02  GraphCPro\.vs\GraphCPro\
     目录           0  2018-05-29 22:19  GraphCPro\.vs\GraphCPro\v15\
     文件       56832  2018-05-29 22:19  GraphCPro\.vs\GraphCPro\v15\.suo
     文件     6385664  2018-05-29 22:19  GraphCPro\.vs\GraphCPro\v15\Browse.VC.db
     目录           0  2018-05-09 14:05  GraphCPro\.vs\GraphCPro\v15\ipch\
     目录           0  2018-05-16 16:46  GraphCPro\.vs\GraphCPro\v15\ipch\AutoPCH\
     目录           0  2018-05-22 22:56  GraphCPro\.vs\GraphCPro\v15\ipch\AutoPCH\2268792d5ba9bd61\
     文件    29884416  2018-05-29 17:11  GraphCPro\.vs\GraphCPro\v15\ipch\AutoPCH\2268792d5ba9bd61\TOURISM.ipch
     目录           0  2018-05-29 18:25  GraphCPro\.vs\GraphCPro\v15\ipch\AutoPCH\4f3bd78ae8af52ce\
     文件    26148864  2018-05-29 18:25  GraphCPro\.vs\GraphCPro\v15\ipch\AutoPCH\4f3bd78ae8af52ce\GRAPH.ipch
     目录           0  2018-05-16 16:45  GraphCPro\.vs\GraphCPro\v15\ipch\AutoPCH\852a8687ec82af0c\
     文件     2031616  2018-05-16 16:45  GraphCPro\.vs\GraphCPro\v15\ipch\AutoPCH\852a8687ec82af0c\MST-MAIN.ipch
     目录           0  2018-05-16 11:33  GraphCPro\.vs\GraphCPro\v15\ipch\AutoPCH\b078bd47f373a8cc\
     文件     3997696  2018-05-16 11:33  GraphCPro\.vs\GraphCPro\v15\ipch\AutoPCH\b078bd47f373a8cc\EXE_COMMON.ipch
     目录           0  2018-05-09 14:06  GraphCPro\.vs\GraphCPro\v15\ipch\AutoPCH\e2b9173128d6da18\
     文件    26083328  2018-05-29 19:48  GraphCPro\.vs\GraphCPro\v15\ipch\AutoPCH\e2b9173128d6da18\GRAPHCPRO.ipch
     文件     3604480  2018-05-09 14:02  GraphCPro\.vs\GraphCPro\v15\ipch\ef5083adb1a0bdd6.ipch
     目录           0  2018-05-16 18:04  GraphCPro\Debug\
     文件      114176  2018-05-23 15:21  GraphCPro\Debug\GraphCPro.exe
     文件      821616  2018-05-23 15:21  GraphCPro\Debug\GraphCPro.ilk
     文件     1019904  2018-05-23 15:21  GraphCPro\Debug\GraphCPro.pdb
     目录           0  2018-05-23 15:21  GraphCPro\GraphCPro\
     目录           0  2018-05-19 17:41  GraphCPro\GraphCPro\Debug\
     文件       39783  2018-05-23 15:21  GraphCPro\GraphCPro\Debug\Graph.obj
     文件         203  2018-05-23 15:21  GraphCPro\GraphCPro\Debug\GraphCPro.log
     文件       51349  2018-05-23 15:21  GraphCPro\GraphCPro\Debug\GraphCPro.obj
     目录           0  2018-05-23 15:21  GraphCPro\GraphCPro\Debug\GraphCPro.tlog\
     文件        2522  2018-05-23 15:21  GraphCPro\GraphCPro\Debug\GraphCPro.tlog\CL.command.1.tlog
     文件       54526  2018-05-23 15:21  GraphCPro\GraphCPro\Debug\GraphCPro.tlog\CL.read.1.tlog
............此处省略22个文件信息