//GraphMatrix.h

//Edge
class Edge
{ 
public: 
	int weight;  // Edge weight
	int from; 
	int to; // form To to 
	Edge(){};								// 構(gòu)造函數(shù)
	Edge(int f,int t,int w)   { 			// 構(gòu)造函數(shù)
		from=f;   to=t;   weight=w;
	}
	bool operator < (const Edge &arg) {return (this->weight < arg.weight);};
	bool operator == (const Edge &arg) {return (this->weight == arg.weight);};
	bool operator > (const Edge &arg) {return (this->weight > arg.weight);};
	bool operator <= (const Edge &arg) {return (this->weight <= arg.weight);};
	bool operator >= (const Edge &arg) {return (this->weight >= arg.weight);};
};

// 圖基類
class Graph  {
public:
	int numVertex;             //圖的頂點(diǎn)的個(gè)數(shù)
	int numEdge;				//圖的邊的數(shù)目
	int *Mark;					/*Mark指針指向保存有圖的頂點(diǎn)的標(biāo)志位的數(shù)組,標(biāo)志位用來(lái)標(biāo)記某頂點(diǎn)是否被訪問過*/
	int *Indegree;				//Indegree指針指向保存有圖的頂點(diǎn)的入度的數(shù)組
	Graph(int numVert)  {		//構(gòu)造函數(shù)
		numVertex = numVert;      //確定圖的頂點(diǎn)的個(gè)數(shù)
		numEdge = 0;				//確定圖的邊的數(shù)目
		Indegree = new int[numVertex]; /*為保存圖的頂點(diǎn)的入度申請(qǐng)數(shù)組,Indegree為數(shù)組指針*/
		Mark = new int[numVertex];	 /*為圖的頂點(diǎn)的標(biāo)志位申請(qǐng)數(shù)組,Mark為數(shù)組指針*/
		
		for (int i = 0; i < numVertex; i ++)  {	/*確定圖的頂點(diǎn)的標(biāo)志位和入度,即所有頂點(diǎn)的標(biāo)志位初始化為未被訪問過,入度初始化為0*/
			Mark[i] = UNVISITED;
			Indegree[i] = 0;
		}
	};
	~Graph() {				//析構(gòu)函數(shù)
		delete [] Mark;
		delete [] Indegree;
	}; 
	virtual Edge FirstEdge(int oneVertex) {	// 返回與頂點(diǎn)oneVertex相關(guān)聯(lián)的第一條邊
		Edge myEdge;
		myEdge.from = oneVertex; 
		myEdge.to = -1;
		return myEdge;
	}; 
	virtual Edge NextEdge(Edge preEdge) {      // 返回與邊PreEdge有相同關(guān)聯(lián)頂點(diǎn)的下一條邊
		return preEdge;
	};
	int VerticesNum() {		//返回圖的頂點(diǎn)個(gè)數(shù)
		return numVertex;
	};       
	int EdgesNum() {			//返回圖的邊數(shù)
		return numEdge;
	};
	int FromVertex(Edge oneEdge) {  // 返回oneEdge的始點(diǎn)
		return oneEdge.from;
	}; 
	int ToVertex(Edge oneEdge) {	// 返回oneEdge的終點(diǎn)
		return oneEdge.to;
	};    
	int Weight(Edge oneEdge) {		// 返回oneEdge的權(quán)值
		return oneEdge.weight;
	}; 
	bool IsEdge(Edge oneEdge)  {	//如果oneEdge是邊則返回TRUE，否則返回FALSE
		if (oneEdge.weight > 0 && oneEdge.weight < INFINITE && oneEdge.to >= 0)
			return true;
		else
			return false;
	}; 
	virtual void setEdge(int from, int to, int weight) = 0;
	virtual void delEdge(int from, int to) = 0;
};


