C语言广度优先搜索详解（从零开始掌握BFS算法与图遍历）

为什么学习BFS？

BFS在实际开发中有广泛应用，例如：

• 查找最短路径（在无权图中）
• 社交网络中的“六度空间”问题
• 迷宫求解
• 网页爬虫的层级抓取

掌握图的遍历算法是每个程序员的基本功，而BFS正是其中的核心之一。

BFS的核心思想

BFS的关键在于使用队列。以下是其基本步骤：

1. 将起始节点加入队列，并标记为已访问。
2. 当队列不为空时，取出队首节点。
3. 访问该节点的所有未访问邻居，并将它们加入队列，同时标记为已访问。
4. 重复步骤2-3，直到队列为空。

C语言实现BFS

下面我们用C语言实现一个简单的BFS程序。假设我们有一个用邻接矩阵表示的无向图。

1. 定义图结构和队列

#include <stdio.h>#include <stdlib.h>#define MAX_VERTICES 100// 邻接矩阵表示图int graph[MAX_VERTICES][MAX_VERTICES];int visited[MAX_VERTICES];// 简单队列结构int queue[MAX_VERTICES];int front = 0, rear = 0;void enqueue(int value) {    queue[rear++] = value;}int dequeue() {    return queue[front++];}int isQueueEmpty() {    return front == rear;}

2. BFS函数实现

void bfs(int start, int n) {    // 初始化visited数组    for (int i = 0; i < n; i++) {        visited[i] = 0;    }    // 起始节点入队并标记    enqueue(start);    visited[start] = 1;    printf("BFS遍历顺序: ");    while (!isQueueEmpty()) {        int current = dequeue();        printf("%d ", current);        // 遍历所有邻居        for (int i = 0; i < n; i++) {            if (graph[current][i] == 1 && !visited[i]) {                visited[i] = 1;                enqueue(i);            }        }    }    printf("\n");}

3. 主函数测试

int main() {    int n = 5; // 节点数    // 构建图：邻接矩阵    // 示例图：0-1-2    //         | / |    //         3---4    graph[0][1] = graph[1][0] = 1;    graph[1][2] = graph[2][1] = 1;    graph[0][3] = graph[3][0] = 1;    graph[1][3] = graph[3][1] = 1;    graph[2][3] = graph[3][2] = 1;    graph[2][4] = graph[4][2] = 1;    graph[3][4] = graph[4][3] = 1;    bfs(0, n); // 从节点0开始BFS    return 0;}

运行上述代码，输出将是：

BFS遍历顺序: 0 1 3 2 4

关键点总结

• 队列在BFS中的应用是核心机制，确保按层级访问。
• 必须使用visited数组防止重复访问，避免死循环。
• BFS天然适用于寻找最短路径（在无权图中）。
• 时间复杂度为 O(V + E)，其中 V 是顶点数，E 是边数。

结语

通过本教程，你已经掌握了C语言广度优先搜索的基本原理与实现方法。无论是面试准备还是实际项目开发，BFS都是一项不可或缺的技能。建议你动手编写并调试上面的代码，加深理解。

记住，算法学习的关键在于实践。尝试修改图结构、添加路径记录功能，甚至将其应用于迷宫问题，你会收获更多！

希望这篇关于BFS算法实现和图的遍历算法的教程对你有所帮助。祝你编程愉快！