深搜与广搜

系列：算法
 • 算法, dfs, bfs

搜索其实挺常见的，但是与搜索引擎并不一样，并不是再庞大的数据中找到匹配的（更类似的是字符串匹配），dfs与bfs更多是指在所有可能的结果中找到可用的结果和对应的路径（后者往往dfs比bfs更加自然，因为dfs常见的实现方式是递归，而bfs基本都是靠队列实现，不过下文我将使用另一种方式指出二者的共通性）

dfs，即深度优先搜索，重点在于深，即一条路走到死，不行再换。这也是为什么常见递归写法的原因，附上简单的伪代码示例:

cpp
1int dfs(int now, int last) {
2 if(now满足条件) {
3 do_some_thing();
4 return 1;
5 }
6 do_onther_thing();
7 for(每种可能选择) {
8 if(是新的情况)
9 dfs(选择, now);
10 }
11 return 0;
12}

不难看出，dfs只需要记录return 1;时的选择就可以做到记录下找到结果对应的路径对的原因。而且dfs的优势在于完整遍历每一种情况，同时思维更符合人脑（方便调试）

至于bfs，广度优先搜索，则是另一种思维，先把每种路都看一遍，保证视野足够的广，正因如此，不太适合递归一类的方式，常见的是使用队列实现:

cpp
1int bfs() {
2 queue q;
3 q.push(初始位置);
4 while(!q.empty()) {
5 do_some_thing();
6 int now = q.front();
7 q.pop();
8 for(每种可能选择)
9 if(是新的情况) {
10 q.push(选择);
11 记录已被处理
12 }
13 }
14}

bfs的优势主要在于能够找到最短路，比如Dijkstra就是典型的bfs。

但是不妨发散一下思维，递归的本质是让调用栈决定了谁先谁后的问题，所以两者本质上是高度相同的，完全可以尝试:

cpp
1int dfs_or_bsf(type stack_or_queue) {
2 stack_or_queue t;
3 t.push(初始位置);
4 while(!t.empty()) {
5 do_some_thing();
6 int now = t.top();
7 t.pop();
8 for(每种可能选择)
9 if(没被使用过)
10 t.push(选择);
11 }
12}

虽然这种行为并没有什么实际意义，但是自认为对于算法的理解是有着加深作用的，至少可以明白，dfs与bfs，两者不只是名字上接近，实际上内核也只有一个queue与stack的区别。未来还会接触不少搜索算法，最后的dfs_or_bsf可以是用不少情况，基本都是type的各种变化。

如果容器是LIFO（栈），就是DFS；如果是FIFO（队列），就是BFS；如果是优先队列，就是带权搜索（如Dijkstra、A*）。