#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define null 0
#define MAX_VERTEX_NUM 30
typedef enum {unvisited,visited}VisitIf;
typedef struct EBox{
    VisitIf mark;
    int ivex,jvex;
    struct EBox*ilink,*jlink;
}EBox;
typedef struct VexBox{
    int data;
    EBox *firstedge;
}VexBox;
typedef struct{
    VexBox adjmulist[MAX_VERTEX_NUM];
    int vexnum,edgenum;
}AMLGraph;
typedef struct QNode{
    int data;
    struct QNode*next;
}QNode,*QueuePtr;
typedef struct{
    QueuePtr front;
    QueuePtr rear;
}LinkQueue;
void CreatGraph(AMLGraph &G)
{
    int i,j,n,e,k;
    int v1,v2;
    EBox *q;
    printf("\n输入图中顶点个数n和边数e:\n");
    scanf("%d,%d",&n,&e);
    G.vexnum=n,G.edgenum=e;
    for(k=1;k<=n;k++)
    {
        G.adjmulist[k].firstedge=null;
        G.adjmulist[k].data=k;
    }
    printf("\n输入图中各边，次序为弧尾编号，弧头编号:\n");
    for(k=1;k<=e;k++)
    {
        printf("第%d边:",k);
        scanf("%d,%d",&v1,&v2);
        i=v1,j=v2;
        q=(EBox*)malloc(sizeof(EBox));
        q->ivex=i,q->jvex=j;
        q->ilink=G.adjmulist[i].firstedge;
        G.adjmulist[i].firstedge=q;
        q->jlink=G.adjmulist[j].firstedge;
        G.adjmulist[j].firstedge=q;
    }
}
void DFSTraverse(AMLGraph G,int n)
{
    void DFS(AMLGraph,int,int visited[]);
    int i,visited[MAX_VERTEX_NUM]={0};

    for(i=1;i<=n;i++)visited[i]=0;
    for(i=1;i<=n;i++)
        if(visited[i]==0)DFS(G,i,visited);
}
void DFS(AMLGraph G,int k,int visited[])
{
    EBox *p;
    int w;
    visited[k]=1;
    printf("%d,",G.adjmulist[k].data);
    p=G.adjmulist[k].firstedge;
    w=p->jvex;
    while(p!=null)
    {
        if(visited[w]==0)DFS(G,w,visited);
        p=p->jlink;
        w=p->jvex;
    }
    
}
int InitQueue(LinkQueue &q)
{
    q.front=q.rear=(QueuePtr)malloc(sizeof(QNode));
    if(!q.front)exit(0);
    q.front->next=NULL;
    return 1;
}
int EnQueue(LinkQueue &q,int e)
{
    QNode*p;
    p=(QueuePtr)malloc(sizeof(QNode));
    if(!p)exit(0);
    p->data=e;
    p->next=NULL;
    q.rear->next=p;
    q.rear=p;
    return 1;
}
int DeQueue(LinkQueue &q,int &e)
{
    QueuePtr p;
    if(q.front==q.rear)return 0;
    p=q.front->next;
    e=p->data;
    q.front->next=p->next;
    if(q.rear==p)q.rear=q.front;
    free(p);
    return 1;
}
int QueueEmpty(LinkQueue Q)
{
    if(Q.front==Q.rear)return 1;
    else return 0;
}
void BFSTraverse(AMLGraph G,int k)
{
    EBox*p;
    LinkQueue Q;
    int w,visited[MAX_VERTEX_NUM];
    InitQueue(Q);
    printf("%d,",G.adjmulist[k].data);
    EnQueue(Q,k);
    while(!QueueEmpty(Q))
    {
        DeQueue(Q,w);
        p=G.adjmulist[w].firstedge;
        while(p!=null)
        {
            if(visited[p->jvex]==0)
            {
                visited[p->jvex]=1;
                printf("%d,",G.adjmulist[p->jvex].data);
                EnQueue(Q,p->jvex);
            }
            p=p->jlink;
        }
    }
}
void main()
{
    AMLGraph G;
    
    int k;
    printf("遍历的起点:");
    scanf("%d",&k);
    CreatGraph(G);
    DFSTraverse(G,G.vexnum);
    BFSTraverse(G,k);
}