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

用户11379153

发布于 2025-11-05 16:27:56

560

文章被收录于专栏：C++语法及相关算法详解C++语法及相关算法详解

引言

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

在探索最短路径的问题中，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}); // 初始节点入队，距离为 0

    while (!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;
}

代码解释