邻接表储存无向图的广度优先遍历C语言

邻接表是一种常见的图的存储结构，它由一个一维数组和若干个链表组成。其中，数组中的每个元素表示一个顶点，每个顶点对应的链表中存储了与该顶点相邻的所有顶点。广度优先遍历是一种图的遍历算法，它从图的某个顶点开始，依次访问该顶点的所有邻接点，然后再依次访问这些邻接点的邻接点，直到遍历完整个图。

下面是使用邻接表储存无向图的广度优先遍历的C语言代码：

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

#define MAX_VERTEX_NUM 100 // 最大顶点数

// 邻接表中的边结构体
typedef struct EdgeNode {
    int adjvex; // 邻接点在数组中的位置下标
    struct EdgeNode *next; // 指向下一个邻接点的指针
} EdgeNode;

// 邻接表中的顶点结构体
typedef struct VertexNode {
    int vertex; // 顶点的值
    EdgeNode *firstedge; // 指向第一个邻接点的指针
} VertexNode;

// 邻接表结构体
typedef struct {
    VertexNode adjlist[MAX_VERTEX_NUM]; // 顶点数组
    int vertex_num, edge_num; // 顶点数和边数
} AdjList;

// 初始化邻接表
void InitAdjList(AdjList *a, int n) {
    a->vertex_num = n;
    a->edge_num = 0;
    for (int i = 0; i < n; i++) {
        a->adjlist[i].vertex = i;
        a->adjlist[i].firstedge = NULL;
    }
}

// 添加边
void AddEdge(AdjList *a, int u, int v) {
    EdgeNode *e = (EdgeNode *)malloc(sizeof(EdgeNode));
    e->adjvex = v;
    e->next = a->adjlist[u].firstedge;
    a->adjlist[u].firstedge = e;
    a->edge_num++;
}

// 广度优先遍历
void BFS(AdjList *a, int v) {
    int visited[MAX_VERTEX_NUM] = {0}; // 标记数组，用于记录每个顶点是否被访问过
    int queue[MAX_VERTEX_NUM], front = 0, rear = 0; // 队列，用于存储待访问的顶点
    EdgeNode *e;

    printf("%d ", v);
    visited[v] = 1;
    queue[rear++] = v;

    while (front != rear) {
        int u = queue[front++];
        for (e = a->adjlist[u].firstedge; e != NULL; e = e->next) {
            int w = e->adjvex;
            if (!visited[w]) {
                printf("%d ", w);
                visited[w] = 1;
                queue[rear++] = w;
            }
        }
    }
}

// 主函数
int main() {
    int n, m, u, v;
    AdjList a;

    printf("请输入顶点数和边数：");
    scanf("%d%d", &n, &m);

    InitAdjList(&a, n);

    printf("请输入每条边的两个端点：\n");
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &u, &v);
        AddEdge(&a, u, v);
        AddEdge(&a, v, u);
    }

    printf("广度优先遍历结果为：");
    BFS(&a, 0);
    printf("\n");

    return 0;
}