C语言使用邻接链表为存储结构，完成图的非递归层次遍历算法

使用邻接链表作为存储结构的图的非递归层次遍历算法如下：

#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;

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

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

int QueueEmpty(Queue Q) {
    return Q.front == Q.rear;
}

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

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

int LocateVex(ALGraph G, char v) {
    for (int i = 0; i < G.vexnum; i++) {
        if (G.vertices[i].data == v) {
            return i;
        }
    }
    return -1;
}

void CreateGraph(ALGraph *G) {
    printf("请输入顶点数和弧数：");
    scanf("%d%d", &G->vexnum, &G->arcnum);
    getchar();
    printf("请输入顶点信息：");
    for (int i = 0; i < G->vexnum; i++) {
        scanf("%c", &G->vertices[i].data);
        G->vertices[i].firstarc = NULL;
    }
    getchar();
    printf("请输入弧的信息：\n");
    for (int k = 0; k < G->arcnum; k++) {
        char v1, v2;
        printf("请输入第%d条弧的顶点1和顶点2：", k + 1);
        scanf("%c%c", &v1, &v2);
        getchar();
        int i = LocateVex(*G, v1);
        int j = LocateVex(*G, v2);
        ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));
        p->adjvex = j;
        p->nextarc = G->vertices[i].firstarc;
        G->vertices[i].firstarc = p;
    }
}

void BFS(ALGraph G, int v, int visited[]) {
    Queue Q;
    InitQueue(&Q);
    visited[v] = 1;
    printf("%c ", G.vertices[v].data);
    EnQueue(&Q, v);
    while (!QueueEmpty(Q)) {
        int u = DeQueue(&Q);
        ArcNode *p = G.vertices[u].firstarc;
        while (p) {
            int w = p->adjvex;
            if (!visited[w]) {
                visited[w] = 1;
                printf("%c ", G.vertices[w].data);
                EnQueue(&Q, w);
            }
            p = p->nextarc;
        }
    }
}

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

int main() {
    ALGraph G;
    CreateGraph(&G);
    printf("非递归层次遍历结果为：");
    BFSTraverse(G);
    printf("\n");
    return 0;
}