// 圖的相鄰矩陣表示法
class Graphm:public Graph  {
private:
	int **matrix;				//指向相鄰矩陣的指針
public:
	void Graphm::IniGraphm(Graphm *Graphm, int A[N][N]); // 初始化
	void DFS(Graph &G, int V);			// 深度優(yōu)先搜索  
	void BFS(Graph &G, int V);			// 廣度優(yōu)先搜索
	void Visit(Graph &G, int V);		// 訪問
	
public:
	Graphm(int numVert):Graph(numVert)  {//構(gòu)造函數(shù)
		int i, j;			//i, j作為for循環(huán)中的計(jì)數(shù)器
		matrix = (int **)new int*[numVertex]; /*申請(qǐng)matrix數(shù)組,該數(shù)組有numVertex個(gè)元素,每個(gè)元素是整型指針類型*/
		
		for (i = 0; i < numVertex; i ++)		/*matrix數(shù)組的每個(gè)元素,都指向一個(gè)具有numVertex個(gè)元素的數(shù)組*/
			matrix[i] = new int[numVertex];  
		for (i = 0; i < numVertex; i++)       /*相鄰矩陣的所有元素都初始化為0,如果矩陣元素matrix[i][j]不為0,則表明頂點(diǎn)i與頂點(diǎn)j之間有一條邊,邊的權(quán)即為matrix[i][j]的值*/
			for (j = 0; j < numVertex; j ++)
				matrix[i][j] = 0;
	};
	~Graphm() {							//析構(gòu)函數(shù)
		for (int i = 0; i < numVertex; i ++)
			delete [] matrix[i];			//釋放每個(gè)matrix[i]申請(qǐng)的空間
		delete [] matrix;				//釋放matrix指針指向的空間
	}; 
	Edge FirstEdge(int oneVertex)  {	//返回頂點(diǎn)oneVertex的第一條邊
		Edge myEdge;						//邊myEdge將作為函數(shù)的返回值
		myEdge.from = oneVertex;			//將頂點(diǎn)oneVertex作為邊myEdge的始點(diǎn)
		//  myEdge.to = -1; 
		for (int i = 0; i < numVertex; i ++)   {/* 下面尋找第一個(gè)使得matrix[oneVertex][i]不為0的i值，
												那么邊(oneVertex,i)或者弧<oneVertex,i>即為頂點(diǎn)oneVertex
												的第一條邊，將頂點(diǎn)i作為邊myEdge的終點(diǎn)邊myEdge的權(quán)為
			矩陣元素matrix[oneVertex][i]的值*/
			if (matrix[oneVertex][i] != 0)
			{									
				myEdge.to = i;
				myEdge.weight = matrix[oneVertex][i];
				break;
			}
		}
		return myEdge;/*如果找到了頂點(diǎn)oneVertex的第一條邊,則返回的myEdge確實(shí)是一條邊；如果沒有找到頂點(diǎn)oneVertex的第一條邊,則myEdge的成員變量to為-1，根據(jù)IsEdge函數(shù)判斷可知myEdge不是一條邊*/
	}; 
	Edge NextEdge(Edge preEdge)  { //返回與邊PreEdge有相同關(guān)聯(lián)頂點(diǎn)的下一條邊
		Edge myEdge;
		myEdge.from=preEdge.from; /*將邊myEdge的始點(diǎn)置為與上一條邊preEdge的始點(diǎn)相同*/
		if(preEdge.to<numVertex)  {
			//如果preEdge.to+1>=numVertex,那么就不存在下一條邊了
			for(int i=preEdge.to+1;i<numVertex;i++)  {
				/*尋找下一個(gè)使得//matrix[preEdge.from][i]不為0的i值,那么(preEdge.from,i)或者<preEdge.from,i>即為頂點(diǎn)preEdge.from的下一條邊*/
				if(matrix[preEdge.from][i]!=0)  {
					myEdge.to=i;
					myEdge.weight=matrix[preEdge.from][i];
					break;
				}
			}
		}
		return myEdge; /*如果找到了頂點(diǎn)preEdge.from的下一條邊，則返回的myEdge確實(shí)是一條邊；如果沒有找到頂點(diǎn)preEdge.from的下一條邊，則myEdge的成員變量to為-1，
		根據(jù)IsEdge函數(shù)判斷可知myEdge不是一條邊*/
	}
	
	void setEdge(int from, int to, int weight)  {	//為圖設(shè)定一條邊
		if (matrix[from][to] <= 0) {    //如果matrix[from][to]<=0，則邊(from,to)或者<from,to>將是新增的一條邊，否則該邊已經(jīng)存在（現(xiàn)在只是對(duì)該邊進(jìn)行修改）
			numEdge ++;
			Indegree[to] ++;
		}
		matrix[from][to] = weight;
	}; 
	
	void delEdge(int from,int to)  {     //刪除圖的一條邊
		if(matrix[from][to]>0)  {
			/*如果matrix[from][to]>0，則邊(from,to)或者<from,to>確實(shí)存在，否則該邊實(shí)際上并不存在（從而不必對(duì)圖的邊數(shù)和頂點(diǎn)to的入度進(jìn)行修改）*/
			numEdge--;
			Indegree[to]--;
		}
		matrix[from][to]=0;		     
	}
};

// 函數(shù)功能：顯示頂點(diǎn)
void Graphm::Visit(Graph &G, int v) {
	cout << 'V' << v <<" ";
}


// 函數(shù)功能：初始化圖
void Graphm::IniGraphm(Graphm *Graphm, int A[N][N])  {
	for (int i = 0; i < N; i ++)  {
		for (int j = 0; j < N; j ++)  {
			if (A[i][j] > 0)
				Graphm->setEdge(i, j, A[i][j]);
		}
	}
}