c语言数据结构广度优先遍历代码

以下是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) { // 判断队列是否为空
    if (Q->front == Q->rear) {
        return 1;
    } else {
        return 0;
    }
}

void EnQueue(Queue *Q, int x) { // 入队
    if ((Q->rear + 1) % MAX_VERTEX_NUM == Q->front) {
        printf("Queue is full!\n");
        exit(1);
    }
    Q->data[Q->rear] = x;
    Q->rear = (Q->rear + 1) % MAX_VERTEX_NUM;
}

int DeQueue(Queue *Q) { // 出队
    if (QueueEmpty(Q)) {
        printf("Queue is empty!\n");
        exit(1);
    }
    int x = Q->data[Q->front];
    Q->front = (Q->front + 1) % MAX_VERTEX_NUM;
    return x;
}

void CreateGraph(ALGraph *G) { // 创建邻接表
    printf("Please input the number of vertexes and edges:\n");
    scanf("%d%d", &G->vexnum, &G->arcnum);
    getchar();
    printf("Please input the vertexes:\n");
    for (int i = 0; i < G->vexnum; i++) {
        scanf("%c", &G->vertices[i].data);
        G->vertices[i].firstArc = NULL;
        getchar();
    }
    printf("Please input the edges:\n");
    for (int i = 0; i < G->arcnum; i++) {
        char v1, v2;
        printf("No.%d edge:\n", i + 1);
        scanf("%c%c", &v1, &v2);
        getchar();
        int m, n;
        for (m = 0; m < G->vexnum; m++) {
            if (G->vertices[m].data == v1) {
                break;
            }
        }
        for (n = 0; n < G->vexnum; n++) {
            if (G->vertices[n].data == v2) {
                break;
            }
        }
        ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));
        p->adjVex = n;
        p->nextArc = G->vertices[m].firstArc;
        G->vertices[m].firstArc = p;
        p = (ArcNode *)malloc(sizeof(ArcNode));
        p->adjVex = m;
        p->nextArc = G->vertices[n].firstArc;
        G->vertices[n].firstArc = p;
    }
}

void BFS(ALGraph *G, int v, int *visited) { // 广度优先遍历
    Queue Q;
    InitQueue(&Q);
    printf("Node: %c\n", G->vertices[v].data);
    visited[v] = 1;
    EnQueue(&Q, v);
    while (!QueueEmpty(&Q)) {
        int u = DeQueue(&Q);
        ArcNode *p = G->vertices[u].firstArc;
        while (p != NULL) {
            if (visited[p->adjVex] == 0) {
                printf("Node: %c\n", G->vertices[p->adjVex].data);
                visited[p->adjVex] = 1;
                EnQueue(&Q, p->adjVex);
            }
            p = p->nextArc;
        }
    }
}

void BFSGraph(ALGraph *G) { // 遍历所有连通分量
    int visited[MAX_VERTEX_NUM];
    for (int i = 0; i < G->vexnum; i++) {
        visited[i] = 0;
    }
    for (int i = 0; i < G->vexnum; i++) {
        if (visited[i] == 0) {
            BFS(G, i, visited);
        }
    }
}

int main() {
    ALGraph G;
    CreateGraph(&G);
    BFSGraph(&G);
    return 0;
}