#include "stdio.h"
#define MaxVertexNum 100
typedef int VertexType;
typedef enum{FALSE,TRUE}Boolean;/*FALSE為0,TRUE為1*/
Boolean visited[MaxVertexNum]; /*訪問標志向量是全局量*/
typedef   int  datatype;
typedef	 struct	qnode{
	datatype	 data;
	struct 	qnode  *next;
} position;
typedef  struct queue{
		position 	*front;
		position 	*rear;
}queuetype;

typedef struct node{/*邊表結點*/
	int adjvex; /*鄰接點域*/
	struct node *next; /*鏈域*/
	/*若要表示邊上的權,則應增加一個數據域*/
}EdgeNode;
typedef struct vnode{ /*頂點表結點*/
	VertexType vertex; /*頂點域*/
	EdgeNode *firstedge;/*邊表頭指針*/
}VertexNode;
typedef VertexNode AdjList[MaxVertexNum];/*AdjList是鄰接表類型*/
typedef struct ALGraph{
	AdjList adjlist;/*鄰接表*/
	int n,e; /*圖中當前頂點數和邊數 */
}Graphic; /*對于簡單的應用,無須定義此類型,可直接使用AdjList類型。*/

int Dequeue(queuetype *  q)
{
	position* p;
	int data;
	p=q->front;
	q->front=q->front->next;
	data=p->data;
	free(p);
	return data;
}
// 在隊列中加入新元素：
void Enqueue(queuetype * q,datatype x)
{
	position* p;
	p=(position*)malloc(sizeof(position*));
	p->data=x;
	p->next=NULL;
	q->rear->next=p;
	q->rear=p;
}
//判斷是否為空隊列：
int Empty(queuetype * q)
{
	return (q->front==q->rear);
}
void InitQueue(queuetype *Q)
{
	///*隊列初始化*/
}
void BFS(Graphic*G,int k)
{/* 以vk為源點對用鄰接表表示的圖G進行廣度優先搜索*/
    int i;
    queuetype Q; /*須將隊列定義中DataType改為int*/
    EdgeNode *p;
    InitQueue(&Q);/*隊列初始化*/
     /*訪問源點vk*/
    printf("visit vertex：%e",G->adjlist[k].vertex);
    visited[k]=TRUE; 
    Enqueue(&Q,k);/*vk已訪問,將其人隊。（實際上是將其序號人隊）*/
    while(!Empty(&Q))
	{  /*隊非空則執行*/
        i=Dequeue(&Q); /*相當于vi出隊*/
        p=G->adjlist[i].firstedge; //取vi的邊表頭指針
        while(p){//依次搜索vi的鄰接點vj(令p->adjvex=j)
            if(!visited[p->adjvex])
			{ /*若vj未訪問過*/
			    printf("visitvertex：%c",G->adjlist[p->adjvex].vertex); 
              /*訪問vj*/
               visited[p->adjvex]=TRUE; 
               Enqueue(&Q,p->adjvex);/*訪問過的vj人隊*/
			}            
            p=p->next;/*找vi的下一鄰接點*/
		}      
	} 
}
void CreateGraphic(Graphic *G)
{/*建立無向圖的鄰接表表示*/
     	int i,j,k;
      	EdgeNode *s;
      	scanf("%d%d",&G->n,&G->e); /*讀人頂點數和邊數*/
      	for(i=0;i<G->n;i++){/*建立頂點表*/
        	G->adjlist[i].vertex=getchar(); /*讀入頂點信息*/
        	G->adjlist[i].firstedge=NULL;/*邊表置為空表*/
       	}
      	for(k=0;k<G->e;k++){/*建立邊表*/
         	scanf("%d%d",&i,&j);/*讀入邊(vi,vj)的頂點對序號*/
         	s=(EdgeNode *)malloc(sizeof(EdgeNode)); /*生成邊表結點*/
         	s->adjvex=j; /*鄰接點序號為j*/
         	s->next=G->adjlist[i].firstedge;
 	        G->adjlist[i].firstedge=s; /*將新結點*s插入頂點vi的邊表頭部*/
         	s=(EdgeNode *)malloc(sizeof(EdgeNode));
         	s->adjvex=i; /*鄰接點序號為i*/
         	s->next=G->adjlist[j].firstedge;
         	G->adjlist[j].firstedge=s; /*將新結點*s插入頂點vj的邊表頭部*/
        }   
} 
void BFSTraverse(Graphic *G)
{    
	    int i;
    	for(i=0;i<G->n;i++)
      		visited[i]=FALSE; /*標志向量初始化*/
    	for(i=0;i<G->n;i++)
      		if(!visited[i]) /*vi未訪問過*/
       BFS(G,i); /*以vi為源點開始DFS搜索*/
}
void main(void)
{
	Graphic Create;
	CreateGraphic(&Create);
	BFSTraverse(&Create);
}