前言
在上一篇部落格中，我們學習了搜尋算法的第一種：深度優先搜尋，這篇部落格就讓我們一起來學習另一種大家都經常聽見的搜尋算法：廣度優先搜尋。看名字就知道，他們兩者之間肯定有什麼不可告人的秘密。廣度優先搜尋，又叫寬度優先搜尋，英文名：Breadth First Search。屬于一種盲目搜尋方法，目的是系統的展開并且搜尋圖中所有的點，以找尋結果。我們還是以上篇部落格後面提到的那個迷宮地圖的問題來詳細介紹一下該種算法。
廣度優先搜尋和深度優先搜尋的差別
在上篇部落格中搜尋算法（一）深度優先搜尋，我們提到了地圖迷宮，那麼深度優先搜尋的思路就是，先找一個方向，然後一直往下走，直到走不通的時候再回到這裡。但是廣度優先搜尋就不是這樣了，比如初始點（1,1），他一步可以走到的點有（2,1）（1,2），這兩個點一步能走到的點有（2,2）（1,3）。。。這樣直到達到女朋友所在的點。核心點就是，每一步都找到目前所有能到達的點，在網絡爬蟲的實作中，如是運用了廣度優先搜尋，那麼他就是先将某個一節點的所有同級節點搜尋完成，再對這些節點的下一個節點進行搜尋，更像一層一層的去進行搜尋，而深度優先搜尋，就是以縱深來完成搜尋的。
解決地圖迷宮
具體的題目和規則，請看上篇部落格。
廣度優先搜尋分析
ok，讓我們來具體分析一下，首先呢我們可以循環的地方是，每一步的通過一步所能達到的位置，這部分是可以重複的，比如初始點 （1,1），一步所能達到的點有（2,1）（1,2），然後第二步，從（2，1）（1,2）點開始，分别計算這兩個點，一步所能達到的點有（2,2） （1,1） 和（1,1）（2,2）（1,3）。也就是說我們算法的核心已經能夠确定下來了。然後我們看第二步能達到的點，發現（1,1）點是我們已 經走過的，而我們是不需要重複走的，是以去除掉已經走過的點。還有呢，出現了重複點（2,2），而重複的點，我們也隻需要記錄一次就行 了，是以需要去重。既然是一個遞歸循環，那麼終止的條件是什麼呢？那肯定是能達到的點，已經包含了女朋友所在的點了。
現在，我們已經有了循環的主體，也有了終止循環的條件，那麼，讓我們開始編寫代碼吧。
首先，讓我們編寫一個Point類，來表示坐标上的一個點
public class Point {
public int x;
public int y;
}
然後，來編寫循環的主體 循環的主體其實就是，根據上一步能達到的坐标點，來計算這一步所有能達到的有效的坐标點，以及目前是第幾步
public void extentFS(Point[] points,int step){
step++;//首先将步數加1，然後下面代碼就是下一步能達到的所有點
//初始化一個數組用于存放下一步能到達的點，最多個數和地圖上的點個數相同
Point[] newPoints = new Point[20];
int count = 0 ;//初始化一個值，用于存放點的時候用
for (int i = 0; i < points.length; i++) {
Point point = points[i];
//計算該點，按上右下左的順序一步之内能達到的位置，不包括已經走過的點
for (int j = 0; j < aaa.length; j++) {
Point nextPoint = new Point();
nextPoint.x = point.x+aaa[j][0];
nextPoint.y = point.y + aaa[j][1];
//将目前點，标記為已經走過的點
path[nextPoint.x][nextPoint.y] = 1;
//将目前點，存入下一步能到達點的數組中
count++;
newPoints[count] = nextPoint;
}
}
//繼續下一步的搜尋
extentFS(newPoints,step);
}
上述代碼中，我們已經大緻寫出了循環的主體，首先，傳入參數points：表示上一步的所有點，step，表示上一步是第幾步。 我們通過周遊上一步的所有點，分别計算該點所能達到的坐标位置，和上面算法一樣，用aaa數組來輔助計算，上下左右的點的坐标，然 後将能達到的點存入用于下一步循環的數組newPoints。
但是，我們也需要加上很多限制條件，比如判斷是否是障礙物，判斷是否越界，判斷是否已經走過了。
判斷是否已經走過了，以及是否是障礙物
if (path[nextPoint.x][nextPoint.y] == 0 && map[nextPoint.x][nextPoint.y] == 0){
//判斷點是否已經走過了，已經是否是障礙物
}
判斷是否越界
if (nextPoint.x > 4 || nextPoint.y > 5 || nextPoint.x < 1 || nextPoint.y < 1){
continue;
}
另外，我們每一步循環中，因為不知道下一步能達到的點的個數，是以new了一個25長度的數組，那麼肯定在下一步循環的時候，會出現 空指針的問題，我們也需要進行排除（當然，這裡也可以用其他資料結構來做，動态增加長度，就不需要判斷空指針了）。
if (point == null)
continue;
然後在進行下一步循環之前，我們需要檢查，是否已經找到了女朋友
//周遊得到的下一步能到達點的數組，判斷是否已經達到了女朋友的位置
for (Point newPoint : newPoints) {
if (newPoint == null)
continue;
if (newPoint.x == q && newPoint.y == p){
//說明已經到了女朋友所在的點
Log.i("hero","====找到女朋友啦------一共用了--"+step+"步");
return;
}
}
是以完整的代碼如下 首先初始化
//地圖迷宮
private int[][] aaa = {{0,-1},{1,0},{0,1},{-1,0}};//每步的搜尋順序
private int[][] map = new int[5][6];//初始化地圖，其他地方為了友善是從1開始的，那麼地圖就多一個便于計算
private int[][] path = new int[5][6];//已經走過的路徑點
private int q = 3;
private int p = 4;
private int min = 0;
private int count = 0;
public void mapMaze(){
map[3][1] = 1;//初始化地圖的障礙物
map[3][3] = 1;
map[2][4] = 1;
map[4][5] = 1;
// depthFS(1,1,0);
Point point = new Point();
point.x = 1;
point.y = 1;
Point[] startPoint = new Point[1];
startPoint[0] = point;
breadthFS(startPoint,0);
// Log.i("hero","---找到女朋友啦，最短路線為--"+min+"步");
}
然後，是算法的核心循環
public void breadthFS(Point[] points,int step){
step++;//首先将步數加1，然後下面代碼就是下一步能達到的所有點
//初始化一個數組用于存放下一步能到達的點，最多個數和地圖上的點個數相同
Point[] newPoints = new Point[20];
//第一步，周遊目前的坐标點，然後分别計算每個點下一步能達到的位置，
int count = 0 ;//初始化一個值，用于存放點的時候用
for (int i = 0; i < points.length; i++) {
Point point = points[i];
if (point == null)
continue;
//計算該點，按上右下左的順序一步之内能達到的位置，不包括已經走過的點
for (int j = 0; j < aaa.length; j++) {
Point nextPoint = new Point();
nextPoint.x = point.x+aaa[j][0];
nextPoint.y = point.y + aaa[j][1];
//檢查該點是否越界
if (nextPoint.x > 4 || nextPoint.y > 5 || nextPoint.x < 1 || nextPoint.y < 1){
continue;
}
//檢視該點是否已經走過了 并且不是障礙物
if (path[nextPoint.x][nextPoint.y] == 0 && map[nextPoint.x][nextPoint.y] == 0){
//說明該點還沒走過，并且不是障礙物
//将目前點，标記為已經走過的點
path[nextPoint.x][nextPoint.y] = 1;
//将目前點，存入下一步能到達點的數組中
count++;
newPoints[count] = nextPoint;
}
}
}
//周遊得到的下一步能到達點的數組，判斷是否已經達到了女朋友的位置
for (Point newPoint : newPoints) {
if (newPoint == null)
continue;
if (newPoint.x == q && newPoint.y == p){
//說明已經到了女朋友所在的點
Log.i("hero","====找到女朋友啦------一共用了--"+step+"步");
return;
}
}
//否則的話，就是還沒到女朋友所在的地方，繼續下一步的搜尋
breadthFS(newPoints,step);
}
代碼的執行結果如下
當然，該算法隻是計算了找到女朋友所需要的最小步數，并沒有要求列印出路線，是以也有一些可以擴充的地方，比如可以通過Point裡 面增加參數，來記錄該點的上一個點，就可以完成軌迹的記錄等等。
雖然我們實作了廣度優先算法，也計算出了找到女朋友所需要的最短步數，但是現在讓我們來思考一下，有沒有什麼可以優化的地方呢？ 首先我們上面是通過遞歸來實作的，每次遞歸都會建立一個長度為25的數組，這樣做其實是非常消耗記憶體資源的。那麼有沒有什麼方法可 以避免這樣呢？其實我們可以通過隊列（queue）和一個while循環來實作算法，我們先将（1,1）點放入隊列中，然後開始找下一步能達到 的點（1,2）（2,1）并且也将它們放入隊列中，當while本次循環查找完目前點，所有能達到的有效點，并且将它們放入隊列中，就将目前 點移出隊列，根據隊列先進先出的原則，while的下次循環，會開始查下我們之前存入的有效點，一步所能達到的所有有效點，直到我們找 到我 們的女朋所在的點為止。
具體代碼如下
初始化地圖等
//地圖迷宮
private int[][] aaa = {{0,-1},{1,0},{0,1},{-1,0}};//每步的搜尋順序
private int[][] map = new int[5][6];//初始化地圖，其他地方為了友善是從1開始的，那麼地圖就多一個便于計算
private int[][] path = new int[5][6];//已經走過的路徑點
private int q = 3;
private int p = 4;
private int min = 0;
private int count = 0;
public void mapMaze(){
map[3][1] = 1;//初始化地圖的障礙物
map[3][3] = 1;
map[2][4] = 1;
map[4][5] = 1;
// depthFS(1,1,0);
int i = breadthFSBasic();
if (i == -1){
Log.i("hero","---地圖找了個遍，都沒發現女朋友---");
}else {
Log.i("hero","---找到女朋友啦，最少需要--"+i+"步");
}
// breadthFS(startPoint,0);
// Log.i("hero","---找到女朋友啦，最短路線為--"+min+"步");
}
算法的主體
public int breadthFSBasic(){
Point point = new Point();
point.x = 1;
point.y = 1;
point.step = 0;
Queue<Point> queue = new LinkedList<>();
queue.add(point);
//如果隊列不為空，則繼續
while (!queue.isEmpty()){
Point remove = queue.remove();
for (int i = 0; i < aaa.length; i++) {
Point newPoint = new Point();
newPoint.x = remove.x+aaa[i][0];
newPoint.y = remove.y+aaa[i][1];
newPoint.step = remove.step + 1;
//檢查是否越界
if (newPoint.x < 1 || newPoint.y < 1 || newPoint.x>4 || newPoint.y > 5)
continue;
//檢查是否是已經走過點或者是障礙物
if (path[newPoint.x][newPoint.y] == 0 && map[newPoint.x][newPoint.y] == 0){
path[newPoint.x][newPoint.y] = 1;
//判斷是否是女朋友
if (newPoint.x ==q && newPoint.y == p){
// Log.i("hero","---找到女朋友了---一共用了"+"步");
return newPoint.step;
}
queue.add(newPoint);
}
}
}
return -1;
}
其實上述代碼，就是廣度優先搜尋最基本的樣子。
總結
當然，本篇文章和上篇文章都隻是簡單的對深度優先搜尋和廣度優先搜尋進行了一些學習。而且用了一個比較實際的運用地圖迷宮來實際 用這兩種算法來解決問題。其實這兩種算法都是圖的搜尋算法中非常基礎的兩種。我們可能在面試或者筆試中更多的被問到的是在二叉樹 周遊中的使用。通過這兩篇文章加上二叉樹的一些特性，相信我們已經可以通過這兩種算法完成二叉樹的周遊了。具體的實作，就需要大 家多多編碼練習了。 因個人水準有限，文章中難免有錯誤和不足之處，請各位多多指正。 下期預告，在介紹了兩種最基礎的搜尋算法之後，我們将要學習的是幾種求最短路徑的算法。咦，是不是感覺地圖迷宮其實也是最短路徑？ 但是我們要說的跟地圖迷宮并不太相同。我們将系統的學習Floyed-Warshell、Dijkstra、Bellman-Ford等幾種求解最短路徑的算法。
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)