深度優先搜索與廣度優先搜索

今天做筆試題遇到兩個很有代表性的題目，分別用到了廣度優先搜索和深度優先搜索，可以記錄并分析一下。

廣度優先搜索

首先來看一下題目：

題目描述
定義一個二維數組N*M(其中2<=N<=10;2<=M<=10)，如5 × 5數組下所示： 
int maze[5][5] = {

        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,

};
它表示一個迷宮，其中的1表示墻壁，0表示可以走的路，只能橫著走或豎著走，
不能斜著走，要求編程序找出從左上角到右下角的最短路線。
入口點為[0,0],既第一空格是可以走的路。
Input
一個N × M的二維數組，表示一個迷宮。數據保證有唯一解,不考慮有多解的情況，即迷宮只有一條通道。
Output
左上角到右下角的最短路徑，格式如樣例所示。
Sample Input
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
Sample Output
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)

從題意來看的話因為要搜索的是最短路徑，所有應該是用廣度優先搜索算法沒跑了。

廣度優先搜索(Breadth First Search, BFS)，又叫寬度優先搜索，是一種窮舉的搜索算法，算法把所有展開的節點放入一個先進先出的隊列中，依次搜索解，因此，如果算法有解的話，一定是最優解或最優解之一。BFS常用隊列或鏈表實現。

直接上代碼：

#include <iostream>
#include <list>
#include <vector>
using namespace std;

typedef struct node
{
    int x;
    int y;
    int id; // 節點ID
    int patent; // 父節點ID
}node;

inline bool isvalid(int x, int y, int m, int n)
{
    if (x >= 0 && x < m &&
        y >= 0 && y < n)
        return true;
    return false;
}

int BFS(vector<vector<int>> &maze, vector<node> &node_table, int start_x, int start_y, int end_x, int end_y)
{
    // 基本思想，廣度優先，找最短路徑
    int m, n, id = 0,
        new_x, new_y;
    n = maze.size();
    m = maze[0].size();
    // open table
    list<node> open = { node_table[id] };
    id++;
    // close table
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    visited[0][0] = true;
    // 四個方向
    vector<pair<int, int>> dir = { { -1, 0 },{ 0, -1 },{ 1, 0 },{ 0, 1 } };
    // 廣度優先
    while (!open.empty())
    {
        node cur = open.front(); // 每次從open表取出一個節點
        open.pop_front();
        // 已經找到
        if (cur.x == end_x && cur.y == end_y) return cur.id;
        // 四個方向擴展子節點
        for (int i = 0; i < 4; ++i)
        {
            new_x = cur.x + dir[i].first;
            new_y = cur.y + dir[i].second;
            if (isvalid(new_x, new_y, n, m) && maze[new_x][new_y] != 1 && !visited[new_x][new_y])
            {
                node &tmp = node_table[id];
                tmp.x = new_x;
                tmp.y = new_y;
                tmp.id = id;
                tmp.patent = cur.id;
                open.push_back(tmp);
                visited[new_x][new_y] = true;
                id++;
            }
        }
    }
    return -1;
}

// 遞歸輸出路徑
void print_path(vector<node> &node_table, int id)
{
    if (node_table[id].patent != -1)
        print_path(node_table, node_table[id].patent);

    cout << "(" << node_table[id].x << "," << node_table[id].y << ")" << endl;
}

int main(void)
{
    int n, m, id;
    while (cin >> n >> m)
    {
        vector<vector<int>> maze(n, vector<int>(m, 0));
        // node 表
        vector<node> node_table(m * n, { 0, 0, 0, -1 });
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < m; ++j)
            {
                cin >> maze[i][j];
            }
        }
        id = BFS(maze, node_table, 0, 0, n - 1, m - 1);
        print_path(node_table, id);
    }
    return 0;
}

可以看到代表并不是很復雜，BFS算法都在BFS這個函數中，而node這個結構主要是用來記錄路徑用的，便于找到路徑之后通過遞歸展開輸出路徑。BFS函數中的思路也比較清晰，不斷從open表頭出去節點，并把擴展的子節點加入到open表尾部，即先進先出的思想。

