#include<iostream>
#include<iomanip>
#include<stdlib.h>
using namespace std;

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

bool visited[MAX_VERTEX_NUM];    //顶点访问标志

struct Mgraph{
	char vexs[MAX_VERTEX_NUM];      //顶点
	int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];  //邻接矩阵
	int vexnum, arcnum;            //顶点数，边数
};

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

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

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

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

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

int main(void)
{
	Mgraph g;
	Creating(g);

}