深度优先搜索（Depth-First Search）

概念

一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件，搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。属于盲目搜索,最糟糕的情况算法时间复杂度为O(!n)。

实现

要满足深搜的实现，我们必然需要用到一些工具，比如如何能建立遍历时前后两个点的联系，如何在遍历结束后返回到上一个点？这些问题的答案就在“栈”中，栈是具有先进后出特性的，上下两点之间具备联系，而且可以遍历结束后回到我们上一个点，因此栈可以满足我们深搜的需求。

但是还有一种方式，天然满足我们这种需求，那就是“递归”。

递归天然可以进入到下一个节点，结束完函数操作后，又可以返回到上一个函数节点继续操作，而且递归相较于栈也更容易被大家所理解，因此递归是一个更易懂的深搜工具。

那么让我们来回忆一下递归的操作：

#include<iostream>
using namespace std;

// 计数器
int count = 0;

// 递归函数
void function() {
    // 递归跳出条件
    if (cout > 100)
        return;
    cout << count << endl;
    // 递归：函数自己调用自己
    function();
}

int main() {
    // 递归调用
    function();
    return 0;
}

现在，让我们来分析一下深搜与递归的相同点和不同点。

深搜的递归函数也需要跳出条件，也需要自行调用，区别是深搜在遍历时候递归调用的点，需要返回上一个点时还原上一个的状态。因此这里需要一个“回溯”操作。伪代码如下：

void dfs(int step)
{
        判断边界 {
            相应操作
        }

        尝试每一种可能 {
            if(满足check条件) {
                标记
                继续下一步dfs(step+1)
                恢复初始状态（回溯的时候要用到）
            }
        }
}  

说完了递归，那我们的栈呢？当然也可以用栈，而且很多时候，通过“栈实现深搜”的时间复杂度会小于通过“递归实现深搜”的时间复杂度。究竟如何实现？如下：

stack<int> st;

返回