BFS和DFS的基本思想

最近碰到BFS和DFS的编程题比较多，所以想整理一下相关算法的基本思想，以便以后使用。

1.DFS（深度优先搜索）

深度优先直白讲是一种一条道走到黑，撞了南墙再回头的算法。所以其整个搜索空间可以表示为一个多叉树。其可以用递归和栈来分别实现。基本思想如下：

1.1 递归实现DFS

function DFS(root){

递归出口：搜索到最底部叶节点

递归部分：循环当前可到达的所有子节点：

                       循环内部：处理该子节点，调用DFS(childrenroot)，复原该子节点。}

1.2 栈实现DFS

使用栈保存未被检测的结点，结点按照深度优先的次序被访问并依次被压入栈中，并以相反的次序出栈进行新的检测。

function DFS(root){

初始：root入栈；

while(栈非空){

出栈一个结点，处理该节点；

把该节点可到达的节点都依次压入栈中；

}

}

2.BFS（广度优先搜索）

广度优先的搜索空间也可以表示为一个多叉树。其实现树结构的逐层遍历。BFS可以用队列来实现。基本思想如下：

2.1 栈实现DFS

使用栈保存未被检测的结点，结点按照深度优先的次序被访问并依次被压入栈中，并以相反的次序出栈进行新的检测。

function DFS(root){

初始：root入队列。

while(队列非空){

出队一个结点，处理该节点；

把该节点可到达的节点都依次压入栈中；

}

}