图的世界就像是一个错综复杂的迷宫，而广度优先遍历（BFS）就像是我们手中的一盏灯，带领我们一步一步去探索这个迷宫的每一个角落。通过 C 语言实现一个简单的图遍历算法——广度优先遍历。
一、图与邻接矩阵——图的“连接地图”
在谈论广度优先遍历之前，我们先得了解图的表示方法。图是由节点（顶点）和连接这些节点的边组成的。想象一下，图就像是一个城市地图，节点是城市中的各个地点，而边就是城市中各个地点之间的道路。
为了让计算机理解这种“连接关系”，我们可以用邻接矩阵来表示图。邻接矩阵就是一个二维数组，它记录了图中每两个节点之间是否有边相连。
如果两个节点 iii 和 jjj 之间有边，邻接矩阵中的值就是 1；
如果没有边，值就是 0。
就像在城市地图上，你能清楚地看到哪些地点通过道路连接，哪些地点没有直接的通道。
二、广度优先遍历——一步步的探索
广度优先遍历（BFS）是一种非常直观的遍历方式。它就像是你从某个地方开始，先探访附近的地方，然后逐步扩展，最后覆盖整个区域。具体来说，广度优先遍历的步骤如下：
从一个起始节点出发，首先访问它。
将它的所有未访问过的邻接节点加入队列。
依次从队列中取出节点，访问它，并将它的未访问邻接节点加入队列。
重复这个过程，直到队列为空。
这个算法特别适合在我们需要“层层扩展”的时候使用，能够确保我们按层次访问每一个节点。
三、用 C 语言实现广度优先遍历
让我们通过 C 语言的代码来实现这个算法。为了让图更加清晰，我们将用邻接矩阵来表示图，并用队列来帮助我们实现广度优先遍历。
1. 定义图的结构
首先，我们需要定义一个图的结构体。图中有一个邻接矩阵，记录了每两个节点之间的连接关系。
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 50 // 最大顶点数
// 图的结构体
typedef struct {
int adj[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵
int numVertices; // 顶点数
} Graph;
2. 初始化图
然后，我们需要一个函数来初始化图，设置邻接矩阵的所有元素为 0，表示最开始没有任何连接。
// 初始化图
void initGraph(Graph* g, int vertices) {
g->numVertices = vertices;
// 初始化邻接矩阵，全部设置为0
for (int i = 0; i < vertices; i++) {
for (int j = 0; j < vertices; j++) {
g->adj[i][j] = 0;
}
}
}
3. 添加边
接下来，编写一个函数来添加边。这个函数会将两点之间的连接标记为 1，表示这两点之间有一条边。
// 添加边
void addEdge(Graph* g, int start, int end) {
g->adj[start][end] = 1;
g->adj[end][start] = 1; // 无向图
}
4. 广度优先遍历——探访每一个节点
广度优先遍历的核心是使用队列。我们会将起始节点加入队列，然后不断从队列中取出节点，访问它，并将它的邻接节点加入队列。这个过程就像是一步步向外扩展，直到整个图都被访问一遍。
// 队列结构
typedef struct {
int items[MAX_VERTICES];
int front;
int rear;
} Queue;
// 初始化队列
void initQueue(Queue* q) {
q->front = -1;
q->rear = -1;
}
// 判断队列是否为空
int isEmpty(Queue* q) {
return q->front == -1;
}
// 入队
void enqueue(Queue* q, int value) {
if (q->rear == MAX_VERTICES - 1) {
printf("队列已满\n");
return;
}
if (q->front == -1) {
q->front = 0;
}
q->rear++;
q->items[q->rear] = value;
}
// 出队
int dequeue(Queue* q) {
if (isEmpty(q)) {
printf("队列为空\n");
return -1;
}
int item = q->items[q->front];
q->front++;
if (q->front > q->rear) {
q->front = q->rear = -1;
}
return item;
}
// 广度优先遍历
void bfs(Graph* g, int start) {
int visited[MAX_VERTICES] = {0}; // 记录访问情况
Queue q;
initQueue(&q);
// 从起始节点开始
visited[start] = 1;
printf("从节点 %d 开始广度优先遍历: ", start);
printf("%d ", start);
enqueue(&q, start);
while (!isEmpty(&q)) {
int current = dequeue(&q);
// 遍历当前节点的所有邻接节点
for (int i = 0; i < g->numVertices; i++) {
if (g->adj[current][i] == 1 && !visited[i]) {
printf("%d ", i);
visited[i] = 1;
enqueue(&q, i);
}
}
}
printf("\n");
}
5. 主函数——测试我们的广度优先遍历
最后，编写主函数，初始化一个图，添加一些边，然后从某个节点开始执行广度优先遍历。
int main() {
Graph g;
int vertices = 6; // 假设图有6个顶点
initGraph(&g, vertices);
// 添加一些边
addEdge(&g, 0, 1);
addEdge(&g, 0, 2);
addEdge(&g, 1, 3);
addEdge(&g, 1, 4);
addEdge(&g, 3, 5);
// 从节点0开始广度优先遍历
bfs(&g, 0);
return 0;
}
四、运行结果
假设我们创建的图如下所示：
0 - 1 - 3 - 5
| |
2 4
从节点 0 开始进行广度优先遍历，输出的结果应该是：
从节点 0 开始广度优先遍历: 0 1 2 3 4 5
五、总结
通过 C 语言实现了一个简单的广度优先遍历算法。广度优先遍历让我们能够从一个起始节点开始，逐层向外扩展，遍历整个图。通过邻接矩阵存储图的结构，我们可以快速检查图中任意两个节点之间是否有边相连。
这个算法虽然看起来简单，但它在很多实际应用中非常有用，比如找最短路径、网络流量分析等。