#include "SeqList.h"					//包含動態數組結構的順序表類

class AdjMWGraph
{
private:
	SeqList Vertices;								//頂點順序表
	int Edge[MaxVertices][MaxVertices];				//邊權值數組
	int numOfEdges;									//邊的個數

	void DepthFirstSearch(const int v, int visited[], 
void Visit(VerT item));		
	void BroadFirstSearch(const int v, int visited[], 
void Visit(VerT item));
public:
	AdjMWGraph(const int sz = MaxVertices);			//構造函數
	~AdjMWGraph(void){};							//析構函數

	int NumOfVertices(void)							//取頂點個數
		{return Vertices.Size();}
	int NumOfEdges(void)							//取邊的個數
		{return numOfEdges;}
	VerT GetValue(const int v);						//取頂點數值
	int GetWeight(const int v1, const int v2);		//取邊的權值

	void InsertVertex(const VerT &vertex);			//插入頂點
	void InsertEdge(const int v1, const int v2, int weight);//插入邊
	void DeleteVertex(const int v);					//刪除頂點
	void DeleteEdge(const int v1, const int v2);	//刪除邊
	int GetFirstNeighbor(const int v);				//取第一個鄰接頂點
	int GetNextNeighbor(const int v1, const int v2);//取下一個鄰接頂點

	void DepthFirstSearch(void Visit(VerT item));	//深度優先遍歷
	void BroadFirstSearch(void Visit(VerT item));	//廣度優先遍歷
};

AdjMWGraph::AdjMWGraph(const int sz): Vertices(sz)
//構造函數
{
	for(int i = 0; i < sz; i++)
		for(int j = 0; j < sz; j++)
		{
			if(i == j) Edge[i][j] = 0;
			else Edge[i][j] = MaxWeight;
		}
	numOfEdges = 0;
}

VerT AdjMWGraph::GetValue(const int v)
//取頂點v的數值
{
	if(v < 0 || v > Vertices.Size())
	{
		cout << "參數v越界出錯!" << endl;
		exit(0);
	}
	return Vertices.GetData(v);
}

int AdjMWGraph::GetWeight(const int v1, const int v2)
//取起始頂點為v1、終止頂點為 v2的邊的權值
{
	if(v1 < 0 || v1 > Vertices.Size() || v2 < 0 || v2 > Vertices.Size())
	{
		cout << "參數v1或v2越界出錯!" << endl;
		exit(0);
	}
	return Edge[v1][v2];
}

void AdjMWGraph::InsertVertex(const VerT &vertex)
//插入頂點vertex
{
	//把頂點vertex插入到順序表的當前表尾位置
	Vertices.Insert(vertex, Vertices.Size());
}

void AdjMWGraph::InsertEdge(const int v1, const int v2, int weight)
//插入一條起始頂點為v1、終止頂點為 v2、權值為weight的邊
{
	if(v1 < 0 || v1 > Vertices.Size() || v2 < 0 || v2 > Vertices.Size())
	{
		cout << "參數v1或v2越界出錯!" << endl;
		exit(0);
	}
	Edge[v1][v2] = weight;							//插入邊
	numOfEdges++;									//邊的個數加1
}

void AdjMWGraph::DeleteVertex(const int v)
//刪除頂點v
{
	//刪除所有包含頂點v的邊
	for(int i = 0; i < Vertices.Size(); i++)
		for(int j = 0; j < Vertices.Size(); j++)
			if((i == v || j == v) && i != j && Edge[i][j] > 0 
				&& Edge[i][j] < MaxWeight) 
			{
				Edge[i][j] = MaxWeight;		//把該邊的權值置為無窮大
				numOfEdges--;				//邊的個數減1
			}

	Vertices.Delete(v);								//刪除頂點v
}

void AdjMWGraph::DeleteEdge(const int v1, const int v2)
//刪除一條起始頂點為v1、終止頂點為 v2的邊
{
	if(v1 < 0 || v1 > Vertices.Size() ||
		v2 < 0 || v2 > Vertices.Size() || v1 == v2)
	{
		cout << "參數v1或v2出錯!" << endl;
		exit(0);
	}

	if(Edge[v1][v2] == MaxWeight || v1 == v2)
	{
		cout << "該邊不存在!" << endl;
		exit(0);
	}

	Edge[v1][v2] = MaxWeight;				//把該邊的權值置為無窮大
	numOfEdges--;							//邊的個數減1
}

int AdjMWGraph::GetFirstNeighbor(const int v)
//取頂點v的第一個鄰接頂點。若存在返回該頂點的下標序號，否則返回-1
{
	if(v < 0 || v > Vertices.Size())
	{
		cout << "參數v1越界出錯!" << endl;
		exit(0);
	}

	for(int col = 0; col <= Vertices.Size(); col++)
		if(Edge[v][col] > 0 && Edge[v][col] < MaxWeight) return col;
	return -1;
}

int AdjMWGraph::GetNextNeighbor(const int v1, const int v2)
//取頂點v1的鄰接頂點v2后的鄰接頂點
//若存在返回該頂點的下標序號，否則返回-1
{
	if(v1 < 0 || v1 > Vertices.Size() || v2 < 0 || v2 > Vertices.Size())
	{
		cout << "參數v1或v2越界出錯!" << endl;
		exit(0);
	}

	for(int col = v2+1; col <= Vertices.Size(); col++)
		if(Edge[v1][col] > 0 && Edge[v1][col] < MaxWeight) return col;
	return -1;
}

void AdjMWGraph::DepthFirstSearch(void Visit(VerT item))
{
	int *visited = new int[NumOfVertices()];
	for(int i = 0; i < NumOfVertices(); i++) visited[i] = 0;
	for(i = 0; i < NumOfVertices(); i++)
		if(! visited[i]) DepthFirstSearch(i, visited, Visit);
	delete []visited;
}

void AdjMWGraph::DepthFirstSearch(const int v, int visited[], void Visit(VerT item))
{
	Visit(GetValue(v));
	visited[v] = 1;

	int w = GetFirstNeighbor(v);
	while(w != -1)
	{
		if(! visited[w]) DepthFirstSearch(w, visited, Visit);
		w = GetNextNeighbor(v, w);
	}
}

void AdjMWGraph::BroadFirstSearch(void Visit(VerT item))
{
	int *visited = new int[NumOfVertices()];
	for(int i = 0; i < NumOfVertices(); i++) visited[i] = 0;
	for(i = 0; i < NumOfVertices(); i++)
		if(!visited[i]) BroadFirstSearch(i, visited, Visit);
	delete []visited;
}

#include "SeqQueue.h"					//包含靜態數組結構的順序隊列類
void AdjMWGraph::BroadFirstSearch(const int v, int visited[], void Visit(VerT item))
{
	VerT u, w;
	SeqQueue queue;
	Visit(GetValue(v));
	visited[v] = 1;
	queue.Append(v);
	while(queue.NotEmpty())
	{
		u = queue.Delete();
		w = GetFirstNeighbor(u);
		while(w != -1)
		{
			if(!visited[w])
			{
				Visit(GetValue(w));
				visited[w] = 1;
				queue.Append(w);
			}
			w = GetNextNeighbor(u, w);
		}
	}
}