讨论/算法和数据结构/如何理解回溯和递归以及DFS/
如何理解回溯和递归以及DFS

本人菜鸡一枚,刚刚开始刷leetcode,为了考研之前刷过pat,因为好多题都是和leetcode很像,所以就来刷leetcode了
但是本菜鸡并不是很理解这三种算法,其实本质上就是递归,但不是很会写,就能理解和写树和图的递归就行了,求大佬指点!!!

展开讨论
共 1 个讨论

递归

递归算法是一种直接或者间接调用自身函数或方法的算法。在写递归算法时,需要注意的使递归的结束条件。如果结束条件错误,会过早跳出递归调用或者出现死循环。

DFS

深度优先搜索(DFS)算法,即是一种搜索算法。他的特点是在搜索时会面临多个选择,当选择某一个情况后仍然会面临多个选择。那么,他每一次都选择一个情况时,会继续沿着这个“方向”搜索下去,直到遇到边界无法在搜索时,结束当前分支路径的搜索。接着,进行其他路径的搜索。以这种方式持续下去,直到将所有的路径搜索完毕。经典的案例,比如对于BST(二叉搜索树)的先序遍历、中序遍历和后序遍历。
形象点说,就是在搜索时呈现了一种“不撞南墙不回头”的效果。对于搜索路径会有很多,DFS在搜索时会依次的搜索每一个路径,只有某一个路径触达边界条件时,才会搜索下一个路径。
与之对应的算法即广度优先搜索(BFS),在搜索时会齐头并进的搜索所有分支。
通常来说,DFS用于查找一些可行的解,BFS用于查找最短路径。

回溯

回溯算法更多的体现在“回溯”这个概念上。这个概念,在我理解是DFS的一个特性。以上述BST的先序遍历而言,当搜索到某一个分支边界时,他会回退到最近的一个节点,继续进行搜索下一个分支直到边界。以这种方式,搜索下去。

针对DFS和回溯可以看下图

此外,我写了一篇文章,希望对你有所帮助:一只青蛙跳出来的分治法、回溯法与动态规划

1