#include<iostream.h>
#include<iomanip.h>
#include<stdlib.h>

#define INFINITY 0
#define MAX_VERTEX_NUM 20     //最大顶点数

class Mgraph{
private:
	char vexs[MAX_VERTEX_NUM];      //顶点
	int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];  //邻接矩阵
	int vexnum, arcnum;            //顶点数，边数
	bool visited[MAX_VERTEX_NUM];    //顶点访问标志
public:
	int FirstAdjVex(int v);    //求顶点v的第一邻接点
	int NextAdjVex(int v, int w);  //求顶点v的邻接点w后的邻接点
	void Creating();
	void DFS(int v);   //从v开始的深度优先搜索
	void DFST();       //图的深度优先搜索
	void BFST();    //图的广度优先搜索
};

int Mgraph::FirstAdjVex(int v)    //求顶点v的第一邻接点
{
	for(int l = 0; l < vexnum; l++)
		if(arcs[v][l] == 1)
			return l;
	return -1;
}

int Mgraph::NextAdjVex(int v, int w)  //求顶点v的邻接点w后的邻接点
{
	for(int l = w + 1; l < vexnum; l++)
		if(arcs[v][l] == 1)
			return l;
	return -1;
}

void Mgraph::Creating()
{
	int i, j;
	cout << "请输入顶点数: " << endl;
	cin >> vexnum;
    cout << "请输入边数: " << endl;
	cin >> arcnum;
	for(i = 0; i < vexnum; i++){
		cout << "请输入第 " << i + 1 << " 顶点符号： " << endl;
		cin >> vexs[i];
	}
	for(i = 0; i < vexnum; i++)
		for(j = 0; j < vexnum; j++)
			arcs[i][j] = INFINITY;
	cout << "请输入边的信息，第一个顶点从i=0 开始记数。" << endl;
	for(int k = 1; k <= arcnum; k++){
		int i1, j1;
		cout << "请输入arcs[i][j] = w 中的i： " << endl;
		cin >> i1;
		cout << "请输入arcs[i][j] = w 中的j： " << endl;
		cin >> j1;
		arcs[i1][j1] = 1;
		arcs[j1][i1] = 1;
	}
}

void Mgraph::DFS(int v)   //从v开始的深度优先搜索
{
	visited[v] = true;
	cout << setw(3) << vexs[v];
	for(int w = FirstAdjVex(v); w >= 0; w = NextAdjVex(v, w))
		if((!visited[w]) && (w >= 0))
			DFS(w);
}

void Mgraph::DFST()       //图的深度优先搜索
{
	for(int j = 0; j < MAX_VERTEX_NUM; j++)
		visited[j] = false;
	for(int i = 0; i < vexnum; i++)
		if(!(visited[i])){ 
			DFS(i);
			cout << endl;
		}
}

typedef struct QNode{
	int data;
	struct QNode *next;
}QNode, *QueuePtr;

typedef struct{
	QueuePtr front;
	QueuePtr rear;
}LinkQueue;

bool InitQueue(LinkQueue &Q)
{
	Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
	if(!Q.front){
		cout << "Initializing a queue failed."<<endl;
		return false;
	}
	Q.front->next = 0;
	return true;
}

bool IsQueueEmpty(LinkQueue Q)
{
	if(Q.front == Q.rear)
		return true;
	return false;
}

bool EnQueue(LinkQueue &Q, int e)
{
	QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
	if(!p){
		cout << "Applying memory failed" << endl;
        return false;
	}
	p->data = e;
	p->next = 0;
	Q.rear->next = p;
	Q.rear = p;
	return true;
}

bool DeQueue(LinkQueue &Q, int &e)
{
	if(Q.front == Q.rear){
		cout << "The Queue is empty." << endl;
		return false;
	}
	QueuePtr p = Q.front->next;
	e = p->data;
	Q.front->next = p->next;
	if(Q.rear == p)
		Q.rear = Q.front;
	free(p);
	return true;
}

void Mgraph::BFST()    //图的广度优先搜索
{
	for(int j = 0; j < MAX_VERTEX_NUM; j++)
		visited[j] = false;
	LinkQueue Q;
	InitQueue(Q);
	for(int v = 0; v < vexnum; ++v){
		if(!visited[v]){
			visited[v] = true;
	        cout << setw(3) << vexs[v];
			EnQueue(Q, v);
			while(!IsQueueEmpty(Q)){
				int u;
				DeQueue(Q, u);
	            for(int w = FirstAdjVex(u); w >= 0; w = NextAdjVex(u, w))
					if((!visited[w]) && (w >= 0)){
						visited[w] = true;
						cout << setw(3) << vexs[w];
			            EnQueue(Q, w);
					}
			}
		}
		cout << endl;
	}
}

void main(void)
{
;
}