武汉理工大学数据结构与算法实验，景区管理导航系统

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


void CGraph::Init（）{
	for（int i=0;i<20;i++）
	for（int j=0;j<20;j++）
		m_aAdjmatrix[i][j]=0;//初始化图
	m_nVexNum=0;
}

int CGraph::InsertVex（Vex sVex）{
	if（m_nVexNum==MAX_VERTEX_NUM）{
	return ERROR;
	}

	 m_aVexs[m_nVexNum++]=sVex;

	 return OK;
}

int CGraph::InsertEdge（Edge sEdge）{
	if（sEdge.vex1<0||sEdge.vex1>m_nVexNum||sEdge.vex2<0||sEdge.vex2>m_nVexNum）
		return ERROR;
	m_aAdjmatrix[sEdge.vex1][sEdge.vex2]=sEdge.weight;
	m_aAdjmatrix[sEdge.vex2][sEdge.vex1]=sEdge.weight;

	return OK;
}



//获得顶点

Vex CGraph::GexVex（int v）{

	return m_aVexs[v];

}
//获得邻近顶点个数与边
int CGraph::FindEdge（int vEdge aEdge[]）
{
	int k = 0;
	for （int i = 0; i < m_nVexNum; i++）
	{
		if （m_aAdjmatrix[v][i]!=0）
		{
			aEdge[k].vex1 = v;
			aEdge[k].vex2 = i;
			aEdge[k].weight = m_aAdjmatrix[v][i];
			k++;
		}

	}
	
	return k;
}
int CGraph::GetVexNum（） {

	return m_nVexNum;
}
//深度优先搜索遍历
void CGraph::DFS（int nVex bool bVisited[] int &nIndex PathList &pList） {
	bVisited[nVex] = true;
	pList->vexs[nIndex++] = nVex;

	int vexNum = 0;//判断是否所有结点是否全都被访问过
	for （int i = 0; i < m_nVexNum; i++）
	{
		if （bVisited[i]）
		{
			vexNum++;
		}
	}
	//如果所有结点都被访问过

	if （vexNum==m_nVexNum）
	{
		pList->next = （PathList）malloc（sizeof（Path））;
		for （int i = 0; i < m_nVexNum; i++）
		{
			pList->next->vexs[i] = pList->vexs[i];
		}
		pList = pList->next;
		pList->next = NULL;
	}
	else
	{

		for （int i = 0; i < m_nVexNum; i++）
		{
			if （m_aAdjmatrix[nVex][i] != 0 && !bVisited[i]）
			{
				DFS（i bVisited nIndex pList）;
				bVisited[i] = false;
				nIndex--;
			}
		}
	}
}

//遍历调用函数
void CGraph::DFSTraverse（int nVex PathList & pList） {
	int nIndex = 0;
	bool bVisited[MAX_VERTEX_NUM] = { false };
	DFS（nVex bVisited nIndexpList）;

}

