用c语言写一个图的遍历，广度优先

以下是使用C语言实现图的广度优先遍历的示例代码：

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

#define MAX_VERTEX_NUM 100  // 最大顶点数

typedef struct ArcNode {  // 弧节点
    int adjvex;  // 邻接点下标
    struct ArcNode *next;  // 下一个邻接点指针
} ArcNode;

typedef struct VertexNode {  // 顶点节点
    int data;  // 顶点数据
    ArcNode *firstarc;  // 第一个邻接点指针
} VertexNode, AdjList[MAX_VERTEX_NUM];

typedef struct {  // 图
    AdjList vertices;  // 顶点数组
    int vexnum, arcnum;  // 顶点数、弧数
} Graph;

int visited[MAX_VERTEX_NUM]; // 访问标志数组

// 初始化图
void InitGraph(Graph *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;
        visited[i] = 0;
    }
}

// 添加顶点
void AddVertex(Graph *G, int v) {
    G->vertices[G->vexnum++].data = v;
}

// 添加弧
void AddArc(Graph *G, int v1, int v2) {
    ArcNode *arc = (ArcNode *)malloc(sizeof(ArcNode));
    arc->adjvex = v2;
    arc->next = G->vertices[v1].firstarc;
    G->vertices[v1].firstarc = arc;
    G->arcnum++;
}

// 广度优先遍历
void BFS(Graph *G, int v) {
    int i, u;
    ArcNode *arc;
    int queue[MAX_VERTEX_NUM], front = 0, rear = 0; // 队列
    visited[v] = 1;
    printf("%d ", G->vertices[v].data);
    queue[rear++] = v; // 入队
    while (front < rear) {
        u = queue[front++]; // 出队
        arc = G->vertices[u].firstarc;
        while (arc != NULL) {
            i = arc->adjvex;
            if (!visited[i]) {
                visited[i] = 1;
                printf("%d ", G->vertices[i].data);
                queue[rear++] = i; // 入队
            }
            arc = arc->next;
        }
    }
}

int main() {
    Graph G;
    int i, v, v1, v2;
    printf("请输入顶点数：");
    scanf("%d", &v);
    printf("请输入顶点数据：");
    for (i = 0; i < v; i++) {
        scanf("%d", &v1);
        AddVertex(&G, v1);
    }
    printf("请输入弧数：");
    scanf("%d", &v);
    printf("请输入弧的起点和终点：");
    for (i = 0; i < v; i++) {
        scanf("%d%d", &v1, &v2);
        AddArc(&G, v1, v2);
    }
    printf("广度优先遍历结果：");
    BFS(&G, 0);
    return 0;
}

在示例代码中，我们定义了一个 `Graph` 结构体表示图，其中 `AdjList` 数组用于存储顶点，每个顶点包含了一个 `ArcNode` 链表表示其邻接点。

我们使用 `InitGraph` 函数初始化图，使用 `AddVertex` 和 `AddArc` 函数添加顶点和弧。其中 `AddArc` 函数会在起点的邻接点链表中添加一个新的弧节点。

在广度优先遍历中，我们使用一个队列来存储待访问的顶点。从起点开始，首先将其标记为已访问，并输出其数据，然后将其入队。接着，从队列中取出一个顶点，遍历其邻接点，对于每个未访问的邻接点，将其标记为已访问，输出其数据，然后将其入队。重复上述步骤直到队列为空。在示例代码中，我们使用 `visited` 数组来记录每个顶点的访问状态。