由于BFS中已經被訪問過的節點如果第二次被訪問，那么第二次訪問時候的路徑長度必然大于(或等于)第一次訪問時的路徑長度，因此就第二次訪問的時候就不需要考慮該節點了，所以我們只需要記錄被訪問過的節點，而不用撤銷訪問(和DFS有所區別)。

深度優先搜索

如果說廣度優先搜索適合搜索最優解，那么深度優先搜索就是適合搜索是否存在解。還是先來看問題：

請設計一個函數，用來判斷在一個矩陣中是否存在一條包含某字符串所有字符的路徑。
路徑可以從矩陣中的任意一個格子開始，每一步可以在矩陣中向左，向右，向上，向下移動一個格子。
如果一條路徑經過了矩陣中的某一個格子，則該路徑不能再進入該格子。 
例如：
abce
sfcs
adee 
矩陣中包含一條字符串"bcced"的路徑，但是矩陣中不包含"abcb"路徑，
因為字符串的第一個字符b占據了矩陣中的第一行第二個格子之后，路徑不能再次進入該格子。

從題意可以看出，需要找到是否包含該路徑，也就是找到是否存在解，所以此處用深度優先搜索比較合適。深度優先搜索展開子節點后把子節點加入到open表的頭部，因此適合用遞歸來實現。

直接上代碼：

#include <iostream>
#include <list>
#include <vector>
using namespace std;

class Solution {
public:
    bool hasPath(char* matrix, int rows, int cols, char* str)
 {
        this->matrix = matrix;
        this->str = str;
        this->rows = rows;
        this->cols = cols;
        // visited
        vector<vector<bool>> visited(rows, vector<bool>(cols, false));
        // 尋找迷宮起點
        for (int i = 0; i < rows * cols; ++i)
        {
            if (matrix[i] == str[0])
            {
                visited[i / cols][i % cols] = true;
                if (DFS(i / cols, i % cols, 0, visited)) return true;
                visited[i / cols][i % cols] = false;
            }
        }
        return false;
    }

    bool isvalid(int x, int y)
 {
        if (x >= 0 && x < rows && y >= 0 && y < cols)
            return true;
        return false;
    }

    bool DFS(int x, int y, int str_index, vector<vector<bool>> &visited)
 {
        // 四個方向
        static pair<int, int> dir[] = { {-1, 0}, {0, -1}, {1, 0}, {0, 1} };
        int new_x, new_y;

        if (str[str_index] == matrix[x * cols + y])
        {
            if (str[str_index + 1] == '\0') return true;
            for (int i = 0; i < 4; ++i)
            {
                new_x = x + dir[i].first;
                new_y = y + dir[i].second;
                if (isvalid(new_x, new_y) && !visited[new_x][new_y])
                {
                    visited[new_x][new_y] = true;
                    if (DFS(new_x, new_y, str_index + 1, visited))
                        return true;
                    visited[new_x][new_y] = false;
                }
            }
        }
        return false;
    }
private:
    int rows;
    int cols;
    char *matrix;
    char *str;
};

int main(void)
{
    Solution sss;
    cout << sss.hasPath("abcesfcsadee", 3, 4, "abcd");
    return 0;
}

可以看到，DFS的代碼和BFS的代碼十分類似。說一下區別：1. DFS采用遞歸來實現; 2. 訪問表在進入函數之間置位，而在退出函數之后需要復位。原因是因為DFS在訪問的時候有一個回溯的過程，如果子節點沒有得到需要的解，那么就需要回溯的父節點，并擴展父節點的其他子節點來搜索解，因此原來被子節點訪問過的位置現在應該撤銷訪問。

總結

BFS和DFS是兩種十分重要的搜索算法，BFS適合查找最優解，DFS適合查找是否存在解(或者說能找到任意一個可行解)。

來自：http://yosef-gao.github.io/2016/08/06/bfs-and-dfs/