最近碰到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(队列非空){
出队一个结点，处理该节点；
把该节点可到达的节点都依次压入栈中；
}
}
网友评论