首页 > 代码库 > 递归,回溯,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