回溯与图的深度优先遍历

Question

波波老师您好，学习了8.2回溯法和其代码，回想起了在您以前的课“学习算法思想”中讲过的图的深度优先遍历。对比了两者代码，也发现了一些相似之处。

请问是否可以将回溯理解为深度优先遍历呢？

多谢老师！

Answer 1

liuyubobobo 2019-03-28 13:39:32

赞！完全没问题。

更准确的说，深度优先遍历只是一种数据结构的遍历顺序。所有的数据结构都是存储数据的。存储了数据，就需要某种顺序的遍历。对于线性数据结构来说，这个顺序很简单。但关键是对于非线性数据结构来说，我们需要定义一种顺序。对于图这种数据结构来说，深度优先遍历就是对便利顺序的一种定义。

但是，对于深度优先遍历，具体的实现方式，其实就是使用了回溯法——先一条路走到底，走不动了就回头：）所以，回溯法是一种算法思想：）

继续加油！：）

• 提问者 软件工程小白菜 #1

  非常感谢！