广度优先搜索遍历算法代码用c

以下是广度优先搜索遍历算法的C语言代码示例：

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

#define MAX_VERTEX_NUM 100 // 图中顶点的最大数量

typedef struct ArcNode {
    int adjvex;                // 相邻节点的下标
    struct ArcNode *nextarc;   // 指向下一个相邻节点的指针
} ArcNode;

typedef struct VNode {
    int data;                  // 顶点的数据信息
    ArcNode *firstarc;         // 指向该顶点的第一个相邻节点的指针
} VNode, AdjList[MAX_VERTEX_NUM];

typedef struct {
    AdjList vertices;          // 图的顶点集合
    int vexnum, arcnum;        // 顶点数和边数
} ALGraph;

// 队列结构体
typedef struct {
    int *data;                 // 存储队列元素的数组
    int front, rear;           // 队头和队尾下标
} Queue;

// 初始化队列
void initQueue(Queue *Q, int size) {
    Q->data = (int*)malloc(size * sizeof(int));
    Q->front = Q->rear = 0;
}

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

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

// 判断队列是否为空
int isEmpty(Queue *Q) {
    return Q->front == Q->rear;
}

// 创建图
void createGraph(ALGraph *G) {
    int i, j, k;
    ArcNode *p;

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

    printf("请输入%d个顶点的数据信息：\n", G->vexnum);
    for (i = 0; i < G->vexnum; i++) {
        printf("第%d个顶点：", i + 1);
        scanf("%d", &G->vertices[i].data);
        G->vertices[i].firstarc = NULL;
    }

    printf("请输入%d条边的顶点序号：\n", G->arcnum);
    for (k = 0; k < G->arcnum; k++) {
        printf("第%d条边：", k + 1);
        scanf("%d %d", &i, &j);

        // 添加边(i, j)
        p = (ArcNode*)malloc(sizeof(ArcNode));
        p->adjvex = j - 1;
        p->nextarc = G->vertices[i - 1].firstarc;
        G->vertices[i - 1].firstarc = p;

        // 添加边(j, i)
        p = (ArcNode*)malloc(sizeof(ArcNode));
        p->adjvex = i - 1;
        p->nextarc = G->vertices[j - 1].firstarc;
        G->vertices[j - 1].firstarc = p;
    }
}

// 广度优先搜索遍历算法
void BFS(ALGraph *G, int v, int visited[]) {
    int u, w;
    Queue Q;

    // 初始化visited数组和队列
    for (u = 0; u < G->vexnum; u++) {
        visited[u] = 0;
    }
    initQueue(&Q, G->vexnum);

    // 访问起始顶点v并将其入队
    visited[v] = 1;
    printf("%d ", G->vertices[v].data);
    enQueue(&Q, v);

    // 遍历队列中的元素
    while (!isEmpty(&Q)) {
        u = deQueue(&Q);

        // 遍历u的所有邻接点
        for (w = G->vertices[u].firstarc; w != NULL; w = w->nextarc) {
            if (!visited[w->adjvex]) {
                // 访问未被访问过的邻接点并将其入队
                visited[w->adjvex] = 1;
                printf("%d ", G->vertices[w->adjvex].data);
                enQueue(&Q, w->adjvex);
            }
        }
    }
}

int main() {
    ALGraph G;
    int visited[MAX_VERTEX_NUM];

    createGraph(&G);

    printf("广度优先搜索遍历结果：");
    BFS(&G, 0, visited);

    return 0;
}