# 廣度優先搜索
廣度優先搜索碰到岔路口時，總是依次訪問該路口可直接到達的所有岔路，直至遇到新的岔路口，并記下這些岔路口。下一次從新的岔路口依次重復原來的操作。廣度優先搜索適合用隊列實現，一個元素出隊，將該元素可直接到達的所有元素依次放入隊尾。
## 求解迷宮問題
```C
#include <stdio.h>
#define MaxSize 500
// 建立隊列
struct SqQueue{
int i, j;
int pre;
}qu[MaxSize];
int front = -1, rear = -1;
void print(int front);
int main()
{
// 建立迷宮
int mg[10][10]={
{1,1,1,1,1,1,1,1,1,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,0,0,1,1,0,0,1},
{1,0,1,1,1,0,0,0,0,1},
{1,0,0,0,1,0,0,0,0,1},
{1,0,1,0,0,0,1,0,0,1},
{1,0,1,1,1,0,1,1,0,1},
{1,1,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1}
};
// 標記起點和終點
int si, sj, ei, ej;
si = sj = 1;
ei = ej = 8;
// 在隊列中放入起始點
int i, j, di;
rear++;
qu[rear].i = si; qu[rear].j = sj; qu[rear].pre = -1;
mg[si][sj] = -1;
while(front!=rear){
front++;
i = qu[front].i; j = qu[front].j;
if(i==ei && j==ej){
print(front);
return 1;
}
for(di=0; di<4; di++){
// 將可能的狀態入隊
switch(di){
case 0: i = qu[front].i; j = qu[front].j+1; break;
case 1: i = qu[front].i+1; j = qu[front].j; break;
case 2: i = qu[front].i; j = qu[front].j-1; break;
case 3: i = qu[front].i-1; j = qu[front].j; break;
}
if(mg[i][j]==0){
rear++;
qu[rear].i = i; qu[rear].j = j; qu[rear].pre = front;
mg[i][j] = -1;
}
}
}
printf("There is no path!\n");
return 0;
}
void print(int front)
{
int k = front, j;
do{
j = k;
k = qu[k].pre;
qu[j].pre = -1;
}while(k!=0);
printf("Find the path that:\n");
k = 0;
int ns = 0;
while(k<=front){
if(qu[k].pre==-1){
ns++;
printf("\t(%d, %d)", qu[k].i, qu[k].j);
if(ns%5==0)
printf("\n");
}
k++;
}
}
```
