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

//m_Graph圖結構已經在主函數中定義，此處調用其
extern?Graph?m_Graph;

//初始化圖結構
int?Init（）
{
	for?（int?i?=?0;?i?		for?（int?j?=?0;?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?		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個文件信息