前言：
谢谢AC君的支持
本帖也放在了讲解题目的题解区中，欢迎各位（剩下看彩蛋）
问：
为什么我（自问自答）的精华帖都加上了自己手搓的图片
答：
因为之前一个帖子没加图片被某人喷是AI，说了也不听，后来只能删帖了（是谁我不说，不是那个素数的）。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
废话不多说，正片开始。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
深搜的定义：
深度优先搜索就是在一个图（树）中遍历搜索的算法，从一个根节点（如果是图的话随便找个点当根节点或按题目要求）进行深度遍历。深搜会沿着一条路径不断的深入去搜索，直到该点没有任何相邻节点或相邻节点全被探索过，即无路可走。那么这时我们就回到上一个访问的节点，继续探索该节点的路径，若该节点也没有可遍历的点则回到上一个节点继续搜索，以此类推。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
深搜过程：
接下来用一个树来模拟整个深搜的过程。这里为了方便区分，空白代表未搜索，淡紫色代表已搜索，橙色代表当前搜索节点，绿色代表候选节点。且在遇到多个节点的时候左侧节点优先。作者梅鼠从没及格过，有亿点点抽象是十分正常的，望见谅。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
首先我们从根节点 000 开始搜索，根节点 000 的邻居节点有节点 1,5,101,5,101,5,10 。按照上述规则（即以左边的节点优先，往后不再提醒）,我们先搜索节点 111 ,同时把节点 000 设为已搜索 ，并将已经搜索过的节点 000 和正在搜索中的节点 111 加入dfs序列。最后将节点 111 的邻居设为候选:
根据深度优先搜索的规则，我们选择最新加入的候选节点 222 ，将节点 111 设为已搜索。同时将节点 222 的邻居节点 333 设为候选。将节点 111 加入dfs序列：
这时我们把最新加入的节点 333 进行搜索，将节点 222 设为已搜索，将节点 333 加入dfs序列：
此时我们可以看见节点 333 没有任何邻居节点，这代表到了节点 333 之后已经无路可走。这时我们就回到节点 222 。发现节点 222 也没有未搜索过的邻居节点，我们就再次回到前一个节点 111 。这时节点 111 有候补节点 444 。我们就搜索节点 444 并将其加入dfs序列:
我们发现此时的节点 444 也没有未探索过的节点，回到节点 111 。节点 111 也没有未探索过的节点，回到节点 000 。此时的节点 000 有候补节点 555 和 666 。优先选择节点 555 进行探索。将节点 555 加入dfs序列。将其未探索的邻居节点 666 和 999 作为后补:
此时先探索节点 666 ，将节点 666 加入dfs序列。同时将节点 555 设为已探索。将节点 666 未探索过的邻居节点 777 设为后补:
重复上述操作，将节点 777 加入dfs序列，将节点 888 设为后补；搜索节点 888 ，发现无路可走，回到节点 777 ，发现仍旧无路可走，回到节点 555 。这时发现还有候补节点 999 。将节点 999 探索并加入dfs序列:
此时节点 999 没有未探索的邻居节点了，多次回溯回到了顶点 000 。这时只剩下最后一个节点 101010 了。搜索节点 101010 ，加入dfs序列。
至此，该树的整个深度优先搜索便完成了。不难发现，每一次搜索都会选择最后加入的节点进行搜索，这与数据结构栈的特点（先进先出）十分相似。所以我们可以使用栈进行模拟。但是现在常用的实现方法是递归搭配回溯的方法，所以这里主要讲递归。
我们用一个较小的矩阵来逐步模拟代码操作。参考题目迷宫之判定。这里我们用橙色来当做深度优先搜索递归代码的搜过的路径。我们以 (0,0)(0 , 0)(0,0) 当做起点， (2,2)(2 , 2)(2,2)当做终点来模拟整个递归的过程。先给出dfs主题代码：
这里我们创建两个数组，一个用来储存迷宫地形，一个用来记录是否走过。
两个方向数组分别为x坐标和y坐标。这里要注意这两个数组的数据需要两两相反。比如x的前两个数据是0,-1 ，那么y数组的数据就是 -1,0。
先分析下代码：
首先我们dfs搜索一个我们就将其设为已走过。如果x和y到达了终点我们就直接return。接下来一个for循环描绘四个走法，只要满足条件“不越界，未走过，不是墙”，我们就在该点进行dfs递归。当遇到某个点无路可走时，我们就回到前边的点。这里需要注意，前一个点的for循环还没有结束。此时就会搜索新的路径。如果依旧无路可走则再回到上一个点……直到到达终点或dfs结束，判定为无路可走。
接下来把矩阵带入代码运行：
起始点在 (0,0)(0 , 0)(0,0)， 首先将 (0,0)(0 , 0)(0,0)设为已探索，而 根据for循环，首先是向下走，运气很好，满足条件，移动到 (0,1)(0 , 1)(0,1) ，递归dfs函数。
记录当前节点 (0,1)(0 , 1)(0,1) 为已探索，按照for循环向下，满足条件，移动到 (0,2)(0 , 2)(0,2) ，递归dfs：
接下来将该节点标记为已走过，然后for循环搜索，向下越界，不满足条件，向左，向右，向上，均不满足条件，这是无路可走，我们回溯到前一格 (0,1)(0 , 1)(0,1)，因为这时这里的for循环只循环了一次，且这里并没有记录 (0,2)(0 , 2)(0,2) 已经走过，所以不需要额外删除：
然后按照for，向左，向上均不满足条件，所以只能向右，这里的for循环结束了。我们递归dfs到 (1,1)(1 , 1)(1,1) ：
记录 (1,1)(1 , 1)(1,1)为已走过，然后for循环到第四次（向右），满足条件，递归dfs到 (2,1)(2 , 1)(2,1) ：
记录该位置为已走过，之后在第一次for（向下）循环满足条件，向下到达 (2,2)(2 , 2)(2,2) ，到达终点，改递归分支结束，将p改为true。但是注意一点，这里的深度优先搜索函数的递归并没有结束，他会尝试所有路径，但是并不会对结果产生什么影响，所以我们不需要特殊处理。如果非要处理的话可以加上
在dfs代码最开头。之后就是朴实无华的输出。完整代码：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
至此，整个深度优先搜索讲解已经结束（有彩蛋吗？↓），谢谢各位观看。
欢迎食用这个帖子
本帖只求加精，点不点赞无所谓，欢迎白嫖！\COLOR{WHITE} 本帖只求加精，点不点赞无所谓，欢迎白嫖！本帖只求加精，点不点赞无所谓，欢迎白嫖！
