搜索

 

BFS和DFS

  1. 搜索算法的要素：状态维护、状态转移、访问操作，这三个方面在抽象层面上相互独立，但有时候依赖共同的底层对象

  2. BFS中，状态用队列维护，DFS中，状态用栈维护。有趣的是，在BFS中需要显式地维护一个队列，但DFS中不需要，因为如果将状态作为递归函数的参数，则状态自动成为一个栈。更有趣的是，由于栈的特性，如果我们能够得到由当前状态推导出上一个状态的方法，就没有必要真的维护一个栈，而是通过计算来虚拟一个栈。因此，维护DFS的状态有了三种可能的实现方法：显式地维护栈；借助递归函数；虚拟一个栈

  3. 然而，为什么在BFS中不能虚拟一个队列，而DFS中可行？因为在DFS中，下一个状态（待入栈元素）必然由当前的状态（栈顶元素）正向推导出来，反过来，当处理完栈顶元素（元素出栈）开始回溯，下一个要处理的（下一个出栈的元素）恰巧是将其推导出的状态，因此如果要反向推导，我们只是期待正向推导过程可逆，这是相对平凡的。然而，在BFS中，当处理完队首元素（元素出队），下一个要处理的（下一个出队的元素）并非是将其推导出的状态，所以期待一个反向推导是荒谬的