广度优先搜索BFS

基本简介

对于每一个点，找到这个点能够直接连通的点，只做广度上的搜索而不做深度的搜索，在这个点的所有广度都搜索完成后，再扩展、深入到下一个深度进行广度搜索，最终完成所有搜索。
##实现思路
在一个带有障碍物的迷宫(二维数组)中模拟使用广度优先搜索来走迷宫。使用一个结构体数组来模拟一个队列，该队列记录每一个点的广度，在某一个层次的所有点的广度都搜索完成后，进入下一层次，这个过程由队列的出队、入队操作来实现。
首先，将起点放入队列作为队头，以队头为基准探索所有可能的走法，将所有符合条件的走法(不是障碍物且没有走过的点)入队，再让这些点成为新的队头(进入下一层次)，进行广度搜索，使用队列的满/空来实现循环控制，不涉及递归调用广度搜索函数。
##实现效果
这里写图片描述
##C代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
/*
project:BFS
author:zhy
IDE:VSCode
Comlile:windows gcc -v 4.8.1
*/

#include<stdio.h>
#include<stdlib.h>

#define _MAX_X 5                        //迷宫的大小
#define _MAX_Y 4

int arr[_MAX_X][_MAX_Y]={0};            //迷宫二维数组
int endx=3,endy=2;                      //目的地
int startx=0,starty=0;                  //起点
int stop[][2]={{0,2},{2,2},{3,1},{4,3}};            //障碍物
int next_step[][2]={{0,1},{1,0},{0,-1},{-1,0}};     //上下左右四个方向(坐标变化)

struct point{       //迷宫的每一个点
    int x;
    int y;
    int step;       //当前的步数：每一次扩展都加1
    int pre;        //上一个点，该属性用于的得到走迷宫的路径
};
int head,tail;      //队列的队头和队尾

//使用数组来模拟队列，该队列存储广度搜素时经过的每一个点
struct point queue[_MAX_X * _MAX_Y]={0};   

/*绘制迷宫到终端*/
int draw()
{
    int i,j;

    //打印迷宫图
    putchar('\n');
    for(i=0;i<_MAX_X;++i){
        for(j=0;j<_MAX_Y;++j)
        {
            switch(arr[i][j]){
                case 0:
                    printf("_");//可以走的地方
                    break;
                case -1:
                    printf("X");//障碍物
                    break;
                case -2:
                    printf("O");//终点
                    break;
                case -3:
                    printf("S");//起点
                    break;
                default:
                    printf("%d",arr[i][j]);
                    break;
            }
            printf("|");
        }
        printf("\n");
    }
    putchar('\n');
}

//BFS
void bfs()
{
    int i=0;
    int nextx=0,nexty=0;     //下一个点的坐标
    
    //标记是否找到目标(除了标记找到目标以外，它还用于跳出while和for两重嵌套的循环)
    int flag = 0;            
    
    //队列的头尾
    head = 0;
    tail = 0;

    //将起点入队
    queue[tail].x = startx;
    queue[tail].y = starty;
    queue[tail].pre = 0;
    queue[tail].step = 1;
    ++tail;                 //移到下一个空白位置

    while(head < tail)      //队列中还存在点没有完成广度搜索
    {
        for(i=0;i < sizeof(arr)/sizeof(int)/2;++i)
        {
            nextx = queue[head].x + next_step[i][0];
            nexty = queue[head].y + next_step[i][1];

            //判断这些点是不是在迷宫内
            if(nextx < 0 || nexty < 0 || nextx >= _MAX_X || nexty >= _MAX_Y){
                continue;
            }

            //判断这些点是否可以走(不是障碍且没有走过)
            if(arr[nextx][nexty] == 0){
                /*将这个点标记为已经走过了，然后令这个点入队;准备在当前所有方向尝试完成后(即for循环结束)进行扩展(去下一层次的点,进入下一次while)*/
                arr[nextx][nexty] = queue[head].step;       //标记
                queue[tail].x = nextx;
                queue[tail].y = nexty;
                queue[tail].step = queue[head].step+1;
                queue[tail].pre = head;
                ++tail;             //移动tail

                //以下两行用于搜索过程可视化，没有实际算法意义
                draw();
                system("pause");
            }

            if(nextx == endx && nexty == endy){
                flag = 1;
                break;
            }
        }/*End for()*/

        if(flag != 0)
            break;
        else
            ++head;         
            //执行else，表明该点的所有方向已完成搜索，因此++head进入下一深度的搜索
    }/*End while()*/
}

int main(int argc,char **argv)
{
    int i=0,j=0;

    //为障碍物、起点终点等对应的数组元素赋值
    for(i=0;i < sizeof(stop)/sizeof(int)/2;++i){
        arr[stop[i][0]][stop[i][1]] = -1;            //障碍物
    }
    arr[endx][endy]=-2;                              //目的地
    arr[startx][starty]=-3;                         //出发点

    draw();
    bfs();

    return 0;
}