BFS算法篇——穿越迷雾森林，探幽最短路径之谜（上）

文章目录

引言
一、问题背景
二、算法思想
三、代码实现
总结

引言

在算法的世界里，路径常常象征着人生的抉择。而在这片由图构成的森林中，我们寻找的，不是一条通向远方的漫长旅途，而是那条最短的、直指目标的光明之路。

在探索最短路径的问题中，BFS（Breadth-First Search，广度优先搜索）如同一位耐心而睿智的向导。他不会在分岔口踌躇犹豫，而是从起点出发，一层一层地向外扩展，直至找到那条最先触及终点的路径。

在这里插入图片描述

一、问题背景

设想你置身于一个二维迷宫中，四面高墙环绕。你可以向上下左右四个方向移动，而某些位置由于障碍而无法通行。你的目标是从起点出发，以最少的步数抵达终点。

这正是 BFS 的用武之地。

与 DFS（深度优先搜索）相比，BFS 保证最先到达终点的一定是路径最短的那一条。
为何如此？因为它是逐层推进的：首先探索距离为 1 的所有节点，再探索距离为 2 的所有节点，依此类推。

二、算法思想

BFS 使用队列（Queue）这一数据结构来实现。其基本流程如下：

将起点加入队列，并标记为已访问；
当队列不为空时，执行以下操作：

弹出队首元素；
遍历其所有邻接节点：
若未被访问，加入队列，并标记其距离为当前节点距离 + 1；
若该节点为终点，终止搜索，返回路径长度。

三、代码实现

以下是用 C 语言实现 BFS 算法来解决迷宫最短路径问题的代码：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>#define MAX 100// 队列结构体定义
typedef struct {int x, y, dist;
} Node;// 四个方向：上、下、左、右
int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};// 队列操作
typedef struct {Node nodes[MAX * MAX];int front, rear;
} Queue;// 队列初始化
void initQueue(Queue* q) {q->front = q->rear = 0;
}// 入队
void enqueue(Queue* q, Node node) {q->nodes[q->rear++] = node;
}// 出队
Node dequeue(Queue* q) {return q->nodes[q->front++];
}// 判断队列是否为空
bool isEmpty(Queue* q) {return q->front == q->rear;
}// BFS 求最短路径
int bfs(int maze[MAX][MAX], int startX, int startY, int endX, int endY, int n, int m) {Queue q;initQueue(&q);bool visited[MAX][MAX] = {false};visited[startX][startY] = true;enqueue(&q, (Node){startX, startY, 0}); // 初始节点入队，距离为 0while (!isEmpty(&q)) {Node current = dequeue(&q);// 到达终点if (current.x == endX && current.y == endY) {return current.dist;}// 处理四个方向的邻居for (int i = 0; i < 4; i++) {int newX = current.x + directions[i][0];int newY = current.y + directions[i][1];// 判断是否越界，是否可以走if (newX >= 0 && newX < n && newY >= 0 && newY < m && maze[newX][newY] == 0 && !visited[newX][newY]) {visited[newX][newY] = true;enqueue(&q, (Node){newX, newY, current.dist + 1});}}}return -1; // 无法到达终点
}int main() {// 迷宫示例：0 表示通路，1 表示墙int maze[MAX][MAX] = {{0, 1, 0, 0, 0},{0, 1, 0, 1, 0},{0, 0, 0, 1, 0},{1, 1, 0, 0, 0}};int n = 4, m = 5; // 迷宫的行列数int startX = 0, startY = 0; // 起点int endX = 3, endY = 4; // 终点int result = bfs(maze, startX, startY, endX, endY, n, m);if (result != -1) {printf("最短路径长度为: %d\n", result);} else {printf("无法到达终点\n");}return 0;
}