宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。
光用语言描述起来可能不太理解，下面直接看一道关于bfs类似的题
1 int data[5][5]={ 2 {0,1,0,0,0}, 3 {0,1,0,1,0}, 4 {0,0,0,0,0}, 5 {0,1,1,1,0}, 6 {0,0,0,1,0} 7 };
迷宫问题，首先0代表可以顺利通过，但是1代表墙壁，即无法通过
起始点是在(0 0),终点是在(4 4)，请找出一条通路，并打印出其路径
由于这个题是需要打印出其路径，所以我们首先要定义一个pre是用来指向此刻路径的父亲路径，只有这样当我们找到（4，4）的时候，我们才可以凭借着其父亲路径将从起点到终点的路径输出出来
1、首先我们要定义一个结构体，结构体里面可以存储我们通过的路径，代码如下：
1 typedef struct sss 2 { 3 int x,y; 4 int pre; //记录其父亲路径的位置 5 }qq; 6 qq queue[100];
2、其次由于在迷宫中摸索的时候是需要有方向的，所以我们还需要定义一个二维数组去指示下一步的方向，代码如下：
1 int dxy[4][2]={ 2 {-1,0},{0,1},{1,0},{0,-1} 3 }; //（-1，0）就相当于是此刻的x坐标-1，y坐标不动，即是向上一个单位，（0，1），（1.0），（0，-1）也是同理
3、我们还要定义一个数组用来表示当前路径是否被访问过，代码如下：
1 int visit[5][5]={0}; //0代表未访问，1代表已访问
如果这几个都定义好了，其实也就没啥了，接下来就是整体代码环节了：
1 #include <stdio.h> 2 int data[5][5]={ 3 {0,1,0,0,0}, 4 {0,1,0,1,0}, 5 {0,0,0,0,0}, 6 {0,1,1,1,0}, 7 {0,0,0,1,0} 8 }; 9 10 typedef struct sss 11 { 12 int x,y; 13 int pre; 14 }qq; 15 qq queue[100]; 16 int dxy[4][2]={ 17 {-1,0},{0,1},{1,0},{0,-1} 18 }; 19 int visit[5][5]={0}; //0代表未访问，1代表已访问 20 21 void bfs(int s,int d); 22 void print_data(int rear); 23 bool cmp(int next_x,int next_y); 24 int main(int argc, char *argv[]) 25 { 26 27 bfs(0,0); 28 return 0; 29 } 30 31 void bfs(int s,int d) 32 { 33 int front=0,rear=1; 34 int next_x,next_y; 35 int i; 36 queue[front].x=s; 37 queue[front].y=d; 38 queue[front].pre=-1; 39 visit[s][d]=1; 40 41 while(front<rear) 42 { 43 for(i=0;i<4;i++) 44 { 45 next_x=queue[front].x+dxy[i][0]; 46 next_y=queue[front].y+dxy[i][1]; 47 if(cmp(next_x,next_y)) 48 { 49 queue[rear].x=next_x; 50 queue[rear].y=next_y; 51 queue[rear].pre=front; 52 visit[next_x][next_y]=1; 53 rear++; 54 } 55 else 56 continue; 57 58 if(next_x==4&&next_y==4) 59 { 60 print_data(rear-1); 61 } 62 } 63 front++; 64 } 65 66 } 67 68 void print_data(int rear) 69 { 70 if(rear!=-1) 71 { 72 print_data(queue[rear].pre); 73 printf("(%d %d)\n",queue[rear].x,queue[rear].y); 74 } 75 } 76 77 bool cmp(int next_x,int next_y) 78 { 79 if(next_x>=0&&next_x<5&&next_y>=0&&next_y<5&&visit[next_x][next_y]==0&&data[next_x][next_y]==0) 80 return true; 81 else 82 return false; 83 }
下面来分析一下代码的执行过程
| 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 0 | 0 | 0 | 1 | 0 |
首先，这就是那个迷宫，起点在（0，0），终点在（4，4），现在让找到一条通路输出，首先由于（0，0）
是起点，所以我们应该将（0，0）放入到结构体数组queue[0]中，因为我们还需要找下一个邻接的next_x和next_y，所以我们应该定义一个指向当前的位置的front和指向下一个位置的rear，在初始时front=0,rear=1，，所以我们将（0，0）放入到结构体数组queue[0]中并设置为已经访问后，
| 数组下标 | x | y | pre(父亲位置) |
| 0 | 0 | 0 | -1 |
然后找寻下一个节点，当我们执行for语句的时候即是在遍历当前位置的四个方向，找出满足条件的将其放入到结构体数组中，通过四个方向找完后发现只有next_x=1,next_y=0是满足条件的，在将其存入到数组中的时候要注意他的父亲位置是0也就是front,故将其存入数组并设置为已经访问后
| 数组下标 | x | y | pre(父亲位置) |
| 0 | 0 | 0 | -1 |
| 1 | 1 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 0 | 0 | 0 | 1 | 0 |
此刻判断当前的位置是否到终点了，明显是没有到的，故rear++,front++,此时front=1,rear=2，此时要从（1，0）开始找邻接点了，同理当next_x=2,next_y=0时是符合条件的，将其装入数组并设置为已经访问后，
| 数组下标 | x | y | pre(父亲位置) |
| 0 | 0 | 0 | -1 |
| 1 | 1 | 0 | 0 |
| 2 | 2 | 0 | 1 |
| 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 0 | 0 | 0 | 1 | 0 |
此时通过判断是没有到达终点的，所以front++,rear++,rear=3,front=2,此时通过找寻发现（2，1）和（3，0）都是符合的，所以都加入到数组中
| 数组下标 | x | y | pre(父亲位置) |
| 0 | 0 | 0 | -1 |
| 1 | 1 | 0 | 0 |
| 2 | 2 | 0 | 1 |
| 3 | 2 | 1 | 2 |
| 4 | 3 | 0 | 2 |
| 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 0 | 0 | 0 | 1 | 0 |
此时判断依旧没有到达终点，则继续往下找，此时的front=3,rear=5,则开始从（2，1）继续往下找，则（2，2）是符合的，所以同理
| 数组下标 | x | y | pre(父亲位置) |
| 0 | 0 | 0 | -1 |
| 1 | 1 | 0 | 0 |
| 2 | 2 | 0 | 1 |
| 3 | 2 | 1 | 2 |
| 4 | 3 | 0 | 2 |
| 5 | 2 | 2 | 3 |
| 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 0 | 0 | 0 | 1 | 0 |
此时的front=4,rear=6,则开始从（3，0）开始找起，（4，0）是符合条件的，所以同理
| 数组下标 | x | y | pre(父亲位置) |
| 0 | 0 | 0 | -1 |
| 1 | 1 | 0 | 0 |
| 2 | 2 | 0 | 1 |
| 3 | 2 | 1 | 2 |
| 4 | 3 | 0 | 2 |
| 5 | 2 | 2 | 3 |
| 6 | 4 | 0 | 4 |
依次找下去即可，这里就不一步一步了，相信看到这里，您应该都懂了，希望着篇文章能对您有帮助，谢谢