Xus | 算法之深度优先算法(DFS)
Xus
关注
时光似箭，日月如梭。转眼间我一年都没有发推文了😰。这一年由于种种原因没把所得的趣事给分享出来，归咎起来终究还是自己太懒啦~
knowledge
深度优先算法
Depth First Search
深度优先搜索属于图算法的一种，是一个针对图和树的遍历算法，英文缩写为DFS即Depth First Search。
深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。一般用堆数据结构来辅助实现DFS算法。
其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。
对于上面的树而言，DFS方法首先从根节点1开始，其搜索节点顺序是1,2,3,4,5,6,7,8（假定左分枝和右分枝中优先选择左分枝）。
从stack中访问栈顶的点。
找出与此点邻接的且尚未遍历的点，进行标记，然后放入stack中，依次进行。
如果此点没有尚未遍历的邻接点，则将此点从stack中弹出，再按照步骤（3）依次进行。
直到遍历完整个树，stack里的元素都将弹出，最后栈为空，DFS遍历完成。
不懂吗？哪方面不大懂？
从 s 到 t , . 意味着可以走， * 意味着不能走，如果能走，输出路径，如果不能走，输出no。
我们来分析.....
打住！打住！
现在我们自己先思考几分钟...
大家想一想，我们看到地图后会如何走呢？
是不是每走一位，都会考虑下一个位置的上、下、左、右是否可以通行(达到通行条件：无障碍物、没有超出边界、没有走过)。
代入到程序中，我们写的程序并不能那么智能，但计算机计算飞快。
程序中，到达每一个新的位置后都会尝试上下左右是否允许通行，若上下左右四个新位置都不能通行，则会回退(回溯)，回退到上一个位置，上一个位置只是走了某个分支，可能还存在其他分支可以走，那就接着其他分支走下去，尝试往前位置的另一个分支走下去，一直走走走。。。直到找到”T”点为止。
为了保存地图数据，我们使用一个二维数组进行地图的保存：
S_row 为输入的行数，S_column为输入的列数
我们可以先写一个找到终点的代码：
Print_Maps() 为打印地图的函数，我们现在不急着实现
然后整体写一个函数：
形参row，column对应的是需要检查的行号以及列号
在函数的一开始，我们判断地图中：
MazeArray[row][column] 是否为终点
难点：往四个方向走 ↓ → ↑ ←
此时我们有了下一个位置的坐标(row_,column_)，我们的任务就是判断这个新的位置是否可以通行：
当我们所有条件都成立后，进入到下一位置（核心）：
整体代码：
全排列
例如n = 3，则输出(1 2 3)、(1 3 2)、(2 1 3)、(2 3 1)、(3 1 2)、(3 2 1) 六种情况。
为了帮大家快速理解全排列
我画了个图例
（欠缺画画天赋😭）
整理一下我们的思路
我们可以用DFS算法去解出此题，如同上面迷宫题目一般。
我们“每把牌放置到一个新的盒子可以看作为上题中每往下探测一步”
先放置了 牌1 到 盒子1
此时 盒子 全部被放满，一种组合完毕，输出当前组合(1 2 3)。
随后把 盒子3 (最后放的位置) 的牌收回，试着放其他牌，发现没有其他牌(分支)了，再往前回收 盒子2 的 牌2 ，现在，手上有 牌2 、 牌3 两张牌 牌3 还未放置，则可以把 牌3 放置在 盒子2 的位置，之后 盒子3 就可以放置 牌2 ，输出组合(1 3 2)，后面以此类推。。。
上代码~
好了
我又又又水了一篇推文😆
笔记记了一大堆
但是还没有编辑好发粗来😤
我追求质量而不是效率
好吧，咱也没质量
🙏祝我插本成功上岸🙏