//求最短路径长度
int CGraph::FindShortPath（int nVexStart int nVexEnd Edge aPath[]）
{
	int nShortPath[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//保存最短路径
	int nShortDistance[MAX_VERTEX_NUM];//保存最短距离
	bool aVisited[MAX_VERTEX_NUM];//判断某顶点是否已经加入到最短路径
								  //初始化
	int v;
	for （v = 0; v	{
		aVisited[v] = false;
		if （m_aAdjmatrix[nVexStart][v] != 0）
			//初始化该顶点到其他顶点的最短距离，默认为两点间的距离
			nShortDistance[v] = m_aAdjmatrix[nVexStart][v];
		else
			//如果顶点i和nVexStart不相连，则最短距离设为最大值
			nShortDistance[v] = 0x7FFFFFFF;
		nShortPath[v][0] = nVexStart;//起始点为nVexStart
		for （int j = 1; j		{
			nShortPath[v][j] = -1;//初始化最短路径
		}
	}
	//初始化，nVexStart顶点加入到集合中
	aVisited[nVexStart] = true;
	int min;

	for （int i = 1; i	{
		min = 0x7FFFFFFF;
		bool bAdd = false;//判断是否还有顶点可以加入到集合中
		for （int j = 0; j		{
			if （aVisited[j] == false）
			{
				if （nShortDistance[j]				{
					v = j;//j顶点离nVexStart顶点最近
					min = nShortDistance[j];//j到nVexStart的最短距离为min
					bAdd = true;
				}
			}
		}//如果没有顶点可以加入到集合，则跳出循环
		if （

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

    ..A..H.     46080  2018-05-30 17:27  GraphCPro.vsGraphCProv14.suo

     文件      55808  2018-05-30 17:26  GraphCProDebugGraphCPro.exe

     文件     424328  2018-05-30 17:26  GraphCProDebugGraphCPro.ilk

     文件     946176  2018-05-30 17:26  GraphCProDebugGraphCPro.pdb

     文件         93  2018-05-12 20:52  GraphCProGraphCProdataEdge.txt

     文件        197  2018-05-12 21:16  GraphCProGraphCProdataVex.txt

     文件       1692  2018-05-11 16:03  GraphCProGraphCProDebugcl.command.1.tlog

     文件      14646  2018-05-11 16:03  GraphCProGraphCProDebugCL.read.1.tlog

     文件       1446  2018-05-11 16:03  GraphCProGraphCProDebugCL.write.1.tlog

     文件      30570  2018-05-30 17:20  GraphCProGraphCProDebugGraph.obj

     文件        381  2018-05-11 16:03  GraphCProGraphCProDebugGraphCPro.exe.intermediate.manifest

     文件         90  2018-05-11 16:03  GraphCProGraphCProDebugGraphCPro.lastbuildstate

     文件       1653  2018-05-30 17:26  GraphCProGraphCProDebugGraphCPro.log

     文件       1800  2018-05-30 17:26  GraphCProGraphCProDebugGraphCPro.tlogCL.command.1.tlog

     文件      30220  2018-05-30 17:26  GraphCProGraphCProDebugGraphCPro.tlogCL.read.1.tlog

     文件       3502  2018-05-30 17:26  GraphCProGraphCProDebugGraphCPro.tlogCL.write.1.tlog

     文件        196  2018-05-30 17:26  GraphCProGraphCProDebugGraphCPro.tlogGraphCPro.lastbuildstate

     文件       1418  2018-05-30 17:26  GraphCProGraphCProDebugGraphCPro.tloglink.command.1.tlog

     文件       2986  2018-05-30 17:26  GraphCProGraphCProDebugGraphCPro.tloglink.read.1.tlog

     文件        662  2018-05-30 17:26  GraphCProGraphCProDebugGraphCPro.tloglink.write.1.tlog

     文件        713  2018-05-11 16:01  GraphCProGraphCProDebugGraphCPro.vcxprojResolveAssemblyReference.cache

     文件          0  2018-05-11 16:01  GraphCProGraphCProDebugGraphCPro.write.1.tlog

     文件       1524  2018-05-11 16:03  GraphCProGraphCProDebuglink.command.1.tlog

     文件       3012  2018-05-11 16:03  GraphCProGraphCProDebuglink.read.1.tlog

     文件        830  2018-05-11 16:03  GraphCProGraphCProDebuglink.write.1.tlog

     文件      41231  2018-05-30 17:26  GraphCProGraphCProDebugMain.obj

     文件        456  2018-05-11 16:03  GraphCProGraphCProDebugmt.command.1.tlog

     文件        734  2018-05-11 16:03  GraphCProGraphCProDebugmt.read.1.tlog

     文件        276  2018-05-11 16:03  GraphCProGraphCProDebugmt.write.1.tlog

     文件      64063  2018-05-30 17:26  GraphCProGraphCProDebugTourism.obj

............此处省略30个文件信息