DFS深度优先搜索算法详解

DFS深度优先搜索

基本思想

• 深度优先搜索算法：是一种用于遍历或搜索树或者图的算法。 沿着树的深度遍历树的节点 尽可能神的搜索树的分支。当节点v的所在边都已被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达到的所有结点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复上述过程，整个进程反复进行指导所有节点都被访问为止。属于盲目搜索。简单点说DFS可以看作一个执着的人，优先往下走。

算法思想

• DFS使用数据结构是stack栈，空间复杂度为O(n); DFS中最重要的算法思想是回溯和剪枝。另外DFS不具有最短性
• 回溯是一种优先搜索法，又称为 试探法，以达到目的。但当探索到某一布时发现原先选择并不优或达不到目标，就是退回一布重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”
• 剪枝，就是减小搜索树规模，今早排除搜索书中不必要的分支一种手段。形象地看就好像剪掉了搜索树的枝条，故称为 “剪枝”

模板

• // 强调写递归函数的技巧
  // 一般来说dfs的参数是那些在递归的过程需要变化的参数，
  // 比如说坐标x，y（这个与你树父节点与子节点
  1
  2