#include<iostream>

using namespace std;

typedef struct qnode

{

    int  data;

    struct qnode *next ;

}qnode,*queueptr;

typedef struct

{

    queueptr front;

    queueptr rear;

}linkqueue;

///

int initqueue(linkqueue &q)

{        

    q.front=q.rear=(queueptr)malloc (sizeof(qnode));

    if(!q.front)

        return 0;

    q.front->next=NULL;

    return 1;

}

//滚动回收指针

int queueempty(linkqueue &q )

{

    if(q.front==q.rear )

        return 1;    

    return 0;

}

///在队尾插入新的元素e

int enqueue(linkqueue &q,int &e)

{

    

    queueptr p=(queueptr)malloc(sizeof(qnode));

    if(!p)

       return 0;

    p->data=e;

    p->next=NULL;

    q.rear->next=p;

    q.rear =p;

    

    return 1;

}

/

int dequeue(linkqueue &q,int &e)

{   

      

    if(q.front==q.rear )

        return 0;    

    queueptr p=q.front->next;    

    e=p->data;    

    q.front->next=p->next;

    if(q.rear==p)

        q.rear=q.front;//当只剩下一个时需修改尾指针

    free(p);

    return e;

}

//

typedef struct Arcnode

{  int adjvex;//该弧所指的顶点的位置；

   struct Arcnode  *nextarc;//指向下一条弧的指针；

}Arcnode;

typedef struct{

int date;//顶点信息；

Arcnode *firstarc;//指向第一条依附该顶点的弧的指针；

}Vnode,Adjlist[30];

typedef struct

{

Adjlist vertices;//

int vexnum,arcnum;//图的当前顶点数和弧数；

}Algraph;

void create(Algraph &g,int a,int b)

{        

        int i;int v1,v2; Arcnode*t1,*t2;

        g.vexnum=a;g.arcnum=b;

        cout<<"请输入"<<g.vexnum<<"节点元素（整型int）"<<endl;

        for(i=0;i<g.vexnum;i++)

        {cin>>g.vertices[i].date ;

        g.vertices[i].firstarc=NULL;

        }

        cout<<"请输入（两个节点编号构成一条有向边）"<<g.arcnum <<"边"<<endl;

                   for(i=0;i<g.arcnum;i++)

                   {

                      cout<<"第"<<i+1<<endl;

                      cin>>v1>>v2;

                     Arcnode*p=new Arcnode;

                     p->adjvex=v2;p->nextarc=NULL;

                     t1=g.vertices[v1].firstarc;

                     if(!t1)g.vertices[v1].firstarc=p;

                     else

                     {while(t1){t2=t1; t1=t1->nextarc;}                    

                     t2->nextarc=p;}

                    

                     p=new Arcnode;

                     p->adjvex=v1;p->nextarc=NULL;

                     t1=g.vertices[v2].firstarc;

                     if(!t1)g.vertices[v2].firstarc=p;

                     else

                     {while(t1){t2=t1; t1=t1->nextarc;}                    

                     t2->nextarc=p;}

                   }

}

bool visited[30];

void visitfun(Algraph &g,int i)

{

  cout<<g.vertices[i].date<<",";

}

int firstadjvex(Algraph &g,int i){

        if(g.vertices[i].firstarc)

        return g.vertices[i].firstarc->adjvex ;

        

        return -1;

}

int  nextadjvex(Algraph & g,int i,int w){

         Arcnode *p=g.vertices[i].firstarc;

        while(p->nextarc  && w!=p->adjvex  ){p=p->nextarc;}

        if(p->nextarc ) return p->nextarc->adjvex;

        return -1;

         

}

void dfs(Algraph &g,int i){

visited[i]=true;

visitfun(g,i);

for(int w=firstadjvex(g,i); w>=0; w=nextadjvex(g,i,w))

 if(!visited[w])dfs(g,w);

}

void dfsT(Algraph &g)//深度优先遍历；

{    bool a=false;int n;

    for(int i=0;i<g.vexnum;i++)

        visited[i]=false;

    cout<<"请输入遍历的起始节点编号"<<endl;

      cin>>n;

    for(i=0;i<g.vexnum;i++)

    {    if(!a) i=n;

        if(!visited[i])dfs(g,i);

        if(!a){i=-1;a=true;}

    }

}

void bfs(Algraph &g)//广度优先遍历；

{      int j;linkqueue Q;int n;bool a=false;

        for(int i=0;i<g.vexnum;i++)visited[i]=false;

        initqueue(Q);

        cout<<"请输入遍历的起始节点编号"<<endl;

         cin>>n;

        for( i=0;i<g.vexnum;i++)

        {    if(!a) i=n;

            if(!visited[i])

            {

                visited[i]=true;    visitfun(g,i);

               enqueue(Q,i);

                   while(!queueempty(Q))

                   {

                       dequeue(Q,j);

                       for(int w=firstadjvex(g,j); w>=0; w=nextadjvex(g,j,w))

                           if(!visited[w])

                           {

                           visited[w]=true;visitfun(g,w);

                            enqueue(Q,w);

                           }//if

                

                    }//while

            }//if

            if(!a){i=-1;a=true;}

        }

}

void show(Algraph &gp1)

{

            Arcnode *p;

        for(int i=0;i<gp1.vexnum ;i++)

        { cout<<endl;

            cout<<"---"<<gp1.vertices[i].date<<",";

          p=gp1.vertices[i].firstarc ;

          while(p){

              cout<<p->adjvex<<",";

              p=p->nextarc;  

                }

        }

}

void main()

{

int num1,num2;

Algraph gp1;

cout<<"请输入节点个数和边数"<<endl;

cin>>num1>>num2;

create(gp1,num1,num2);

cout<<endl<<"深度优先遍历"<<endl;

dfsT(gp1);

cout<<endl<<"广度优先遍历"<<endl;

bfs(gp1);

}