#include<stdio.h>
#include<stdlib.h>
#include <malloc.h>
#define False 0
#define True 1
#define Null 0
#define maxsize 20//队列的最大空间
#define maxvertexnum 20//最大顶点数
typedef struct node{
    int adjvex;//弧指向顶点的位置
    struct node *next;//指向下一条弧的指针
}edgenode;//表结点

typedef struct {//头结点
    char vertex;//顶点信息
    edgenode *link;//指向第一条依附该顶点的弧的指针
}vexnode,AdjList[maxvertexnum];

typedef struct{//图
AdjList adjlist;
int n,e;//n顶点数，e边数
}Graph;
typedef struct{//栈
    int *data;//栈底指针
    int *top;//栈顶指针
}seqstack;
//全局变量
vexnode g[maxvertexnum];//先定义后使用vexnode，邻接表g为全程变量
int visited[maxvertexnum]; //定义visit为全程向量

void CreatAdjList(Graph &G){
    int i,j,k;//i,j为邻接点序号
    edgenode *s;
    char c;
    printf("请输入定点数和边数:\n");
     scanf("%d,%d",&G.n,&G.e);
     c=getchar();
    printf("请输入顶点信息(顶点号):\n");
    for(i=1;i<=G.n;i++){//建立有n个顶点的顶点表
        printf("第%d个顶点为",i);
        scanf("%c",&G.adjlist[i].vertex);
        c=getchar();
        G.adjlist[i].link=NULL;
    }
    printf("请输入边的信息():\n");
    for(k=1;k<=G.e;k++){//建立边表
        printf("请输入请输入第%d条边起始顶点编号:\n",k);
        scanf("%d",&i);
        printf("请输入请输入第%d条边终顶点编号:\n",k);
        scanf("%d",&j);
        s=(edgenode*)malloc(sizeof(edgenode));//分配顶点空间
        s->adjvex=j;
        s->next=G.adjlist[i].link;
        G.adjlist[i].link=s;
    }
}

void DisplayAdjList(Graph G)
 {
    int i;
    edgenode *q;
    for(i=1;i<=G.n;++i)
    {
    q=G.adjlist[i].link;
    printf("%d",i);
    while(q!=NULL)
    {
    printf("->%d",q->adjvex);
    q=q->next;
    }
  printf("\n");
    }
}

void DFSAL(Graph G)
{
    edgenode *p;
    seqstack s;
    int i=1,t;
    for(i=1;i<=G.n;i++)  
        visited[i]=0;
    printf("这是深度优先遍历,遍历顺序为:\n");//输出起始顶点
    s.data=(int*)malloc(maxsize*sizeof(seqstack));
    s.top=s.data;//初始化栈   
    for(i=1;i<=G.n;i++)//考虑到图可能不连通
    {
        p=G.adjlist[i].link;   
        t=i;
            if(p==NULL)//p==NULL时,即该结点没有邻结点
            {
                if(!visited[t])               
                {
                    printf("%c",G.adjlist[t].vertex);//如果此时该结点没有被访问过,则访问
                    visited[t]=True;
                }
                continue;//即该结点没有邻结点,本次循环结束
            }
        do{
            if(p==NULL)//即到了图的最底层
            {
                s.top--;//没有下个邻接点，则退回前一个顶点
                p=G.adjlist[*s.top].link;               
                if(p!=NULL){
                    t=p->adjvex;               
                }
            }
            else if(!visited[t])//该结点中p!=NULL且其没有被访问过
            {
                printf("%c",G.adjlist[t].vertex);//输出该顶点
                visited[t]=True;//置为已访问
                if(G.adjlist[t].link==NULL)continue;               
*s.top=t;
                s.top++;//进栈               
                p=G.adjlist[t].link;//p指针指到以G.adjlist[t].vertex为起点的第一条边,如果//p==NULL               
                if(p==NULL)//如果该结点没有邻接点则输出之
                {
                    if(!visited[t])printf("%c",G.adjlist[t].vertex);                                                        
                }
                else t=p->adjvex;//如果该结点有邻接点,则把其邻接点的顶点号赋值给t
            }
            else//如果该结点被访问过,且有邻结点,p指向以当前结点的邻接点为起点的边//也可能P=NULL

            {               
                p=p->next;               
if(p!=NULL)t=p->adjvex;//如果该邻接点有邻接点,则记下其邻接点的位置
            }
        }while(s.top!=s.data);
    }
}


void BFSAL(Graph G){
    int v,Q[maxsize];
    edgenode * w;
    printf("这是广度优先遍历,遍历顺序为:\n");
    int front=0,rear=0;//辅助队列置空
    for(v=1;v<=G.n;v++)  
        visited[v]=0;   
    for(v=1;v<=G.n;v++)
       if(!visited[v])
       {
        visited[v]=1;
        printf("%c",G.adjlist[v].vertex);
        Q[rear]=v;
        rear++; //入队
        while (front!=rear)
        { //队不空
          front++;    //出队
          w=G.adjlist[v].link;
          while(w){
              if(!visited[w->adjvex])
              {
                  visited[w->adjvex]=1;// 访问w;
                  printf("%c",G.adjlist[w->adjvex].vertex);
                  Q[rear]=w->adjvex;            
                  rear++;
              }
              w=w->next;
          }
        }
       }
}
  

void main(){
    Graph G;
int choice;
    char ch;   
 printf("------创建邻接表存储的图");
CreatAdjList(G);
printf("已创建一个图了邻接表\n");
DisplayAdjList(G)
    while(ch!='n'){
         printf("\n请选择操作：");
         printf("\n1------深度优先遍历：");
         printf("\n2------广度优先遍历");
         printf("\n3-----退出\n");
     scanf("%d",&choice);
         switch(choice){
         case 1:DFSAL(G);break;
         case 2:BFSAL(G);break;
         case 3:ch='n';break;
         default:ch='n';
         }
}
     }
}