广度优先遍历c语言

广度优先遍历（BFS）是一种图形搜索算法，可以用于遍历或搜索树或图的数据结构。下面是一个简单的C语言实现。

首先，我们需要定义一个队列数据结构。队列是BFS算法中用来存储待访问节点的数据结构。

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

struct queue {
    int front, rear;
    int capacity;
    int* data;
};

接下来，我们需要实现队列的操作函数。

// 创建一个队列并返回指向该队列的指针
struct queue* create_queue(int capacity) {
    struct queue* q = (struct queue*)malloc(sizeof(struct queue));
    q->capacity = capacity;
    q->front = -1;
    q->rear = -1;
    q->data = (int*)malloc(sizeof(int) * capacity);
    return q;
}

// 检查队列是否为空
int is_empty(struct queue* q) {
    return q->front == -1;
}

// 检查队列是否已满
int is_full(struct queue* q) {
    return (q->rear + 1) % q->capacity == q->front;
}

// 入队
void enqueue(struct queue* q, int value) {
    if (is_full(q)) {
        printf("Queue is full.\n");
        return;
    }
    if (is_empty(q)) {
        q->front = q->rear = 0;
    } else {
        q->rear = (q->rear + 1) % q->capacity;
    }
    q->data[q->rear] = value;
}

// 出队
int dequeue(struct queue* q) {
    if (is_empty(q)) {
        printf("Queue is empty.\n");
        return -1;
    }
    int value = q->data[q->front];
    if (q->front == q->rear) {
        q->front = q->rear = -1;
    } else {
        q->front = (q->front + 1) % q->capacity;
    }
    return value;
}

现在，我们可以使用队列来实现BFS算法了。

#define MAX_VERTICES 100

struct graph {
    int n; // 节点数
    int adj[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵
};

// 初始化图
void init_graph(struct graph* g) {
    g->n = 0;
    for (int i = 0; i < MAX_VERTICES; i++) {
        for (int j = 0; j < MAX_VERTICES; j++) {
            g->adj[i][j] = 0;
        }
    }
}

// 添加一条边
void add_edge(struct graph* g, int u, int v) {
    g->adj[u][v] = 1;
    g->adj[v][u] = 1;
}

// 广度优先遍历
void bfs(struct graph* g, int start) {
    int visited[MAX_VERTICES] = {0}; // 记录节点是否已访问
    struct queue* q = create_queue(g->n);
    enqueue(q, start);
    visited[start] = 1;
    while (!is_empty(q)) {
        int current = dequeue(q);
        printf("%d ", current);
        for (int i = 0; i < g->n; i++) {
            if (g->adj[current][i] && !visited[i]) {
                visited[i] = 1;
                enqueue(q, i);
            }
        }
    }
    printf("\n");
}

现在，我们可以测试一下BFS算法是否正确。

int main() {
    struct graph g;
    init_graph(&g);
    g.n = 6;
    add_edge(&g, 0, 1);
    add_edge(&g, 0, 2);
    add_edge(&g, 1, 3);
    add_edge(&g, 1, 4);
    add_edge(&g, 2, 4);
    add_edge(&g, 3, 4);
    add_edge(&g, 3, 5);
    add_edge(&g, 4, 5);
    bfs(&g, 0);
    return 0;
}

输出结果为：0 1 2 3 4 5，说明BFS算法是正确的。