//*************** Link.h **************//

#define UNVISITED 0
#define VISITED 1
#define INFINITE 0xffffffff
#define N 5 // 定義圖的頂點數

struct listUnit  {    //鄰接表表目中數據部分的結構定義
	int vertex;      //邊的終點
	int weight;      //邊的權
};

template<class Elem>   //鏈表元素
class Link  {
public:
	Elem element;      //表目的數據
	Link *next;        //表目指針，指向下一個表目
	Link(const Elem& elemval,Link *nextval = NULL)  { //構造函數
		element = elemval; 
		next = nextval; 
	}
	Link(Link *nextval = NULL)  { 					//構造函數
		next = nextval; 
	} 
};

template<class Elem>   //鏈表
class LList  {
public:
	Link<Elem>* head;  //head指針并不儲存任何實際元素，其存在只是為了操作方便
	LList()  {          //構造函數
		head = new Link<Elem>();
	}
	void removeall()  {  //釋放邊表所有表目占據的空間
		Link<Elem> *fence;
		while(head != NULL)  { //逐步釋放每個表目占據的空間
			fence = head;
			head = head->next;
			delete fence;
		}
	}
	~LList() {				//析構函數
		removeall();
	}
};


class Graphl: public Graph  {
private:
	LList<listUnit> *graList;  //graList是保存所有邊表的數組	
public:
	Graphl(int numVert):Graph(numVert)  { //構造函數
		graList = new LList<listUnit>[numVertex]; /*為graList數組申請空間，圖有
										  numVertex個頂點，則有numVertex個邊表*/
	}

	~Graphl()  {                        //析構函數
		delete [] graList;				   //釋放空間
	}
	
	Edge FirstEdge(int oneVertex)  {   //返回頂點oneVertex的第一條邊
		Edge myEdge;                   //邊myEdge將作為函數的返回值
		myEdge.from = oneVertex;       //將頂點oneVertex作為邊myEdge的始點
									  /*graList[oneVertex].head保存的是頂點oneVertex的邊表，
									  temp->next指向頂點oneVertex的第一條邊(如果temp->next
									  不為null)*/
		Link<listUnit> *temp = graList[oneVertex].head;
		if(temp->next != NULL)  {        //如果頂點oneVertex的第一條邊確實存在
			myEdge.to = temp->next->element.vertex;
			myEdge.weight = temp->next->element.weight;
		}
		/*如果找到了頂點oneVertex的第一條邊,則返回的myEdge確實是一條邊;如果沒有
		找到頂點oneVertex的第一條邊,則myEdge的成員變量to為-1,根據IsEdge函數判
		斷可知myEdge不是一條邊*/
		return myEdge;
	}	

	Edge NextEdge(Edge preEdge)  {  // 返回與邊PreEdge有相同關聯頂點的下一條邊
		Edge myEdge;			 		// myEdge的初始成員變量to為-1
		myEdge.from = preEdge.from;  		// 將邊的始點置為與上一條邊的相同
		Link<listUnit> *temp = graList[preEdge.from].head;		// temp指向邊表頭一個
		while (temp->next != NULL && temp->next->element.vertex <= preEdge.to)
			temp = temp->next; 			// 確定邊preEdge的位置
		if (temp->next != NULL) {		// 邊preEdge的下一條邊存在
			myEdge.to = temp->next->element.vertex;
			myEdge.weight = temp->next->element.weight;
		}
		return myEdge;					// 如果沒有找到第一條邊，myEdge.to=-1
	}

	void setEdge(int from,int to,int weight)  {  //為圖設定一條邊
		Link<listUnit> *temp = graList[from].head;  /*graList[from].head保存的是頂點from的
													邊表，temp->next指向頂點from的第一條邊
													(如果temp->next不為null)*/
		while(temp->next != NULL && temp->next->element.vertex < to)
			temp = temp->next;   /*確定邊(from,to)或<from,to>在邊表中的位置,如果不存在,
									則邊(from,to)或<from,to>為新加的一條邊*/
		if(temp->next == NULL) {  /*邊(from,to)或<from,to>在邊表中不存在且在邊表中其后
									已無其它邊,則在邊表中加入這條邊*/
			temp->next = new Link<listUnit>;
			temp->next->element.vertex = to;
			temp->next->element.weight = weight;
			numEdge++;
			Indegree[to]++;
			return;
		}
		if(temp->next->element.vertex == to)  { /*邊(from,to)或<from,to>在邊表中已存在,
												故只需要改變邊的權值*/
			temp->next->element.weight = weight;
			return;
		}
		if(temp->next->element.vertex>to) { /*邊(from,to)或<from,to>在邊表中不存在,但在邊表中
												其后存在其它邊,則在邊表中插入這條邊*/
			Link<listUnit> *other = temp->next;
			temp->next = new Link<listUnit>;
			temp->next->element.vertex = to;
			temp->next->element.weight = weight;
			temp->next->next = other;
			numEdge++;
			Indegree[to]++;
			return;
		}
	}

	void delEdge(int from,int to)  {          //刪掉圖的一條邊
		Link<listUnit> *temp = graList[from].head;  /*graList[from].head保存的是頂點from的邊表，temp->next指向頂點from的第一條邊(如果temp->next不為null)*/
		while(temp->next != NULL && temp->next->element.vertex<to)  
			temp = temp->next;	/*確定邊(from,to)或<from,to>在邊表中的位置(如果該邊存在)*/
		if(temp->next == NULL)
			return;        //邊(from,to)或<from,to>在邊表中不存在,則不需要做任何操作
		if(temp->next->element.vertex>to)
			return;        //邊(from,to)或<from,to>在邊表中不存在,則不需要做任何操作
		if(temp->next->element.vertex == to) { /*邊(from,to)或<from,to>在邊表中存在且確
											   定了該邊在邊表中的位置,則從邊表中將其刪掉*/
			Link<listUnit> *other = temp->next->next;
		    delete temp->next;
		    temp->next = other;
		    numEdge--;
		    Indegree[to]--;
		    return;
		}
	}

	void IniGraphl(Graphl *Graphl, int A[N][N]);
	void DFS(Graph& G, int v);
	void BFS(Graph& G, int v);
	void Visit(Graph &G, int v);
};

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


//函數功能：深度優先搜索算法實現
void Graphl::DFS(Graph& G, int v)  {    //深度優先搜索算法實現
    G.Mark[v] = VISITED;       //訪問頂點v，并標記其標志位
    Visit(G,v);	
    //訪問V鄰接到的未被訪問過的頂點，并遞歸地按照深度優先的方式進行周游
    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));
}


// 函數功能：廣度優先搜索
void Graphl::BFS(Graph& G, int v)  {           // 廣度優先搜索算法的實現
    using std::queue;
	queue<int> Q;                    // 初始化廣度優先周游要用到的隊列
	Visit(G,v);                       // 問頂點v，并標記其標志位
    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));  // 入隊
		    }
	}
}


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