////2012.03.26  by zhengshihao

#include<stdio.h>
#define GRAPHMAX 10
#define FALSE 0
#define TRUE 1
#define Error printf
#define QueueSize 30

typedef struct
{
	char vexs[GRAPHMAX];
	int edges[GRAPHMAX][GRAPHMAX];
	int n,e;
}Mgraph;
int visited[10];
typedef struct
{
	int front,rear,count;
	int data[QueueSize];
}CirQueue;

void InitQueue(CirQueue* q)
{
	q->front=q->rear=0;
	q->count=0;
}

int QueueEmpty(CirQueue* q)
{
	return q->count==0;   
}

int QueueFull(CirQueue* q)
{
	return q->count==QueueSize; 
}

void EnQueue(CirQueue* q,int x)
{
	if(QueueFull(q))
	  Error("Queue overflow");
    else{
    	q->count++;
    	q->data[q->rear]=x;
    	q->rear=(q->rear+1)%QueueSize;
    }
}

int DeQueue(CirQueue* q)
{
	int temp;
	if(QueueEmpty(q)){
		Error("Queue underflow");
		return NULL;
	}
	else{
		temp=q->data[q->front];
		q->count--;
		q->front=(q->front+1)%QueueSize;
		return temp;
	}
}

void CreateMGraph(Mgraph* g)
{
	int i,j,k;
	char ch1,ch2;
	printf("\n\t\t请输入定点数，边数并按回车（格式如：3,4）：");
	scanf("%d,%d",&(g->n),&(g->e));
	for(i=0;i<g->n;i++)
	{
		getchar();
		printf("\n\t\t请输入第%d个定点并回车：",i+1);
		scanf("%c",&(g->vexs[i])); 
	}
	for(i=0;i<g->n;i++)
	  for(j=0;j<g->n;j++)
	    g->edges[i][j]=0;
    for(k=0;k<g->e;k++)
    {
    	getchar();
    	printf("\n\t\t请输入第%d条边的顶点序号（格式如：i，j）：",k+1);
    	scanf("%c,%c",&ch1,&ch2);
    	for(i=0;ch1!=g->vexs[i];i++);
  	    for(j=0;ch2!=g->vexs[j];j++);
  	    g->edges[i][j]=1;
    }
}

void DFSM(Mgraph* g,int i)
{
	int j;
	printf("\n\t\t深度优先遍历序列：%c\n",g->vexs[i]);
	visited[i]=TRUE;
	for(j=0;j<g->n;j++)
	  if(g->edges[i][j]==1&&!visited[j])DFSM(g,j);
}

void BFSM(Mgraph *g,int k)
{
	int i,j;
	CirQueue q;
	InitQueue(&q);
	printf("\n\t\t广度优先遍历序列：%c\n",g->vexs[k]);
	visited[k]=TRUE;
	EnQueue(&q,k);
	while(!QueueEmpty(&q))
	{
		i=DeQueue(&q);
		for(j=0;j<g->n;j++)
		if(g->edges[i][j]==1&&!visited[j])
		{
			visited[j]=TRUE;
			printf("\n\t\t广度优先遍历序列：%c\n",g->vexs[j]);
			EnQueue(&q,j);
		}
	}
}

void DFSTraverseM(Mgraph* g)  //深度优先遍历 
{
	int i;
	for(i=0;i<g->n;i++)
	visited[i]=FALSE;
	for(i=0;i<g->n;i++)
	if(!visited[i])DFSM(g,i);
}

void BFSTraverseM(Mgraph* g)  //广度优先遍历 
{
	int i;
	for(i=0;i<g->n;i++)
	visited[i]=FALSE;
	for(i=0;i<g->n;i++)
	if(!visited[i])BFSM(g,i);
}
 
int main()
{
	Mgraph *g,a;
	char ch1;
	int i,ch2;
	g=&a;
	printf("\n\t\t建立一个有向图的邻接矩阵表示\n");
	CreateMGraph(g);
	printf("已建立一个有向图的邻接矩阵存储\n");
	for(i=0;i<g->n;i++)
	{
		printf("\n\t\t");
		for(j=0;j<g->n;j++)
		printf("%5d",g->edges[i][j]);
	}
	getchar();
	ch1='y';
	while(ch1=='y'||ch1=='Y')
	{
		printf("\n");
		printf("\n\t\t       图的存储和遍历        ");
		printf("\n\t\t*****************************");
		printf("\n\t\t    1----更新邻接矩阵        ");
		printf("\n\t\t    2----深度优先遍历        ");
		printf("\n\t\t    3----广度优先遍历        ");
		printf("\n\t\t    0----退        出        ");
		printf("\n\t\t*****************************");
		printf("\n\t\t  请选择菜单号（0--3）：");
		scanf("%d",&ch2);
		getchar();
		switch(ch2)
		{
			case 1:CreateMGraph(g);
			       printf("\n\t\t图的邻接矩阵建立完成\n");break;
            case 2:DFSTraverseM(g);break;
            case 3:BFSTraverseM(g);break;
            case 0:ch1='n';break;
            default:printf("\n\t\t输出错误！请重新输入！");
		} 
	}
}