简谈DFS

所谓DFS就是“不撞南墙不回头”的一种搜索。其时间复杂度为O(V+E)。

能算出从起点到终点的全部路径，在算法执行的过程中需要一个visit[v_i]数组来维护每个结点的访问情况，这样就能避免重复访问。但需要注意的是对于同一起点到同一终点有多条路径的时候，每次递归回溯时要重置visit[v_i]的状态。并且可以使用vector来存储每次经过的节点。两个同类型的vector数组可以直接比较、直接赋值的，所以DFS也就可以简单的求出最佳路径。

DFS在递归过程中的还存在一个难点就是结束递归开始回溯的条件设置。这里往往在到达终点的基础还要加上题目所限定的条件。这有一个技巧就是先一个 if(begin == end && 题目限定的条件){到达终点后要处理的逻辑} if(begin == end){return;} 正所谓把逻辑处理和返回分离避免混乱（因为会存在有时需要执行逻辑有时不需执行逻辑的情况）。像PAT“周游世界”的题目中就存在这样的情况：第一次找到了能到达终点的路径此时还不需要去做任何比较就可以直接返回，但第二次、第三次、。。。都需要去执行逻辑比较判断每条路径经过的站数和换乘站次数。这里站数的统计很简单，每次递归执行就把站数加一。注意在dfs函数的参数中要想维护一个参数一定要加&（引用）。

接下来在说一个DFS中提升效率的方法：剪枝。以PAT“球队食物链”链为例，此题答案要求要满足排列{ a₁ a₂ ...a_N }在字典序上小于排列{ b₁ b₂ ... b_N }，当且仅当存在整数K（1 <= K <= N），满足：a_K < b_K且对于任意小于K的正整数i，a_i=b_i。所以1号节点一定是答案集中的第一个元素，并且答案集的最后一个元素必须和第一个元素在邻接表所表示的图上是连通的。所以我们在每次递归前都检验一下接下来还没访问过点是否能到达1号节点，若不能的话就不进行之后的递归。

最后总结一下，dfs是图论最基本的一个遍历策略，适用于求路径数目，对于非层次遍历的题目都可考虑用次方法解决。但有时候会因时间复杂度的限制不得不放弃此方法。

 

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有