轉載請注明本文出自大苞米的博客（http://go.rritw.com/blog.csdn.net/a396901990），謝謝支持！

深度優先搜索（Depth First Search，DFS）

主要思想：不撞南牆不回頭

深度優先遍曆的主要思想就是：首先以一個未被訪問過的頂點作为起始頂點，沿當前頂點的邊走到未訪問過的頂點；當沒有未訪問過的頂點時，則回到上一個頂點，繼續試探訪問別的頂點，直到所有的頂點都被訪問。

沿着某條路徑遍曆直到末端，然後回溯，再沿着另一條進行同样的遍曆，直到所有的頂點都被訪問過为止。

圖解：

分析：

通過上面的圖例可以非常直觀的了解深度優先搜索的工作方式。下面來分析一下如何用代碼來實現它。 
大家都知道，深度優先的主要思想就是“不撞南牆不回頭”，“一條路走到黑”，如果遇到“牆”或者“無路可走”時再去走下一條路。

所以先規定好一個走路的規則，比如就按照右下左上順時針的方式去嘗試。

如上圖僵尸的位置是起始點，先往右走，但是有堵牆走不了，所以按照規定嘗試往下走。到達“1”的位置，此時重复剛才的步驟，先向右走可以走到“2”，再重复規則發現向右可以走到“3”，再重复發現“下右左上”四個方向都不能走，這時候就退回“2”的位置嘗試向下走。。。依次類推直到走到最終的目的地。

聰明的你肯定已經發現了“遞歸”是實現深度優先搜索的最好的方式。定義好規則然後就這样遞歸的循環下去直到走到終點，請看下面的偽代碼：

void dfs()  
{  
    // 判斷是否到達終點
    if() {
        return;
    }

    // 嘗試每一個可走方向（右下左上） 
    for(i=0; i<n; i++){ 
        // 判斷是否可走,可走調用遞歸嘗試下一步，不可走則嘗試該點的其他方向
        if () {
            // 繼續下一步  
            dfs();  
        }
    }  
}  

代碼：

程序中完整的深度優先搜索代碼如下：

    // 深度優先搜索
    public void DFS( int x, int y )
        throws Exception
    {

        int tx, ty;

        int[] pos =
            { x, y };
        dfs_posList.add(pos);

        // 是否到達目的地
        if (mMapView[y][x] == 8)
        {
            throw new Exception("find");
        }

        // 順時針循環，右下左上四個方向
        for (int k = 0; k < 4; k++)
        {
            tx = x + next[k][1];
            ty = y + next[k][0];

            // 是否出了邊界
            boolean isOut = tx < 0 || tx >= mapWidth || ty < 0 || ty >= mapHeight;
            if (!isOut)
            {

                // 是否是障礙物
                if (mMapView[ty][tx] == 0 && dfs_book[tx][ty] == 0 || mMapView[ty][tx] == 8)
                {
                    dfs_book[tx][ty] = 1;
                    DFS(tx, ty);
                    dfs_book[tx][ty] = 0;
                }
            }

        }
    }

// 判斷方向的數組
int[][] next =
        {
                { 0, 1 }, // 右
                { 1, 0 }, // 下
                { 0, -1 }, // 左
                { -1, 0 } // 上
        };

廣度優先搜索（Breadth First Search, BFS）

主要思想：層層遞進

首先以一個未被訪問過的頂點作为起始頂點，訪問其所有相鄰的頂點，然後對每個相鄰的頂點再訪問它們相鄰的未被訪問過的頂點，直到所有頂點都被訪問過，遍曆結束。

圖解：

分析：

通過兩個圖例的對比，可以清楚的看到兩種搜索算法的區別。 
深度優先就是一條路走到底，然後再嘗試下一條路。 
廣度優先就是走到一個點，將該點周圍可走的點走完，然後再按同样規則走其他的點。（大家可以想像一下鋪滿的多米諾骨牌，將其中一塊推倒其餘周圍的骨牌也會一層層擴散式的倒塌）

所以先規定好一個走路的規則，同样按照右下左上順時針的方式去嘗試。

如上圖僵尸的位置是起始點，先往右走，但是有堵牆走不了，所以按照規定嘗試往下走。到達“1”的位置，在“1”處可以知道四周能走的點只有“2”。“2”能走的點有“3”，“4”。來到“3”，發現沒有可走的。來到“4”發現去可以去“5”。這样依次進行下去就完成了廣度優先搜索。

我們可以通過“隊列”來模擬上面的過程，偽代碼如下：

void dfs()  
{  
    // 創建一個隊列
    Queue queue = new Quene();
    // 將起點加入隊列中
    queue.offer("起點");

    // 循環隊列直到隊列沒有元素
    while(queue!＝null) ｛
        // 從隊列中取出一個點(並移除)
        p ＝ quene.poll();

        // 循環嘗試p點附近可走的點（右下左上） 
        for(i=0; i<n; i++) {

            // 判斷是否到達目的地
            if() {
            }

            // 判斷是否可走,可走將該點加入到隊列中，不可走則嘗試該點的其他方向
            if () {
                queue.offer("新點");
            }
        }  
    ｝ 

}  

完整代碼：

// 廣度優先搜索（Breadth First Search）
    public void BFS()
    {

        // 存儲點的序列
        Queue<int[]> queue = new LinkedList<int[]>();

        int x, y;
        int[] pos =
            { 0, 0 };
        queue.offer(pos);

        while (!queue.isEmpty())
        {
            // 從隊列中取出並移除
            pos = queue.poll();
            bfs_posList.add(pos);

            // 順時針循環，右下左上四個方向
            for (int k = 0; k < 4; k++)
            {
                x = pos[0];
                y = pos[1];

                // 是否到達目的地
                if (mMapView[y][x] == 8)
                {
                    return;
                }

                x += next[k][1];
                y += next[k][0];

                // 是否出了邊界
                boolean isOut = x < 0 || x >= mapWidth || y < 0 || y >= mapHeight;
                if (!isOut)
                {
                    // 是否是障礙物
                    if (mMapView[y][x] == 0 && bfs_book[x][y] == 0  || mMapView[y][x] == 8)
                    {
                        bfs_book[x][y] = 1;
                        queue.offer(new int[]
                            { x, y });
                    }
                }

            }
        }
    }

    int[][] next =
        {
                { 0, 1 }, // 右
                { 1, 0 }, // 下
                { 0, -1 }, // 左
                { -1, 0 } // 上
        };

寫在最後

相信通過上面的配圖和講解可以很清晰的理解深度優先搜索和廣度優先搜索，如果今後有時間我爭取再做一個最短路徑的小Demo。

本例代碼已經上傳到我的github，感興趣的可以下載來玩玩（純屬娛樂沒啥實際價值）：http://go.rritw.com/github.com/a396901990/PathFind