#include <stdio.h>#include <stdlib.h>#define MAXVERTEX 10typedef char VertexType;                //顶点类型typedef int EdgeType;                   //边的类型typedef int ElemType;                   //队列中元素类型typedef struct EdgeNode{    int adjvex;    EdgeType weight;    struct EdgeNode *next;}EdgeNode;                              //在邻接表中存放邻接顶点下标值的结点typedef struct VertexNode{    int Flag;    int vertex;    VertexType data;    EdgeNode *firstedge;}VertexNode,AdjList[MAXVERTEX];         //定义一个MAXVERTEX个顶点的邻接表typedef struct GraphAdjList{    AdjList adjList;    int numVertex;    int numEdge;}GraphAdjList;                          //定义一个图typedef struct QNode{    ElemType qData;    struct QNode *nextNode;}QNode;                                 //定义队列的结点typedef struct QueueList{    QNode *front;    QNode *rear;}QueueList,*queue;                      //定义一个队列                                        //初始化队列void InitQueue(QueueList *Q){    Q->front = (QNode*)malloc(sizeof(QNode));    if( Q->front == NULL )    {        printf("Error!");        exit(0);    }    Q->rear = Q->front;//    Q->rear = NULL;    Q->front->nextNode = NULL;}                                        //插入一个结点到队列void InsertQueue(QueueList *Q,ElemType *e){    QNode *p;    p = (QNode *)malloc(sizeof(QNode));    p->qData = http://www.mamicode.com/*e;"请输入图的顶点数和边数，中间用英文逗号隔开 :\n");    scanf("%d,%d",&G->numVertex,&G->numEdge);    printf("请输入各个顶点中存放的数据：\n");    fflush(stdin);    scanf("%c",&c);    while(i < G->numVertex)    {        if(c == ‘\n‘)        {            break;        }        G->adjList[i].data = http://www.mamicode.com/c;"%c",&c);    }        fflush(stdin);        for(k = 0;k < G->numEdge;k++)        {            printf("请输入边Vi~Vj依附的顶点下标 i 和 j :\n");            scanf("%d,%d",&i,&j);            s = (EdgeNode*)malloc(sizeof(EdgeNode));            s->adjvex = j;            s->next = G->adjList[i].firstedge;            G->adjList[i].firstedge = s;            s = (EdgeNode*)malloc(sizeof(EdgeNode));            s->adjvex = i;            s->next = G->adjList[j].firstedge;            G->adjList[j].firstedge = s;        }}                                            //查看邻接表是否构建的正确，这个函数只是为了验证void print(GraphAdjList *G){    int i = 0;    EdgeNode *p;    for(i = 0;i < G->numVertex;i++)    {        printf("\n %d->",i);        p = G->adjList[i].firstedge;        while(p)        {            printf("%d->",p->adjvex);            p = p->next;        }        printf("End\n");    }}                                            //DFS遍历void DFSTraverse(GraphAdjList *G,int i){    int j = 0;    EdgeNode *p;    G->adjList[i].Flag = 1;    printf("%c->",G->adjList[i].data);    p = G->adjList[i].firstedge;    while(p != NULL)    {        if(G->adjList[p->adjvex].Flag == 0)        {            DFSTraverse(G,p->adjvex);        }        p = p->next;    }}                                            //判断队列是否为空int QueueEmpty(QueueList *Q){    if(Q->front == Q->rear)        return 0;    else        return 1;}                                            //BFS遍历void BFSTraverse(GraphAdjList *G){    int i = 0,k = 0,flag = 0;    EdgeNode *s;    QueueList Q;    InitQueue(&Q);    for(i = 0;i < G->numVertex;i++)    {        G->adjList[i].Flag = 0;    }    for(i = 0;i < G->numVertex;i++)    {        if(G->adjList[i].Flag == 0)        {            G->adjList[i].Flag = 1;//            printf("%c ",G->adjList[i].data);            InsertQueue(&Q,&i);            while(QueueEmpty(&Q))            {                DeleteQueue(&Q,&i);                printf("%c->",G->adjList[i].data);                s = G->adjList[i].firstedge;                while(s != NULL)                {                    k = s->adjvex;                    if(G->adjList[k].Flag == 0)                    {                        G->adjList[k].Flag = 1;//                        printf("%c ",G->adjList[k].data);                        InsertQueue(&Q,&(s->adjvex));                    }                    s = s->next;                }            }        }    }    printf("End\n");}int main(){    int k = 0;                               //深度优先遍历从第1个顶点（按输入顺序）开始    GraphAdjList *G;    CreateGraph(G);    printf("\n顶点的邻接表为:\n");    print(G);                                //按照头插法得到的邻接表    printf("\nDFS的结果是：\n");    DFSTraverse(G,k);                        //深度优先遍历    printf("End\n");    printf("\nBFS的结果是：\n");    BFSTraverse(G);                         //广度优先遍历    return;}