基于BFS实现迷宫求解

前言

在学习算法的过程中，广度优先搜索（BFS）是一个非常经典且实用的算法。今天我想分享一个使用C语言实现迷宫最短路径的例子，并附上完整代码。最好用循环队列，防止假溢出，这里先使用普通数组队列。

问题描述

假设我们有一个 n x n 的迷宫矩阵，矩阵中的 1 表示可走的路径，0 表示障碍。我们希望从起点 (0,0) 出发，找到终点 (n-1,n-1) 的最短路径，并打印出来。

示例迷宫：

BFS算法思路

BFS 的核心思想是一层一层地扩展搜索，这样可以保证第一次到达终点时路径长度最短。实现步骤如下：

使用队列存储待访问的节点。
用visited数组标记访问过的节点。
使用parent数组记录每个节点的前驱节点。
当到达终点时，通过回溯parent数组打印完整路径。

代码结构拆解

我们的代码可以拆解成以下几个模块：

全局变量和结构体定义
BFS函数实现
路径回溯
主函数初始化与调用

全局变量和结构体定义

#define MAX_VERTICES 100

int visited[MAX_VERTICES];   // 标记节点是否已访问
int queue[MAX_VERTICES];     // BFS队列
int parent[MAX_VERTICES];    // 记录每个节点的前驱节点

typedef struct {
    int x, y;
} Point; // 坐标结构体

visited防止重复访问节点，保证BFS正确性。
queue保存带访问节点、保证BFS的层次顺序。
parent用于回溯路径。
Point结构体让代码更清晰。

BFS函数实现

BFS核心代码如下

void BFS(int maze[][MAX_VERTICES],int n,Point start,Point end){

    int front =0;   //
    int rear =0;

    queue[rear++]=start.x*n+start.y;
    visited[start.x*n+start.y]=1;
    parent[start.x*n+start.y]=-1;

    while(front<rear){
        int current=queue[front++];

        if(current/n == end.x && current%n == end.y){
            printf("Successfully find the road!\n");

节点编码为 index = x * n + y，方便存储在一维数组。

回溯路径

int path[MAX_VERTICES];
            int step=0;

            int temp = current;
            while (temp != -1) {
                path[step++] = temp;
                temp = parent[temp];
            }

            printf("The road is:\n");
            for(int i=step-1;i>=0;i--){
                int px=path[i]/n;
                int py=path[i]%n;
                printf("(%d,%d)",px,py);
                if(i>0)printf("->");
            }
            printf("\n");
            return;
        }

从终点开始，沿parent数组回溯到起点。
存储到path数组。
逆序打印

扩展邻居节点

int moves[4][2]={
            {-1,0},
            {1,0},
            {0,-1},
            {0,1}};
        for(int i=0;i<4;i++){
            int newX=current/n+moves[i][0];
            int newY=current%n+moves[i][1];
            if(newX>=0&&newY>=0&&newX<n&&newY<n&&!visited[newX*n+newY]&&maze[newX][newY]==0){
                if(rear >= MAX_VERTICES){
                    printf("Queue Overflow!\n");
                    return;
                }
                queue[rear++]=newX*n+newY;
                visited[newX*n+newY]=1;
                parent[newX*n+newY] = current;
            }
        }

主函数

int main(){
    int n=6;
    int maze[MAX_VERTICES][MAX_VERTICES]={
    {0, 1, 0, 0, 0, 0},
    {0, 1, 0, 1, 1, 0},
    {0, 0, 0, 1, 0, 0},
    {1, 1, 0, 1, 0, 1},
    {0, 0, 0, 0, 0, 0},
    {0, 1, 1, 1, 1, 0},
    };
for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
        visited[i*n+j]=0;
        parent[i*n+j] = -1;
    }
}

BFS(maze,n,(Point){0,0},(Point){5,5});

return 0;
}

运行结果

Successfully find the road!
The road is:
(0,0)->(1,0)->(2,0)->(2,1)->(2,2)->(3,2)->(4,2)->(4,3)->(4,4)->(4,5)->(5,5)
Running time:1.000 ms

总结

BFS 是按层搜索，保证第一次到达终点就是最短路径
queue 保证访问顺序，visited 防止重复访问。
parent 用于路径回溯，是打印路径的关键。
节点编码 (x*n+y) 方便存储和回溯。
可以扩展八方向、障碍更多、迷宫更大，或者改成权重图使用 Dijkstra。

之后可能更新更多的东西（挖坑中）敬请期待……