写在开头：本文章提供深搜与宽搜的解题思路，无具体题目对应的代码，如想了解，请到个人主页查找，感谢观看。

深度优先搜索（DFS）：

递归，即函数调用自身，以逐步减小问题 的规模。但在一些问题中，并不是所有的 递归路径都是有效的。 如图所示迷宫，很可能会进入橙色所标识 的“死胡同”，只能回到之前的路径，直到 找到绿色的解为止。

这种方法被称为回溯法。 回溯法往往会尝试一条尽可能深而完整的搜索路线，直至完全无 法继续递归时才回溯，因而需要用深度优先搜索(DFS) 实现。

所以学会深度优先搜索前一定要深刻理解递归，先来看一段代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 void dfs(int x){
 4     if(x==0) 
 5         return;
 6     cout<<x<<endl;
 7     dfs(x-1);
 8     cout<<"*"<<x<<endl;
 9 }
10 int main(){
11     dfs(5);
12     return 0;
13 }