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]; // 模拟队列

void bfs() {
    int dx[4] = {-1, 0, 1, 0}; // 用向量-1，0，1，0来表示每次走的行方向
    int dy[4] = {0, 1, 0, -1}; // 用向量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 current = q[hh++];
        
        for (int i = 0; i < 4; i++) {
            int newX = current.x + dx[i];
            int newY = current.y + dy[i];
            
            if (newX >= 0 && newX < n && newY >= 0 && newY < m && g[newX][newY] == 0 && d[newX][newY] == -1) {
                d[newX][newY] = d[current.x][current.y] + 1;
                q[++tt].x = newX;
                q[tt].y = newY;
            }
        }
    }
}

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;
        }
    }
    
    bfs();
    
    printf('%d\n', d[n-1][m-1]);
    
    return 0;
}

代码说明：

• 代码首先定义了图的大小 n 和 m，以及一个二维数组 g 来存储图的信息。
• bfs() 函数实现了广度优先搜索算法，使用队列 q 来存储待访问的节点，并使用数组 d 来记录每个节点到起点的距离。
• main() 函数中，首先读取图的信息，然后调用 bfs() 函数计算最短路径，最后输出结果。

示例应用：

假设我们有一个 5x5 的地图，如下所示：

0 1 0 0 0
0 0 1 0 1
0 1 0 1 0
0 0 0 0 1
0 1 1 0 0

其中，0 表示可以通过的路径，1 表示不可通过的障碍物。

运行上述代码，程序会输出 8，表示从左上角到右下角的最短路径长度为 8。

希望这个示例代码能够帮助你理解和使用C语言实现BFS算法。