#include<stdio.h>
#include<stdlib.h>
#define MaxVex 100
int visited[MaxVex]; //定义全局数组，用于记录图中节点的访问状态

typedef struct EdgeNode{ //定义边节点
    int adjvex;          //该邻接点在顶点数组中的下标
    struct EdgeNode *next;//指向下一个邻接点
}EdgeNode;

typedef struct VexNode{ //顶点节点 
    char data;//顶点信息
    EdgeNode *firstedge; //边表头指针(指向第一条依附于该顶点的边的指针)
}VexNode,Adjlist[MaxVex];//结构体数组，储存顶点

typedef struct Graph{//图结构体
    Adjlist adjlist;//结构体数组，储存所有的顶点
    int numVexs,numEdges;//顶点的数量、边的总数。
}Graph;
//队列相关
typedef struct queue
{
    int data[MaxVex];//用于记录顶点；
    int front;
    int rear;
}queue;

void initqueue(queue* Q){//初始化队列
    Q->front=Q->rear=0;
}

int isfull(queue *Q){//判断队列是否满
    if(Q->front==Q->rear){
        return 1;
    }
    else return 0;
}

void inqueue(queue *Q,int e){//入队函数
    if(!isfull(Q)){
        Q->data[Q->rear]=e;
        Q->rear++;
    }
}

int outqueue(queue *Q){//出队函数
    int temp=Q->data[Q->front];
    Q->front++;
    return temp;
}

//******  建立图的邻接表结构 ******
void createGraph(Graph *G){
    /*if(G==NULL){//为图节点开辟空间
        G=(Graph*)malloc(sizeof(Graph));
    }*/
    printf("请输入图的顶点数和边数(以逗号隔开):\n");
    scanf("%d,%d",&G->numVexs,&G->numEdges);
    getchar();//缓冲回车
    printf("输入顶点数据:\n");
    int i;
    for(i=0;i<G->numVexs;i++){
        scanf("%c",&(G->adjlist[i].data));
        G->adjlist[i].firstedge=NULL;//置空边节点。
        getchar();//缓冲回车
    }
    int j,temp1,temp2;
    for(j=0;j<G->numEdges;j++){
        printf("输入边对应的两个顶点序号(以逗号隔开):\n");
        scanf("%d,%d",&temp1,&temp2);
        EdgeNode *p= (EdgeNode*)malloc(sizeof(EdgeNode));//为边节点开辟空间
        p->adjvex=temp2;
        p->next=G->adjlist[temp1].firstedge;
        G->adjlist[temp1].firstedge=p;

        p=(EdgeNode*)malloc(sizeof(EdgeNode));
        p->adjvex=temp1;
        p->next=G->adjlist[temp2].firstedge;
        G->adjlist[temp2].firstedge=p;

    }
}

void DFS(Graph *G,int i){
    visited[i]=1;//标记已访问
    printf("%c ",G->adjlist[i].data);//输入顶点数据
    EdgeNode *p=G->adjlist[i].firstedge;//p指向与该顶点相连的第一条边
    while (p!=NULL)//一直遍历这个顶点的边，直到指针为空
    {
        if (!visited[p->adjvex])
        {
            DFS(G,p->adjvex);//递归深度遍历
        }
        p=p->next;
    }
}

void DFSTraverse(Graph* G){
    int i;
    for(i=0;i<G->numVexs;i++){
        visited[i]=0;//初始化顶点数组
    }
    for(i=0;i<G->numVexs;i++){
        if(!visited[i]){
            DFS(G,i);
        }
    }
}

void BFSTraverse(Graph *G){
    //建立队列
    queue Q;
    initqueue(&Q);//初始化队列
    int i;
    for(i=0;i<G->numVexs;i++){
        visited[i]=0;
    }//清除遍历记录
    for(i=0;i<G->numVexs;i++){
        if(!visited[i]){//选定一个节点，入队。
            visited[i]=1;
            printf("%c ",G->adjlist[i].data);
            inqueue(&Q,i);
            
        }
        if(!isfull(&Q)){
            i=outqueue(&Q);//取对头元素，依次通过边节点来输出其邻接点对应的数值，同时将邻接点入队。
            EdgeNode *p=G->adjlist[i].firstedge;
            while (p!=NULL)
            {
                if(!visited[p->adjvex]){
                    visited[p->adjvex]=1;
                     printf("%c",G->adjlist[p->adjvex]);
                    inqueue(&Q,p->adjvex);
                }
                p=p->next;//指向通向下一个临界点的边
            }
            
        }
    }

}
int main(){
    Graph G;//初始置空，在函数中为图节点开辟空间
    createGraph(&G);//创建图
    printf("\n图的深度优先遍历为:\n");
    DFSTraverse(&G);
    printf("\n图的广度优先遍历为:\n");
    BFSTraverse(&G);
    return 0;

}