回溯

Question

老师，深度优先遍历这个算法和回溯算法有什么区别啊？还有我感觉floodfill就是深度优先遍历啊，我感觉这两个算法运行机制和回溯特别像呀。

Answer 1

liuyubobobo 2020-02-29 02:08:43

深度优先遍历就是回溯法。只不过深度优先遍历更常用在某种特定的数据结构的遍历上，比如树的遍历或者图的遍历，而回溯法更常用于更加广义的搜索策略上。

但我认为，这两种方法在名词使用上不用做特别的区分：）

继续加油！：）

• 讲武德的年轻人 #1

  请教bobo老师，leetcode有些word ***问题，譬如word break，word ladder，word pattern，word search。这类问题就算是回溯问题吧？图论这门课会涉及这类问题吗？谢谢

• liuyubobobo 回复 讲武德的年轻人 #2

  不一定。问题的题目和问题的类型没有关系。也可能是字符传的问题，甚至可能是排序问题，需要具体问题具体分析。你说的很多问题可以使用 trie 解决，trie 是一种处理字符串的结构，在我的体系课程中有做介绍。