关键：队列（先进先出），一个顶点出队列，它的邻接点入队列。

队列的实现

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

// 定义队列节点结构
typedef struct QueueNode {
    void *data;
    struct QueueNode *next;
} QueueNode;

// 定义队列结构
typedef struct Queue {
    QueueNode *front;
    QueueNode *rear;
} Queue;

// 初始化队列
Queue* createQueue() {
    Queue *queue = (Queue *)malloc(sizeof(Queue));
    queue->front = NULL;
    queue->rear = NULL;
    return queue;
}

// 入队操作
void enqueue(Queue *queue, void *data) {
    QueueNode *newNode = (QueueNode *)malloc(sizeof(QueueNode));
    newNode->data = data;
    newNode->next = NULL;
    if (queue->rear == NULL) {
        queue->front = newNode;
        queue->rear = newNode;
    } else {
        queue->rear->next = newNode;
        queue->rear = newNode;
    }
}

// 出队操作
void* dequeue(Queue *queue) {
    if (queue->front == NULL) {
        return NULL;
    }
    QueueNode *temp = queue->front;
    void *data = temp->data;
    queue->front = queue->front->next;
    if (queue->front == NULL) {
        queue->rear = NULL;
    }
    free(temp);
    return data;
}

// 判断队列是否为空
int isQueueEmpty(Queue *queue) {
    return queue->front == NULL;
}

// 销毁队列，释放所有节点
void destroyQueue(Queue *queue) {
    while (!isQueueEmpty(queue)) {
        dequeue(queue);
    }
    free(queue);
}

// 测试队列结构
int main() {
    Queue *queue = createQueue();

    // 示例：将整数加入队列
    int a = 1, b = 2, c = 3;
    enqueue(queue, &a);
    enqueue(queue, &b);
    enqueue(queue, &c);

    // 出队并打印数据
    while (!isQueueEmpty(queue)) {
        int *data = (int *)dequeue(queue);
        printf("%d ", *data);
    }
    printf("\n");

    destroyQueue(queue);

    return 0;
}

二叉树的BFS

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

// 定义二叉树节点结构
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 定义队列节点结构
typedef struct QueueNode {
    TreeNode *node;
    struct QueueNode *next;
} QueueNode;

// 定义队列结构
typedef struct Queue {
    QueueNode *front;
    QueueNode *rear;
} Queue;

// 初始化队列
Queue* createQueue() {
    Queue *queue = (Queue *)malloc(sizeof(Queue));
    queue->front = NULL;
    queue->rear = NULL;
    return queue;
}

// 入队操作
void enqueue(Queue *queue, TreeNode *node) {
    QueueNode *newNode = (QueueNode *)malloc(sizeof(QueueNode));
    newNode->node = node;
    newNode->next = NULL;
    if (queue->rear == NULL) {
        queue->front = newNode;
        queue->rear = newNode;
    } else {
        queue->rear->next = newNode;
        queue->rear = newNode;
    }
}

// 出队操作
TreeNode* dequeue(Queue *queue) {
    if (queue->front == NULL) {
        return NULL;
    }
    QueueNode *temp = queue->front;
    TreeNode *node = temp->node;
    queue->front = queue->front->next;
    if (queue->front == NULL) {
        queue->rear = NULL;
    }
    free(temp);
    return node;
}

// 判断队列是否为空
int isQueueEmpty(Queue *queue) {
    return queue->front == NULL;
}

