标签：bfs
深搜与广搜
搜索其实挺常见的，但是与搜索引擎并不一样，并不是再庞大的数据中找到匹配的（更类似的是字符串匹配），dfs与bfs更多是指在所有可能的结果中找到可用的结果和对应的路径（后者往往dfs比bfs更加自然，因为dfs常见的实现方式是递归，而bfs基本都是靠队列实现，不过下文我将使用另一种方式指出二者的共通性） dfs，即深度优先搜索，重点在于深，即一条路走到死，不行再换。这也是为什么常见递归写法的原因，附上简单的伪代码示例: 不难看出，dfs只需要记录return 1;时的选择就可以做到记录下找到结果对应的路径对的原因。而且dfs的优势在于完整遍历每一种情况，同时思维更符合人脑（方便调试） 至于bfs，广度优先搜索，则是另一种思维，先把每种路都看一遍，保证视野足够的广，正因如此，不太适合递归一类的方式，常见的是使用队列实现: bfs的优势主要在于能够找到最短路，比如Dijkstra就是典型的bfs。 但是不妨发散一下思维，递归的本质是让调用栈决定了谁先谁后的问题，所以两者本质上是高度相同的，完全可以尝试:...