#include<stdio.h>
#include<stdlib.h>
int visited[MAX_VERTEX_NUM];

typedef struct ArcNode{
    int adjvex;
    struct ArcNode *nextarc;
}ArcNode;

typedef struct{
    char     data;
    ArcNode  *firstarc;
}Adjlist[MAX_VERTEX_NUM];

typedef struct{
    Adjlist   vertices;
    int   vexnum,arcnum;
}AlGraph;

int locate(AlGraph G,char V)
{//查找G中v节点的位置并返回其值
    int i=-1;
    while(i<G.vexnum&&G.vertices[i].data!=V)
        i++;
    if(i<G.vexnum)
        return i;
    return -1;
        
}
void CreatAdjlist (AlGraph &G)
{
    int i,j,v,k;
    ArcNode *p;
    char v1,v2;
    printf("输入无向图的顶点数和边数：\n");
    scanf("%d%d",&G.vexnum,&G.arcnum);
    getchar();
    printf("输入无向图G的各顶点：");
    for(v=0;v<G.vexnum;v++)
    {
        scanf("%c",&G.vertices[v].data);
        G.vertices[v].firstarc=NULL;
    }
    printf("输入无向图的边:");
    for(k=0;k<G.arcnum;k++)
    {
        getchar();
        scanf("%c%c",&v1,&v2);
        i=locate(G,v1);
        j=locate(G,v2);
        p=(ArcNode*)malloc(sizeof(ArcNode));
        p->adjvex=j;
        p->nextarc=G.vertices[i].firstarc;
        G.vertices[i].firstarc=p;//利用头插法建立单链表
        p=(ArcNode*)malloc(sizeof(ArcNode));
        p->adjvex=i;
        p->nextarc=G.vertices[j].firstarc;
        G.vertices[j].firstarc=p;
    }//for
}

void visit(AlGraph G,int v)
{//访问G图中第V个结点
    printf("%3c",G.vertices[v].data);
}



void DFS(AlGraph G,int v)
{//从第v个顶点开始非递归地深度优先遍历G图
    int top;
    ArcNode *p;
    ArcNode *S[MAX_VERTEX_NUM];
    visit(G,v);
    visited[v]=1;
    top=0;
    p=G.vertices[v].firstarc;
    while(top>0||p)
    {
        while(p)
            if(visited[p->adjvex])
                     p=p->nextarc;
             else 
                   {
                        visit(G,p->adjvex);
                        visited[p->adjvex]=1;
                        S[top++]=p;
                        p=G.vertices[p->adjvex].firstarc;
                     }
          if(top>0)
               {
                   p=S[--top];
                   p=p->nextarc;
                }
        }
}


void BFS(AlGraph G,int v)
{//从第v个顶点出发非递归地广度优先遍历G图
    ArcNode *p;
    int Q[MAX_VERTEX_NUM];
    int front, rear;
    visit(G,v);
    visited[v]=1;
    front=rear=0;
    Q[rear++]=v;
    while(front<rear)
    {
        v=Q[front++];
        p=G.vertices[v].firstarc;
        while(p)
        {
            if(!visited[p->adjvex])
            {
                visit(G,p->adjvex);
                visited[p->adjvex]=1;
                Q[rear++]=p->adjvex;
            }
            p=p->nextarc;
        }
    }
}
void DTraverse(AlGraph G)
{//广度优先遍历图G
    int v;
    for(v=0;v<G.vexnum;v++)
        visited[v]=0;
    printf("\n该无向图的深度优先地遍历为：");
    for(v=0;v<G.vexnum;v++)
      if(!visited[v])
            DFS(G,v);
   
}
void BTraverse(AlGraph G)
{//广度优先遍历图G
    int v;
    for(v=0;v<G.vexnum;v++)
        visited[v]=0;
     printf("\n该无向图的广度优先地遍历为：");    
    for(v=0;v<G.vexnum;v++)
        if(!visited[v])
            BFS(G,v);
}
    
void main()
{
    AlGraph G;
    CreatAdjlist(G);
    DTraverse(G);
    BTraverse(G);
}