开启生长之旅！这是我参加「日新方案 12 月更文挑战」的第20天，点击查看活动概况。

一，什么是查找算法

算法是基于特定数据结构之上的，深度优先查找算法和广度优先查找算法都是基于“图”这种数据结构的。

树是图的一种特例（连通无环的图便是树）。

图上的查找算法，最直接的了解便是，在图中找出从一个极点动身，到另一个极点的途径。具体方法有许多，两种最简单、最“暴力”的深度优先、广度优先查找，还有 A*、IDA* 等启发式查找算法。深度优先查找算法和广度优先查找算法，既能够用在无向图，也能够用在有向图上。

图（选用邻接表存储）的 C++ 代码完结如下：


#include <list>
// 无向图结构的定义
class Graph{
private:
    int v;  // 极点个数
    list<int> adj()  // 存储的邻接表
public:
    // 结构函数定义
    Graph(int v){
        adj = new List<int>(v);
        for (int i = 0; i < v; i++){
            adj[i] = new list<int> ();
        }
    }
    // 无向图一条边存储 2 次
    void addEdge(int s, int t){
        adj[s].push_back(t);
        adj[t].push_back(s);
    }
}

二，广度优先查找（BFS）

广度优先查找（Breadth-First-Search），咱们往常都简称 BFS。直观地讲，它其实便是一种“地毯式”层层推动的查找战略，即先查找离开始极点最近的，然后是次近的，依次往外查找。

求图中开始极点 s 到停止极点 t 的最短途径，可使用 bfs 算法，代码如下：

#include <queue>
using namespace std;
void bfs(int s, int t){
    if( s==t ) return;
    bool visited[v];  // 用来记载现已拜访过的极点, v 表明极点个数
    queue<int> queue; // 一个行列，用来存储现已被拜访、但相连的极点还没有被拜访的极点。
    queue.push_back(s); // 添加开始极点
    vector<int> prev(v, -1); // prev 用来记载查找途径, prev[w]存储的是，极点 w 是从哪个前驱极点遍历过来的。
    while(queue.size() != 0){
        int w = queue.pop();
        for(int i= 0; i<adj[w].size();++i){
            int q = adj[w].at(i);
            if(!visited[q]){
                prev[q] = w;
                if(q==t){
                    print_map(prev, s, t);
                    return;
                }
                visited[q] = true;
                queue.add(q);
            }
        }
    }
void print_map(int prev[], int s, int t){
    if(prev[t] != -1 && t!=s){
        print_map(prev, s, prev[t]);
    }
    cout << t << "+ ";
}

queue 是一个行列，用来存储现已被拜访、但相连的极点还没有被拜访的极点。因为广度优先查找是逐层拜访的，也便是说，咱们只要把第 k 层的极点都拜访完结之后，才干拜访第 k+1 层的极点。当咱们拜访到第 k 层的极点的时分，咱们需求把第 k 层的极点记载下来，稍后才干经过第 k 层的极点来找第 k+1 层的极点。所以，咱们用这个行列来完结记载的功用。

prev 用来记载查找途径。当咱们从极点 s 开始，广度优先查找到极点 t 后，prev 数组中存储的便是查找的途径。不过，这个途径是反向存储的。prev[w]存储的是，极点 w 是从哪个前驱极点遍历过来的。比如，咱们经过极点 2 的邻接表拜访到极点 3，那 prev[3]就等于 2。为了正向打印出途径，咱们需求递归地来打印。

最坏情况下，停止极点 t 离开始极点 s 很远，需求遍历完整个图才干找到。这个时分，每个极点都要进出一遍行列，每个边也都会被拜访一次，所以，广度优先查找的时刻复杂度是 O(V+E)O(V+E)，其中，V 表明极点的个数，E 表明边的个数。当然，关于一个连通图来说，也便是说一个图中的一切极点都是连通的，E 肯定要大于等于 V-1，所以，广度优先查找的时刻复杂度也能够简写为 O(E)O(E)。

广度优先查找的空间消耗主要在几个辅佐变量 visited 数组、queue 行列、prev 数组上。这三个存储空间的大小都不会超越极点的个数，所以空间复杂度是 O(V)O(V)。

三，深度优先查找（DFS）

深度优先查找（Depth-First-Search），简称 DFS。

最直观的比如便是“走迷宫”。假定你站在迷宫的某个岔路口，然后想找到出口。你随意挑选一个岔路口来走，走着走着发现走不通的时分，你就回退到上一个岔路口，重新挑选一条路继续走，直到终究找到出口。这种走法便是一种深度优先查找战略。

bool found = false;  // 类成员变量
void dfs(int s, int t){
    found = false;
    bool visited[v];  // v 表明极点个数
    int prev[v];
    for(int i=0; i< v;i++){
        prev[i] = -1;
    }
    recurDFS(s, t, visited, prev);
    print_map(prev, s, t)
}
void recurDFS(int w, int t, bool visited[], int prev[]){
    if(found == true) return;
    visited[w] = true;
    if(w == t){
        found = true;
        return;
    }
    for(int i = 0; i < adj[w].size();++i){
        int q = adj[w].at(i);
        if(!visited[q]){
            prev[q] = w;
            recurDFS(q, t, visited, prev);
        }
    }
}

四，内容总结

广度优先查找，通俗的了解便是，地毯式层层推动，从开始极点开始，依次往外遍历。广度优先查找需求凭借行列来完结，遍历得到的途径便是，开始极点到停止极点的最短途径。深度优先查找用的是回溯思维，十分适合用递归完结。换种说法，深度优先查找是凭借栈来完结的。在履行效率方面，深度优先和广度优先查找的时刻复杂度都是 O(E)O(E)，空间复杂度是 O(V)O(V)。

参考资料

《数据结构与算法之美》-深度和广度优先查找