// 创建新的二叉树节点
TreeNode* createTreeNode(int val) {
    TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 广度优先搜索（BFS）遍历二叉树
void bfs(TreeNode *root) {
    if (root == NULL) {
        return;
    }
    Queue *queue = createQueue();
    enqueue(queue, root);
    while (!isQueueEmpty(queue)) {
        TreeNode *current = dequeue(queue);
        printf("%d ", current->val);
        if (current->left != NULL) {
            enqueue(queue, current->left);
        }
        if (current->right != NULL) {
            enqueue(queue, current->right);
        }
    }
    printf("\n");
}

int main() {
    // 创建一个简单的二叉树用于测试
    TreeNode *root = createTreeNode(1);
    root->left = createTreeNode(2);
    root->right = createTreeNode(3);
    root->left->left = createTreeNode(4);
    root->left->right = createTreeNode(5);
    root->right->left = createTreeNode(6);
    root->right->right = createTreeNode(7);

    // 执行BFS遍历
    printf("BFS traversal of the binary tree:\n");
    bfs(root);

    return 0;
}

以 邻接表 表示的图的BFS

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

#define MAX_VERTICES 100  // 假设最大顶点数

// 定义图的邻接表结构
typedef struct AdjListNode {
    int dest;
    struct AdjListNode* next;
} AdjListNode;

typedef struct AdjList {
    AdjListNode* head;
} AdjList;

typedef struct Graph {
    int numVertices;
    AdjList* array;
} Graph;

// 创建一个新的邻接表节点
AdjListNode* newAdjListNode(int dest) {
    AdjListNode* newNode = (AdjListNode*)malloc(sizeof(AdjListNode));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

// 创建一个图，包含V个顶点
Graph* createGraph(int V) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->numVertices = V;

    // 创建V个邻接表
    graph->array = (AdjList*)malloc(V * sizeof(AdjList));

    // 初始化每个邻接表的头节点
    for (int i = 0; i < V; ++i)
        graph->array[i].head = NULL;

    return graph;
}

// 添加边到无向图
void addEdge(Graph* graph, int src, int dest) {
    // 添加从src到dest的边
    AdjListNode* newNode = newAdjListNode(dest);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;

    // 因为是无向图，添加从dest到src的边
    newNode = newAdjListNode(src);
    newNode->next = graph->array[dest].head;
    graph->array[dest].head = newNode;
}

// 定义队列节点结构
typedef struct QueueNode {
    int data;
    struct QueueNode* next;
} QueueNode;

// 定义队列结构
typedef struct Queue {
    QueueNode *front, *rear;
} Queue;

// 创建一个新的队列节点
QueueNode* newQueueNode(int data) {
    QueueNode* temp = (QueueNode*)malloc(sizeof(QueueNode));
    temp->data = data;
    temp->next = NULL;
    return temp;
}

// 创建一个队列
Queue* createQueue() {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->front = queue->rear = NULL;
    return queue;
}

// 入队操作
void enqueue(Queue* queue, int data) {
    QueueNode* temp = newQueueNode(data);
    if (queue->rear == NULL) {
        queue->front = queue->rear = temp;
        return;
    }
    queue->rear->next = temp;
    queue->rear = temp;
}

// 出队操作
int dequeue(Queue* queue) {
    if (queue->front == NULL)
        return -1;
    QueueNode* temp = queue->front;
    int data = temp->data;
    queue->front = queue->front->next;
    if (queue->front == NULL)
        queue->rear = NULL;
    free(temp);
    return data;
}

// 判断队列是否为空
int isQueueEmpty(Queue* queue) {
    return queue->front == NULL;
}

// 广度优先搜索（BFS）算法
void bfs(Graph* graph, int startVertex) {
    int* visited = (int*)malloc(graph->numVertices * sizeof(int));
    for (int i = 0; i < graph->numVertices; i++)
        visited[i] = 0;

    Queue* queue = createQueue();
    visited[startVertex] = 1;
    enqueue(queue, startVertex);

    while (!isQueueEmpty(queue)) {
        int currentVertex = dequeue(queue);
        printf("%d ", currentVertex);

        AdjListNode* temp = graph->array[currentVertex].head;
        while (temp) {
            int adjVertex = temp->dest;
            if (!visited[adjVertex]) {
                visited[adjVertex] = 1;
                enqueue(queue, adjVertex);
            }
            temp = temp->next;
        }
    }
    printf("\n");

    free(visited);
}

// 主函数测试
int main() {
    int V = 5;
    Graph* graph = createGraph(V);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 4);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 4);

    printf("BFS traversal starting from vertex 0:\n");
    bfs(graph, 0);

    return 0;
}

以邻接矩阵表示的图的BFS

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

#define MAX_VERTICES 100  // 假设最大顶点数

// 定义队列节点结构
typedef struct QueueNode {
    int data;
    struct QueueNode* next;
} QueueNode;

// 定义队列结构
typedef struct Queue {
    QueueNode *front, *rear;
} Queue;

// 创建一个新的队列节点
QueueNode* newQueueNode(int data) {
    QueueNode* temp = (QueueNode*)malloc(sizeof(QueueNode));
    temp->data = data;
    temp->next = NULL;
    return temp;
}

// 创建一个队列
Queue* createQueue() {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->front = queue->rear = NULL;
    return queue;
}

// 入队操作
void enqueue(Queue* queue, int data) {
    QueueNode* temp = newQueueNode(data);
    if (queue->rear == NULL) {
        queue->front = queue->rear = temp;
        return;
    }
    queue->rear->next = temp;
    queue->rear = temp;
}

// 出队操作
int dequeue(Queue* queue) {
    if (queue->front == NULL)
        return -1;
    QueueNode* temp = queue->front;
    int data = temp->data;
    queue->front = queue->front->next;
    if (queue->front == NULL)
        queue->rear = NULL;
    free(temp);
    return data;
}

// 判断队列是否为空
int isQueueEmpty(Queue* queue) {
    return queue->front == NULL;
}

// 广度优先搜索（BFS）算法
void bfs(int graph[MAX_VERTICES][MAX_VERTICES], int numVertices, int startVertex) {
    int* visited = (int*)malloc(numVertices * sizeof(int));
    for (int i = 0; i < numVertices; i++)
        visited[i] = 0;

    Queue* queue = createQueue();
    visited[startVertex] = 1;
    enqueue(queue, startVertex);

    while (!isQueueEmpty(queue)) {
        int currentVertex = dequeue(queue);
        printf("%d ", currentVertex);

        for (int i = 0; i < numVertices; i++) {
            if (graph[currentVertex][i] && !visited[i]) {
                visited[i] = 1;
                enqueue(queue, i);
            }
        }
    }
    printf("\n");

    free(visited);
}

// 主函数测试
int main() {
    int numVertices = 5;
    int graph[MAX_VERTICES][MAX_VERTICES] = {
        {0, 1, 0, 0, 1},
        {1, 0, 1, 1, 1},
        {0, 1, 0, 1, 0},
        {0, 1, 1, 0, 1},
        {1, 1, 0, 1, 0}
    };

    printf("BFS traversal starting from vertex 0:\n");
    bfs(graph, numVertices, 0);

    return 0;
}