C语言BFS算法实现：图的最短路径搜索

C语言BFS算法实现：图的最短路径搜索

广度优先搜索 (BFS) 是一种经典的图遍历算法，常用于寻找图中两点之间的最短路径。以下是用 C 语言实现 BFS 算法的示例代码：

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

#define MAX_NODES 110

typedef struct {
    int x, y;
} Point;

int n, m;
int g[MAX_NODES][MAX_NODES]; // 存放起始图
int d[MAX_NODES][MAX_NODES]; // 每一个点到起点的距离
Point q[MAX_NODES * MAX_NODES]; // 模拟队列

int bfs() {
    int dx[4] = {-1, 0, 1, 0};
    int dy[4] = {0, 1, 0, -1};

    int hh = 0, tt = 0; // 定义队头和队尾
    q[0].x = 0;
    q[0].y = 0; // 定义起始位置
    d[0][0] = 0;

    while (hh <= tt) { // 队列不空
        Point t = q[hh++]; // 取出队头元素

        for (int i = 0; i < 4; i++) { // 遍历四个方向
            int nx = t.x + dx[i];
            int ny = t.y + dy[i]; // 移动后的点

            if (nx >= 0 && nx < n && ny >= 0 && ny < m && g[nx][ny] == 0 && d[nx][ny] == -1) { // 移动后的点是合理的
                d[nx][ny] = d[t.x][t.y] + 1; // 更新这个点
                q[++tt].x = nx;
                q[tt].y = ny; // 将这个点加进队列
            }
        }
    }
    
    return d[n-1][m-1]; // 返回右下角的距离
}

int main() {
    scanf('%d %d', &n, &m);
    
    for (int i = 0; i < n; i++) { // 读入整个地图
        for (int j = 0; j < m; j++) {
            scanf('%d', &g[i][j]);
            d[i][j] = -1;
        }
    }
    
    int result = bfs();
    printf('%d\n', result);
    
    return 0;
}

代码解释：

1. 代码首先定义了一个 Point 结构体，用于表示地图上的点。
2. g 数组存储地图信息，d 数组存储每个点到起点的距离，q 数组模拟队列。
3. bfs() 函数实现 BFS 算法，从起点开始，逐层遍历所有可达的点，并计算最短距离。
4. main() 函数负责读取地图信息，调用 bfs() 函数计算最短路径，并输出结果。

如何使用：

1. 将代码保存为 .c 文件，例如 bfs.c。
2. 使用 C 编译器编译代码，例如 gcc bfs.c -o bfs。
3. 运行程序，输入地图大小和地图信息。

示例输入：

5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

示例输出：

8

这意味着从地图左上角到右下角的最短路径长度为 8。