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) { // 判断队列是否为空
    return Q->front == Q->rear;
}

void EnQueue(Queue *Q, int x) { // 入队
    Q->data[Q->rear++] = x;
}

int DeQueue(Queue *Q) { // 出队
    return Q->data[Q->front++];
}

void BFSTraverse(ALGraph *G) { // 广度优先遍历
    int visited[MAX_VERTEX_NUM] = {0}; // 访问标记数组
    Queue Q;
    ArcNode *p;
    int v, w;

    InitQueue(&Q); // 初始化队列

    for (v = 0; v < G->vexnum; v++) { // 初始化访问标记数组
        visited[v] = 0;
    }

    for (v = 0; v < G->vexnum; v++) { // 对每个连通分量调用一次BFS
        if (!visited[v]) {
            visited[v] = 1;
            printf("%c ", G->vertices[v].data); // 访问第v个顶点
            EnQueue(&Q, v); // 第v个顶点入队

            while (!QueueEmpty(&Q)) { // 队列不为空时循环
                v = DeQueue(&Q); // 出队
                p = G->vertices[v].firstarc;

                while (p != NULL) { // 访问v的所有邻接点
                    w = p->adjvex;

                    if (!visited[w]) {
                        visited[w] = 1;
                        printf("%c ", G->vertices[w].data); // 访问第w个顶点
                        EnQueue(&Q, w); // 第w个顶点入队
                    }

                    p = p->nextarc;
                }
            }
        }
    }
}

int main() {
    ALGraph G;
    int i, j, k;
    char c;

    printf("请输入顶点数和边数：");
    scanf("%d%d", &G.vexnum, &G.arcnum);

    getchar(); // 读取回车符

    printf("请输入顶点信息：");

    for (i = 0; i < G.vexnum; i++) { // 输入顶点信息，建立顶点表
        scanf("%c", &c);
        G.vertices[i].data = c;
        G.vertices[i].firstarc = NULL;
        getchar(); // 读取回车符
    }

    for (k = 0; k < G.arcnum; k++) { // 建立边表
        printf("请输入边(vi, vj)的顶点序号：");
        scanf("%d%d", &i, &j);

        ArcNode *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;
    }

    printf("广度优先遍历结果为：");
    BFSTraverse(&G);
    printf("\n");

    return 0;
}