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

//m_Graph圖結(jié)構(gòu)已經(jīng)在主函數(shù)中定義，此處調(diào)用其
extern?Graph?m_Graph;

//初始化圖結(jié)構(gòu)
int?Init（）
{
	for?（int?i?=?0;?i?		for?（int?j?=?0;?j?			m_Graph.m_aAdjMatrix[i][j]?=?0;	//鄰接矩陣置零
		}
		m_Graph.m_nVexNum?=?0;				//景點(diǎn)數(shù)目置零
	}
	return?OK;
}

//將頂點(diǎn)添加到數(shù)組中
int?InsertVex（Vex?sVex）
{?
	//頂點(diǎn)已滿
	if?（m_Graph.m_nVexNum?==?20）
		return?ERROR;??????
	//
	m_Graph.m_aVexs[m_Graph.m_nVexNum++]?=?sVex;
	return?OK;
}

//將邊保存到鄰接矩陣中
int?InsertEdge（Edge?sEdge）
{?
	//下標(biāo)越界
	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;
}

//查詢指定頂點(diǎn)信息
Vex?GetVex（int?nVex）
{
	return?m_Graph.m_aVexs[nVex];
}

//查詢與指定頂點(diǎn)相連的邊
int?FindEdge（int?nVex?Edge?aEdge[]）
{
	int?flag?=?0;??//與景點(diǎn)n相鄰的邊的條數(shù)
	//便利整個(gè)圖的鄰接矩陣
	for?（int?j?=?0;?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;
}

//獲取當(dāng)前頂點(diǎn)數(shù)
int?GetVexmun（）{
	return?m_Graph.m_nVexNum;
}

//實(shí)現(xiàn)圖的深度優(yōu)先搜索遍歷
void?DFS（int?nVex?bool?bVisited[]?int?&?nIndex?PathList?&?pList）
{
	bVisited[nVex]?=?true;				//改為已訪問
	pList->vexs[nIndex++]?=?nVex;		//訪問頂點(diǎn)nVex并賦值給鏈表，然后索引值自加

	//判斷所有的頂點(diǎn)是否都已經(jīng)被訪問過									
	int?v_num?=?0;
	for?（int?i?=?0;?i	{
		//如果當(dāng)前i節(jié)點(diǎn)被訪問過，則V-Num自加
		if?（bVisited[i]）
			v_num++;
	}
	
	//所有的頂點(diǎn)都已經(jīng)被訪問過新增鏈表結(jié)點(diǎn)保存此次的路徑。必須保存，不然在后續(xù)的遞歸中會(huì)存在重復(fù)使用的vex，導(dǎo)致有的路徑結(jié)點(diǎn)中vex沒有值
	if?（v_num?==?m_Graph.m_nVexNum）
	{		
		//創(chuàng)建一個(gè)新鏈表，將當(dāng)前的pList中的數(shù)據(jù)保存起來
		pList->next?=?new?Path;
		for?（int?i?=?0;?i		{
			pList->next->vexs[i]?=?pList->vexs[i];
		}
		pList?=?pList->next;		//pList指針繼續(xù)往下移動(dòng)，尋找下一條路徑
		pList->next?=?NULL;			//next賦值為空
	}
	//并沒有全部訪問，則進(jìn)行尋找下一個(gè)相鄰節(jié)點(diǎn)的操作
	else
	{
		for?（int?i?=?0;?i		{
			//如果i是nVex的的鄰接點(diǎn)??并且未被訪問
			if?（!bVisited[i]?&&?m_Graph.m_aAdjMatrix[nVex][i]>0）	
			{
				DFS（i?bVisited?nIndex?pList）;			//遞歸調(diào)用DFS
				bVisited[i]?=?false;						//改為未訪問，回退
				nIndex--;									//索引值減一
			}
		}
	}
}

//深度優(yōu)先遍歷
void?DFSTraverse（int?nVex?PathList?&?pList）
{
	int?nIndex?=?0;					//遍歷深度
	bool?bVisited[20]?=?{?false?};??//所有的景點(diǎn)起始均為未訪問
	DFS（nVex?bVisited?nIndex?pList）;

}

//尋找最短路徑
int?FindShortPath（int?nVexStart?int?nVexEnd?Edge?aPath[]）
{
	int?nShortPath[20][20];???????//保存最短路徑，其中行表示終點(diǎn)，列表示從起點(diǎn)到終點(diǎn)的最短路徑的每一步
	int?nShortDistance[20];???????//保存最短距離，保存從起點(diǎn)到任一頂點(diǎn)的最短距離
	bool?aVisited[20];????????????//判斷某頂點(diǎn)是否已經(jīng)加入到最短路徑中
	int?v;????????????????????????//在下面的循環(huán)中，表示每一次找到的可以加入集合的頂點(diǎn)，即已經(jīng)找到了從起點(diǎn)到該頂點(diǎn)的最短路徑

	//初始化工作
	for?（v?=?0;?v	{
		aVisited[v]?=?false;
		if?（m_Graph.m_aAdjMatrix[nVexStart][v]?!=?0）?{
			//初始化該頂點(diǎn)到其他頂點(diǎn)的最短距離，默認(rèn)為兩頂點(diǎn)間的距離
			nShortDistance[v]?=?m_Gr

?屬性????????????大小?????日期????時(shí)間???名稱
-----------?---------??----------?-----??----
?????目錄???????????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個(gè)文件信息