#pragma once

#define MaxNumEdges   38				//最大邊數(shù)
const int MaxNumVertices=19;				//最大頂點(diǎn)數(shù)
#define MAXINT 2000                      //權(quán)值的最大值
#define VERTICES 19						//頂點(diǎn)總數(shù)


class CGraph
{
public:
	CGraph( const int sz=MaxNumEdges );					//構(gòu)造函數(shù)
	~CGraph() {};
	int GetValue ( const int i );						//取頂點(diǎn)i的值, i不合理則返回空
	int GetWeight ( const int v1, const int v2 );	//給出以頂點(diǎn)v1和v2為兩端點(diǎn)的邊上的權(quán)值
	int GetFirstNeighbor ( const int v );				//給出頂點(diǎn)位置為v的第一個(gè)鄰接頂點(diǎn)的位置
	int GetNextNeighbor ( const int v1, const int v2 );	//給出頂點(diǎn)位置v1的某鄰接頂點(diǎn)v2的下一個(gè)鄰接頂點(diǎn)

	void InsertVertex(int);
	void InsertEdge ( const int, const int, int );	//插入一條邊(v1, v2), 該邊上的權(quán)值為weight
	int* BestPath(int, int, int&, int&);                  //輸出最短路徑

	void AllLengths();
//	int* Prim(int& count);
	int* DFS(int& count);
	void DFS(const int v, int visited[], int &count, int*);
private:
	CString strAddress,strTemp,strOutput;       //為輸出所求路的徑信息而設(shè);
	int Edge[MaxNumVertices][MaxNumVertices];	//鄰接矩陣
	int dist[MaxNumVertices][MaxNumVertices];	//存放從頂點(diǎn)0到其它各頂點(diǎn)的最短路徑長度
	int path[MaxNumVertices][MaxNumVertices];	//存放在最短路徑上該頂點(diǎn)的前一頂點(diǎn)的頂點(diǎn)號(hào)
};