首页 > 代码库 > 递归,回溯,DFS,BFS的理解和模板【摘】
递归,回溯,DFS,BFS的理解和模板【摘】
递归:就是出现这种情况的代码: (或者说是用到了栈)
解答树角度:在dfs遍历一棵解答树
优点:结构简洁
缺点:效率低,可能栈溢出
递归的一般结构:
1 void f() { 2 if(符合边界条件) { 3 /////// 4 return; 5 } 6 7 //某种形式的调用 8 f(); 9 }
回溯:递归的一种,或者说是通过递归这种代码结构来实现回溯这个目的。回溯法可以被认为是一个有过剪枝的DFS过程。
解答树角度:带回溯的dfs遍历一棵解答树
回溯的一般结构:
1 void dfs(int 当前状态) { 2 if(当前状态为边界状态) { 3 记录或输出 4 return; 5 } 6 for(i=0;i<n;i++) { //横向遍历解答树所有子节点 7 //扩展出一个子状态。 8 修改了全局变量 9 if(子状态满足约束条件) { 10 dfs(子状态) 11 } 12 恢复全局变量//回溯部分 13 } 14 }
BFS和DFS是相似。
BFS(显式用队列)
DFS(隐式用栈)(即递归)
当然,对于DFS,用递归可能会造成栈溢出,所以也可以更改为显示栈。
1 void bfs(node &head) { 2 //将(起始)首节点加入队列 3 q.push(head); 4 //标记首节点已经被访问 5 isvisited[head]=true; 6 7 while(!q.empty()){ 8 int temp=q.front(); 9 q.pop(); 10 //访问temp,并标记temp已被访问过,将temp的子相关节点加入队列 11 q.push(temp相关节点); 12 } 13 }
Reference:
http://blog.csdn.net/fightforyourdream/article/details/12866861
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。