c语言无向图的广度优先遍历

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

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

#define MAX_VERTEX_NUM 100 // 最大顶点数

// 邻接表中边结点的定义
typedef struct ArcNode{
    int adjvex; // 该边指向的顶点位置
    struct ArcNode *next; // 指向下一条边的指针
}ArcNode;

// 邻接表中顶点结点的定义
typedef struct VNode{
    int data; // 顶点值
    ArcNode *firstarc; // 指向第一条依附该顶点的边的指针
}VNode, AdjList[MAX_VERTEX_NUM];

// 邻接表的定义
typedef struct{
    AdjList vertices; // 邻接表中的顶点数组
    int vexnum; // 顶点数
    int arcnum; // 边数
}ALGraph;

// 初始化邻接表
void InitGraph(ALGraph *G){
    int i;
    printf("请输入顶点数和边数：\n");
    scanf("%d %d", &G->vexnum, &G->arcnum);
    for(i = 0; i < G->vexnum; ++i){
        printf("请输入第%d个顶点的值：", i+1);
        scanf("%d", &G->vertices[i].data);
        G->vertices[i].firstarc = NULL;
    }
    for(i = 0; i < G->arcnum; ++i){
        int v1, v2;
        printf("请输入第%d条边的两个端点：", i+1);
        scanf("%d %d", &v1, &v2);
        // 添加v1->v2这条边
        ArcNode *p = (ArcNode*)malloc(sizeof(ArcNode));
        p->adjvex = v2-1;
        p->next = G->vertices[v1-1].firstarc;
        G->vertices[v1-1].firstarc = p;
        // 添加v2->v1这条边
        p = (ArcNode*)malloc(sizeof(ArcNode));
        p->adjvex = v1-1;
        p->next = G->vertices[v2-1].firstarc;
        G->vertices[v2-1].firstarc = p;
    }
}

// 广度优先遍历
void BFS(ALGraph *G, int v){
    int visited[MAX_VERTEX_NUM] = {0}; // 标记数组，用于记录顶点是否被访问过
    int queue[MAX_VERTEX_NUM], front = 0, rear = 0; // 辅助队列
    printf("%d ", G->vertices[v].data);
    visited[v] = 1;
    queue[rear++] = v;
    while(front < rear){
        int w = queue[front++];
        ArcNode *p = G->vertices[w].firstarc;
        while(p != NULL){
            int u = p->adjvex;
            if(!visited[u]){
                printf("%d ", G->vertices[u].data);
                visited[u] = 1;
                queue[rear++] = u;
            }
            p = p->next;
        }
    }
}

int main(){
    ALGraph G;
    InitGraph(&G);
    printf("广度优先遍历：");
    BFS(&G, 0);
    return 0;
}

这里我们使用了一个辅助队列来实现广度优先遍历。从起始顶点开始，先将该顶点标记为已访问，然后将其加入队列中。接下来，从队首取出一个顶点，依次访问它的所有未被访问过的邻接点，并将这些邻接点标记为已访问并加入队列中。直到队列为空时，遍历结束。