#include "Graph.h" 
#define N 7 // 定義圖的頂點數(shù)


// 圖的相鄰矩陣表示法
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)中的計數(shù)器
		matrix = (int **)new int*[numVertex]; /*申請matrix數(shù)組,該數(shù)組有numVertex個元素,每個元素是整型指針類型*/
		
		for (i = 0; i < numVertex; i ++)		/*matrix數(shù)組的每個元素,都指向一個具有numVertex個元素的數(shù)組*/
			matrix[i] = new int[numVertex];  

		for (i = 0; i < numVertex; i++)       /*相鄰矩陣的所有元素都初始化為0,如果矩陣元素matrix[i][j]不為0,則表明頂點i與頂點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];			//釋放每個matrix[i]申請的空間
		delete [] matrix;				//釋放matrix指針指向的空間
	}

	Edge FirstEdge(int oneVertex)  {	//返回頂點oneVertex的第一條邊
		Edge myEdge;						//邊myEdge將作為函數(shù)的返回值
		myEdge.from = oneVertex;			//將頂點oneVertex作為邊myEdge的始點
		//  myEdge.to = -1; 
		for (int i = 0; i < numVertex; i ++)   {/* 下面尋找第一個使得matrix[oneVertex][i]
												不為0的i值，那么邊(oneVertex,i)或者
												弧<oneVertex,i>即為頂點oneVertex
												的第一條邊，將頂點i作為邊myEdge的終點邊myEdge
			                                    的權(quán)為矩陣元素matrix[oneVertex][i]的值*/
			if (matrix[oneVertex][i] != 0)  {									
				myEdge.to = i;
				myEdge.weight = matrix[oneVertex][i];
				break;
			}
		}
		return myEdge;/*如果找到了頂點oneVertex的第一條邊,則返回的myEdge確實是一條邊；
		              如果沒有找到頂點oneVertex的第一條邊,則myEdge的成員變量to為-1，
		              根據(jù)IsEdge函數(shù)判斷可知myEdge不是一條邊*/
	}

	Edge NextEdge(Edge preEdge)  { //返回與邊PreEdge有相同關(guān)聯(lián)頂點的下一條邊
		Edge myEdge;
		myEdge.from=preEdge.from; /*將邊myEdge的始點置為與上一條邊preEdge的始點相同*/
		if(preEdge.to<numVertex)  {
			//如果preEdge.to+1>=numVertex,那么就不存在下一條邊了
			for(int i=preEdge.to+1;i<numVertex;i++)  {
				/*尋找下一個使得//matrix[preEdge.from][i]不為0的i值,那么
				(preEdge.from,i)或者<preEdge.from,i>即為頂點preEdge.from的下一條邊*/
				if(matrix[preEdge.from][i]!=0)  {
					myEdge.to=i;
					myEdge.weight=matrix[preEdge.from][i];
					break;
				}
			}
		}
		return myEdge; /*如果找到了頂點preEdge.from的下一條邊，則返回的myEdge確實是一條邊；
					   如果沒有找到頂點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)在只是對該邊進行修改）*/
			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ù)和頂點to的入度進行修改）*/
			numEdge--;
			Indegree[to]--;
		}
		matrix[from][to]=0;		     
	}
};

// 函數(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]);
		}
	}
}

//函數(shù)功能：深度優(yōu)先搜索算法實現(xiàn)
void Graphm::DFS(Graph& G, int v)  {    //深度優(yōu)先搜索算法實現(xiàn)
    G.Mark[v] = VISITED;       //訪問頂點V，并標(biāo)記其標(biāo)志位
    Visit(G,v);	
    //訪問V鄰接到的未被訪問過的頂點，并遞歸地按照深度優(yōu)先的方式進行周游
    for(Edge e=G.FirstEdge(v);G.IsEdge(e);e=G.NextEdge(e))
        if(G.Mark[G.ToVertex(e)]== UNVISITED)
			DFS(G, G.ToVertex(e));
}


// 函數(shù)功能：廣度優(yōu)先搜索
void Graphm::BFS(Graph& G, int v)  {           // 廣度優(yōu)先搜索算法的實現(xiàn)
    using std::queue;
	queue<int> Q;                    // 初始化廣度優(yōu)先周游要用到的隊列
	Visit(G,v);                       // 問頂點v，并標(biāo)記其標(biāo)志位
    G.Mark[v] = VISITED;
    Q.push(v);                       // v入隊
	while (!Q.empty())  {              // 如果隊列仍然有元素
		int u = Q.front ();              // 隊列頂部元素
		Q.pop();                     // 隊列頂部元素出隊
       		// 該頂點鄰接到的每一個未訪問頂點都入隊
		for (Edge e = G.FirstEdge(u);G.IsEdge(e);e = G.NextEdge(e))
		if (G.Mark[G.ToVertex(e)] == UNVISITED)  {
		        Visit(G, G.ToVertex(e));	
			G.Mark[G.ToVertex(e)] = VISITED;
		    	Q.push(G.ToVertex(e));  // 入隊
		    }
	}
}

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