如何用队列实现广度优先算法-C语言解决迷宫问题

广度优先搜索算法（也称宽度优先搜索，缩写BFS）是图里面常用的一种遍历算法。这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和广度优先搜索类似的思想。广度优先算法属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。基本过程，BFS是从根节点开始，沿着树（图）的宽度遍历树（图）的节点。如果所有节点均被访问，则算法中止。一般用数据结构队列来辅助实现BFS算法。

下面给出了一个例子，给大家详细的解析下广度优先是怎么搜索的。给出如图的图形结构（初始化全是白色），寻找v1到v7的最短路径：

1、访问起点v1（灰色），并且把起点v1的位置信息做进队操作。

2、已经访问了v1（黑色），下面可能的路径有三个，v2、v3、v4（灰色），把三个节点的位置信息同样的做进队操作。此时队列里面的路径已经有三个：v1->v2、v1->v3、v1->v4。

3、对于v2而言，下面可能的路径有两个，v6和v3，但是v3已经访问过了，所以暂时忽略它。于是v6的位置信息进队。同样的，对v5和v7也做进队操作。此时队列里面有三条路径：v1->v2->v6、v1->v3->v5、v1->v4->v7。

4、此时已经访问了v7，于是搜索可以结束。队列里面存放了三条路径只有一条路径包含了v7，而且我们可以肯定的是，该路径也是最短的路径。

看完这个例子，不知道大家有没有感触，总结一下，广度优先算法就是齐头并进，按照所有可能一起搜索下去。而且深度优先算法则跟它完全相反，认准一条路一直走下去，行不通再回来。

下面我们再次借用走迷宫的问题，只不过我们这次配合队列，使用广度优先搜索算法找到一条最佳路径。还是先看下问题：

问题描述：

以一个m*n的矩阵（二维数组）表示迷宫，0和1分别表示迷宫中的通路和障碍。迷宫问题要求求出从入口（0，0）到出口（m，n）的一条通路，或得出没有通路的结论。基本要求：首先实现一个以顺序表作存储结构的队列模型，然后编写一个求迷宫问题的非递归程序，求得最佳通路。其中：（x，y）指示迷宫中的一个坐标，pre表示该节点从哪个节点走过来。左上角（0，0）为入口，右下角（m，n）为出口。

#include <stdio.h>

#define SIZE      1024

struct Box     //表示一个格子的位置信息
{
    int x;     //横坐标
    int y;     //纵坐标
    int pre;   //前一个格子再在队列里面存放的位置（下标）
};
typedef struct Box Box;

//顺序队列存放路径的信息
struct Queue
{
    Box data[SIZE];
    int front;
    int rear;
};
typedef struct Queue Queue;

#include <stdio.h>

#define SIZE      1024

struct Box     //表示一个格子的位置信息
{
    int x;     //横坐标
    int y;     //纵坐标
    int pre;   //前一个格子再在队列里面存放的位置（下标）
};
typedef struct Box Box;

//顺序队列存放路径的信息
struct Queue
{
    Box data[SIZE];
    int front;
    int rear;
};
typedef struct Queue Queue;

int map[6][6] = { 
    {0, 0, 0, 1, 1, 1}, 
    {1, 1, 0, 0, 0, 0}, 
    {1, 1, 0, 1, 1, 0}, 
    {1, 1, 0, 0, 0, 0}, 
    {1, 1, 1, 0, 1, 1}, 
    {1, 1, 1, 0, 0, 1}, 
};

//初始化顺序队列
int InitQueue(Queue *q) 
{
    q->front = q->rear = -1;
    return 1;
}

//进队操作
int push(Queue *q, Box b)
{
    if (q->rear == SIZE - 1)
    {
        return 0;
    }
    (q->rear)++;
    q->data[q->rear] = b;

    return 1;
}

//判断队列是否为空
int EmptyQueue(Queue *q)
{
    return (q->front == q->rear) ? 1 : 0;
}

//出队操作（只是操作对头指针，元素实际还保留在队列中）
int pop(Queue *q, Box *b)
{
    if (q->front == q->rear)
    {
        return 0;
    }
    (q->front)++;
    *b = q->data[q->front];

    return 1;
}

//打印路径
void ShowPath(Queue *q, int front)
{
    int p = front, tmp;
    while (p != 0)
    {
        tmp = q->data[p].pre;
        q->data[p].pre = -1;
        p = tmp;
    }

    int i;
    for (i = 0; i <= q->rear; i++)
    {
        if (q->data[i].pre == -1)
        {
            printf("(%d, %d)->", q->data[i].x, q->data[i].y);
        }
    }
    printf("\n");
}

//入口（0，0） 出口（5，4）
int Walk(Queue *q, int x1, int y1, int x2, int y2)
{
    Box now;
    int i, j, i0, j0;

    now.x = x1;
    now.y = y1;
    now.pre = -1;

    push(q, now);            //入口信息入队
    map[x1][y1] = -1;

    while (EmptyQueue(q) != 1)
    {
        pop(q, &now);

        i = now.x;
        j = now.y;

        if (i == x2 && j == y2)       //出口
        {
            ShowPath(q, q->front);
            return 1;
        }

        int dir;
        for (dir = 0; dir < 4; dir++)   //循环四次，遍历四个方向  上  右  下  左
        {
            switch(dir)
            {
                case 0:            //方向上
                    i0 = i - 1;
                    j0 = j;
                    break;
                case 1:            //方向又
                    i0 = i;
                    j0 = j + 1;
                    break;
                case 2:           //方向下
                i0 = i + 1;
                    j0 = j;
                    break;
                case 3:           //方向左
                    i0 = i;
                    j0 = j - 1;
                    break;
            }
            //判断该点是否可走
            if (i0 >= 0 && j0 >= 0 && i0 <= 5 && j0 <= 5 && map[i0][j0] == 0)   //格子可以走
            {
                now.x = i0;
                now.y = j0;
                now.pre = q->front;

                push(q, now);
                map[i0][j0] = -1;     //该点已经走过
            }
        }
    }

    return 0;
}

int main()
{
    Queue queue;
    InitQueue(&queue);

    if (Walk(&queue, 0, 0, 5, 4) == 0)
    {
        printf("路径不存在\n");
    }

    return 0;
}

更多精彩视频、文章、嵌入式学习资料，微信关注 『学益得智能硬件』！