bfs算法c语言数据结构

BFS（Breadth-First-Search，广度优先搜索）是一种常用的图遍历算法，其基本思想是从图的某一结点出发，依次访问其所有相邻的结点，再依次访问这些相邻结点的未被访问过的相邻结点，直到所有结点都被访问为止。

以下是BFS算法的C语言实现：

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

#define MAX_VERTICES 100 // 最大顶点数
#define MAX_QUEUE_SIZE 100 // 最大队列长度

typedef struct {
    int front, rear; // 队头和队尾指针
    int data[MAX_QUEUE_SIZE]; // 队列数组
} Queue;

// 初始化队列
void initQueue(Queue *q) {
    q->front = q->rear = 0;
}

// 判断队列是否为空
bool isQueueEmpty(Queue *q) {
    return q->front == q->rear;
}

// 入队
void enqueue(Queue *q, int value) {
    if ((q->rear + 1) % MAX_QUEUE_SIZE == q->front) {
        printf("队列已满，无法入队！\n");
        return;
    }
    q->data[q->rear] = value;
    q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
}

// 出队
int dequeue(Queue *q) {
    if (isQueueEmpty(q)) {
        printf("队列为空，无法出队！\n");
        return -1;
    }
    int value = q->data[q->front];
    q->front = (q->front + 1) % MAX_QUEUE_SIZE;
    return value;
}

// 遍历图
void bfs(int graph[][MAX_VERTICES], int start, int numVertices) {
    bool visited[MAX_VERTICES] = { false }; // 标记顶点是否被访问过
    Queue q;
    initQueue(&q);
    visited[start] = true;
    printf("%d ", start);
    enqueue(&q, start);
    while (!isQueueEmpty(&q)) {
        int vertex = dequeue(&q);
        for (int i = 0; i < numVertices; i++) {
            if (graph[vertex][i] && !visited[i]) { // 如果相邻顶点未被访问过
                visited[i] = true;
                printf("%d ", i);
                enqueue(&q, i);
            }
        }
    }
}

int main() {
    int graph[MAX_VERTICES][MAX_VERTICES] = { {0, 1, 1, 0, 0}, {1, 0, 0, 1, 1}, {1, 0, 0, 1, 0}, {0, 1, 1, 0, 1}, {0, 1, 0, 1, 0} };
    int numVertices = 5;
    int start = 0;
    bfs(graph, start, numVertices);
    return 0;
}

以上代码中，使用了一个循环数组实现队列，使用了一个visited数组记录顶点是否被访问过。函数bfs遍历整个图并输出遍历结果。