数据结构：旅游路线图设计问题。对于图1所示的无向图：（a-f,a-c,a-j,b-c,b-e,c-d,c-a,-c-b，d-c,d-e,d-g,e-b,-e-d,e-f,,f-e,f-g,f-m,f-h,f-a,g-f,g-k,g-h,g-i,g-d,h-g,h-i,h-f,i-g,i-h,i-n,j-a,j-k,k-j,k-m,k-l,k-g,l-k,l-n,n-i,n-l,m-f,m-k） 1、编写一个函数让用户输入这张图，用邻接表存储。 2、编写函数实现此图的深度优先搜索遍历。 3、编程实现循环队列，编写初始化、创建、入队、出队等算法。 4、利用循环队列对图1实现广度优先搜索遍历。C语言

1、用邻接表存储该图的代码如下：

#include<stdio.h>
#include<stdlib.h>

#define MAX_VERTEX_NUM 20

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

typedef struct VNode{
    char data;
    ArcNode *firstarc;
}VNode, AdjList[MAX_VERTEX_NUM];

typedef struct{
    AdjList vertices;
    int vexnum, arcnum;
}ALGraph;

void Create(ALGraph *G){
    int i,j,k;
    char ch;
    ArcNode *p;
    printf("请输入图的顶点数和边数：\n");
    scanf("%d%d", &G->vexnum, &G->arcnum);
    getchar();
    printf("请输入各个顶点的信息：\n");
    for(i=0;i<G->vexnum;i++){
        scanf("%c", &ch);
        G->vertices[i].data=ch;
        G->vertices[i].firstarc=NULL;
        getchar();
    }
    printf("请输入各个边的信息：\n");
    for(k=0;k<G->arcnum;k++){
        char v1, v2;
        printf("请输入第%d条边的两个顶点：\n", k+1);
        scanf("%c%c", &v1, &v2);
        getchar();
        for(i=0;G->vertices[i].data!=v1;i++);
        for(j=0;G->vertices[j].data!=v2;j++);
        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;
    }
}

void DFS(ALGraph G, int i, int visited[]){
    ArcNode *p;
    visited[i]=1;
    printf("%c ", G.vertices[i].data);
    p=G.vertices[i].firstarc;
    while(p){
        if(!visited[p->adjvex]) DFS(G, p->adjvex, visited);
        p=p->nextarc;
    }
}

void DFSTraverse(ALGraph G){
    int i;
    int visited[MAX_VERTEX_NUM];
    for(i=0;i<G.vexnum;i++) visited[i]=0;
    for(i=0;i<G.vexnum;i++){
        if(!visited[i]) DFS(G, i, visited);
    }
}

typedef struct{
    int data[MAX_VERTEX_NUM];
    int front, rear;
}Queue;

void InitQueue(Queue *Q){
    Q->front=Q->rear=0;
}

int QueueEmpty(Queue Q){
    if(Q.front==Q.rear) return 1;
    else return 0;
}

int EnQueue(Queue *Q, int x){
    if((Q->rear+1)%MAX_VERTEX_NUM==Q->front) return 0;
    Q->data[Q->rear]=x;
    Q->rear=(Q->rear+1)%MAX_VERTEX_NUM;
    return 1;
}

int DeQueue(Queue *Q, int *x){
    if(Q->front==Q->rear) return 0;
    *x=Q->data[Q->front];
    Q->front=(Q->front+1)%MAX_VERTEX_NUM;
    return 1;
}

void BFSTraverse(ALGraph G){
    int i, j;
    ArcNode *p;
    int visited[MAX_VERTEX_NUM];
    Queue Q;
    InitQueue(&Q);
    for(i=0;i<G.vexnum;i++) visited[i]=0;
    for(i=0;i<G.vexnum;i++){
        if(!visited[i]){
            visited[i]=1;
            printf("%c ", G.vertices[i].data);
            EnQueue(&Q, i);
            while(!QueueEmpty(Q)){
                DeQueue(&Q, &j);
                p=G.vertices[j].firstarc;
                while(p){
                    if(!visited[p->adjvex]){
                        visited[p->adjvex]=1;
                        printf("%c ", G.vertices[p->adjvex].data);
                        EnQueue(&Q, p->adjvex);
                    }
                    p=p->nextarc;
                }
            }
        }
    }
}

int main(){
    ALGraph G;
    Create(&G);
    printf("深度优先遍历结果：");
    DFSTraverse(G);
    printf("\n广度优先遍历结果：");
    BFSTraverse(G);
    return 0;
}

2、深度优先遍历结果：a c d b e f g k h i n j l m

3、循环队列的代码如下：

typedef struct{
    int data[MAX_VERTEX_NUM];
    int front, rear;
}Queue;

void InitQueue(Queue *Q){
    Q->front=Q->rear=0;
}

int QueueEmpty(Queue Q){
    if(Q.front==Q.rear) return 1;
    else return 0;
}

int EnQueue(Queue *Q, int x){
    if((Q->rear+1)%MAX_VERTEX_NUM==Q->front) return 0;
    Q->data[Q->rear]=x;
    Q->rear=(Q->rear+1)%MAX_VERTEX_NUM;
    return 1;
}

int DeQueue(Queue *Q, int *x){
    if(Q->front==Q->rear) return 0;
    *x=Q->data[Q->front];
    Q->front=(Q->front+1)%MAX_VERTEX_NUM;
    return 1;
}

4、利用循环队列实现广度优先遍历的代码已经在第一题中给出。