#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?	{
		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?	{
		if?（bVisited[i]）
		{
			vexNum++;
		}
	}
	//如果所有結點都被訪問過

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

		for?（int?i?=?0;?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\.vs\GraphCPro\v14\.suo

?????文件??????55808??2018-05-30?17:26??GraphCPro\Debug\GraphCPro.exe

?????文件?????424328??2018-05-30?17:26??GraphCPro\Debug\GraphCPro.ilk

?????文件?????946176??2018-05-30?17:26??GraphCPro\Debug\GraphCPro.pdb

?????文件?????????93??2018-05-12?20:52??GraphCPro\GraphCPro\data\Edge.txt

?????文件????????197??2018-05-12?21:16??GraphCPro\GraphCPro\data\Vex.txt

?????文件???????1692??2018-05-11?16:03??GraphCPro\GraphCPro\Debug\cl.command.1.tlog

?????文件??????14646??2018-05-11?16:03??GraphCPro\GraphCPro\Debug\CL.read.1.tlog

?????文件???????1446??2018-05-11?16:03??GraphCPro\GraphCPro\Debug\CL.write.1.tlog

?????文件??????30570??2018-05-30?17:20??GraphCPro\GraphCPro\Debug\Graph.obj

?????文件????????381??2018-05-11?16:03??GraphCPro\GraphCPro\Debug\GraphCPro.exe.intermediate.manifest

?????文件?????????90??2018-05-11?16:03??GraphCPro\GraphCPro\Debug\GraphCPro.lastbuildstate

?????文件???????1653??2018-05-30?17:26??GraphCPro\GraphCPro\Debug\GraphCPro.log

?????文件???????1800??2018-05-30?17:26??GraphCPro\GraphCPro\Debug\GraphCPro.tlog\CL.command.1.tlog

?????文件??????30220??2018-05-30?17:26??GraphCPro\GraphCPro\Debug\GraphCPro.tlog\CL.read.1.tlog

?????文件???????3502??2018-05-30?17:26??GraphCPro\GraphCPro\Debug\GraphCPro.tlog\CL.write.1.tlog

?????文件????????196??2018-05-30?17:26??GraphCPro\GraphCPro\Debug\GraphCPro.tlog\GraphCPro.lastbuildstate

?????文件???????1418??2018-05-30?17:26??GraphCPro\GraphCPro\Debug\GraphCPro.tlog\link.command.1.tlog

?????文件???????2986??2018-05-30?17:26??GraphCPro\GraphCPro\Debug\GraphCPro.tlog\link.read.1.tlog

?????文件????????662??2018-05-30?17:26??GraphCPro\GraphCPro\Debug\GraphCPro.tlog\link.write.1.tlog

?????文件????????713??2018-05-11?16:01??GraphCPro\GraphCPro\Debug\GraphCPro.vcxprojResolveAssemblyReference.cache

?????文件??????????0??2018-05-11?16:01??GraphCPro\GraphCPro\Debug\GraphCPro.write.1.tlog

?????文件???????1524??2018-05-11?16:03??GraphCPro\GraphCPro\Debug\link.command.1.tlog

?????文件???????3012??2018-05-11?16:03??GraphCPro\GraphCPro\Debug\link.read.1.tlog

?????文件????????830??2018-05-11?16:03??GraphCPro\GraphCPro\Debug\link.write.1.tlog

?????文件??????41231??2018-05-30?17:26??GraphCPro\GraphCPro\Debug\Main.obj

?????文件????????456??2018-05-11?16:03??GraphCPro\GraphCPro\Debug\mt.command.1.tlog

?????文件????????734??2018-05-11?16:03??GraphCPro\GraphCPro\Debug\mt.read.1.tlog

?????文件????????276??2018-05-11?16:03??GraphCPro\GraphCPro\Debug\mt.write.1.tlog

?????文件??????64063??2018-05-30?17:26??GraphCPro\GraphCPro\Debug\Tourism.obj

............此處省略30個文件信息