图的广度优先遍历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, arcnum; // 顶点数和边数
} ALGraph;

// 初始化邻接表
void InitALGraph(ALGraph *G) {
    int i;
    G->vexnum = G->arcnum = 0;
    for (i = 0; i < MAX_VERTEX_NUM; i++) {
        G->vertices[i].data = 0;
        G->vertices[i].firstarc = NULL;
    }
}

// 插入边
void InsertArc(ALGraph *G, int v, int w) {
    ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));
    p->adjvex = w;
    p->next = G->vertices[v].firstarc;
    G->vertices[v].firstarc = p;
}

// 广度优先遍历
void BFS(ALGraph *G, int v, int *visited) {
    int queue[MAX_VERTEX_NUM], front = 0, rear = 0;
    ArcNode *p;
    printf("%d ", G->vertices[v].data);
    visited[v] = 1;
    queue[rear++] = v;
    while (front != rear) {
        v = queue[front++];
        p = G->vertices[v].firstarc;
        while (p) {
            if (!visited[p->adjvex]) {
                printf("%d ", G->vertices[p->adjvex].data);
                visited[p->adjvex] = 1;
                queue[rear++] = p->adjvex;
            }
            p = p->next;
        }
    }
}

int main() {
    ALGraph G;
    int visited[MAX_VERTEX_NUM] = {0}; // 标记顶点是否被访问过
    int i, j, v;
    printf("请输入顶点数和边数：");
    scanf("%d%d", &G.vexnum, &G.arcnum);
    printf("请输入顶点的数据：");
    for (i = 0; i < G.vexnum; i++) {
        scanf("%d", &G.vertices[i].data);
    }
    printf("请输入每条边的起点和终点：");
    for (i = 0; i < G.arcnum; i++) {
        scanf("%d%d", &j, &v);
        InsertArc(&G, j, v);
        InsertArc(&G, v, j); // 无向图需要插入反向边
    }
    printf("广度优先遍历结果为：");
    for (i = 0; i < G.vexnum; i++) {
        if (!visited[i]) {
            BFS(&G, i, visited);
        }
    }
    printf("\n");
    return 0;
}

在该示例中，我们使用邻接表来表示图。首先，我们需要定义边结构体 `ArcNode` 和顶点结构体 `VNode`，然后通过邻接表数组 `AdjList` 来定义图。在 `InitALGraph` 函数中，我们初始化邻接表。在 `InsertArc` 函数中，我们插入边。在 `BFS` 函数中，我们实现广度优先遍历，并通过 `visited` 数组来标记顶点是否被访问过。在 `main` 函数中，我们输入顶点数、边数以及每个顶点的数据，并通过 `InsertArc` 函数插入边，最后调用 `BFS` 函数进行广度优先遍历。