#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>
#include "tu.head"
bool visited[MAX_VERTEX_NUM];
void CreateGraph(ALGraph &G){
	
	int i, j = 0, k = 0;
	char hand, tide;
	ArcNode *p;
	
	cout<<"input the number for vexnum and arcnum:";
	cin>>G.vexnum>>G.arcnum;
	cout<<endl;
	cout<<"input"<<G.vexnum<<"char for vexs:";
	for(i=0; i < G.vexnum; i++)
		cin>>G.vertices[i].data;
	cout<<endl;
	for(i=0;i<G.vexnum;++i)
		G.vertices[i].firstarc=NULL;
	cout<<"input"<<G.arcnum<<"arc(char-enter-char):"<<endl;
	j = 0;
	k = 0;
	for(i=0; i < G.arcnum; i++)
	{
		cout<<i<<":";
		cin>>hand;
		cin>>tide;
		while (hand != G.vertices[j].data)
			j++;
		while (tide != G.vertices[k].data)
			k++;
		p=new ArcNode;
		p->adjvex=j;
		p->nextarc=G.vertices[j].firstarc;
		G.vertices[k].firstarc=p;
		p=new ArcNode;
		p->adjvex=k;
		p->nextarc=G.vertices[j].firstarc;
		G.vertices[j].firstarc=p;
		
		j = 0;
		k = 0;
		cout<<endl;
	}
}

void BFSTraverse(ALGraph G, Status (*Visit)(int v)){
	int w;
	SqQueue  Q;
	QElemType   u;
	
	InitQueue(Q);
	
	for(int v=0; v < G.vexnum;++v)
		visited[v]=FALSE;
	for(v=0; v<G.vexnum;++v)
		if(!visited[v])
		{
			visited[v]=TRUE;
			EnQueue(Q, v);
			Visit(v);
			while(QueueEmpty(Q))
			{
				DeQueue(Q, u);
				for(w = FirstAdjVex(G, u); w; w = NextAdjVex(G, u, w))
					if(! visited[w])
					{
						visited[w]=TRUE;
						Visit(w);
						EnQueue(Q, w);
					}
			}
		}
}
void DFSTraverse(ALGraph G, Status (*Visit)(int v)){
	
	int j;
	VisitFunc = Visit;
	for( j=0; j<G.vexnum; j++)
		visited[j] = 0;
	for(j=0; j<G.vexnum; j++)
		if(!visited[j])
			DFS(G, j);
}


void DFS(ALGraph G, int v) {
	int w;
	visited[v]=1;
	VisitFunc(v);
	for(w=FirstAdjVex(G, v); w>=0; w=NextAdjVex(G, v, w))
		if(!visited[w])
			DFS(G, w);
}


int FirstAdjVex(ALGraph G, int v){
	ArcNode *p;
	p = G.vertices[v].firstarc;
	while(p != NULL)
	{
		if(visited[p->adjvex] != 1)
			return p->adjvex;
		p = p->nextarc;
	}
	return 0;
}

int NextAdjVex(ALGraph G, int v, int w){
	ArcNode *p;
	p = G.vertices[v].firstarc;
	while(p != NULL)
	{
		if(visited[p->adjvex] != 1 && p->adjvex != w)
			return p->adjvex;
		p = p->nextarc;
	}
	return 0;
}


Status printGraph(int v){
	printf("%c", v + 'a');
	cout<<endl;
	return 1;
}


Status InitQueue(SqQueue & queue){
	queue.base = (QElemType *) malloc(MAXQSIZE * sizeof(QElemType));
	
	if (!queue.base)
		return FALSE;
	queue.front = queue.rear = 0;
	
	return TRUE;
}

///////////////////////////////////////////////////////////////////////
//
// 函數名       : EnQueue
// 功能描述     : 插入元素到隊列
// 參數         : SqQueue &queue
// 參數         : QElemType element
// 返回值       : Status
//
///////////////////////////////////////////////////////////////////////
Status EnQueue(SqQueue &queue, QElemType element)
{
 //先判斷是不是沒滿的隊列
 if ((queue.rear + 1)  % MAXQSIZE == queue.front)
  return FALSE;
 queue.base[queue.rear] = element;

 queue.rear = (queue.rear + 1) % MAXQSIZE;

 return TRUE;
}


///////////////////////////////////////////////////////////////////////
//
// 函數名       : DeQueue
// 功能描述     : 刪除隊列的頭結點
// 參數         : SqQueue &queue
// 參數         : QElemType &element
// 返回值       : Status 
//
///////////////////////////////////////////////////////////////////////
Status DeQueue(SqQueue &queue, QElemType &element)
{
 //判斷隊列是不是空的
 if (queue.front == queue.rear)
  return FALSE;
 element = queue.base[queue.front];
 queue.front = (queue.front + 1) % MAXQSIZE;
 
 return TRUE;
}

Status  QueueEmpty(SqQueue queue)
{
 if (queue.front == queue.rear)
  return FALSE;
 else
  return TRUE;

}


void Bprint(ALGraph G){
	int i;
	ArcNode *p;
	for(i= 0; i < G.vexnum; i++)
	{
		cout<<i<<"   "<<G.vertices[i].data;
		p = G.vertices[i].firstarc;
		while(p != NULL)
		{
			cout<<"--->";
			cout<<(G.vertices[p->adjvex].data);
			p = p->nextarc;   
		}
		cout<<endl;
	}
	BFSTraverse(G, printGraph);
}


void Dprint(ALGraph G){
	int i;
	ArcNode *p;
	for(i= 0; i < G.vexnum; i++) {
		cout<<i<<"   "<<G.vertices[i].data;
		p = G.vertices[i].firstarc;
		while(p != NULL)
		{
			cout<<"--->";
			cout<<(G.vertices[p->adjvex].data);
			p = p->nextarc;   
		}
		cout<<endl;
	}
	DFSTraverse(G, printGraph);

}