递归与回溯，DFS及BFS的算法

本文主要是介绍递归与回溯，DFS及BFS的算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

转载自：https://blog.csdn.net/qq_21158525/article/details/79459378

递归：就是出现这种情况的代码： （或者说是用到了栈）

解答树角度：在dfs遍历一棵解答树

优点：结构简洁

缺点：效率低，可能栈溢出

递归的一般结构：

void f()  
{  if(符合边界条件)  {  ///////  return;  }  //某种形式的调用  f();  
} 

回溯：递归的一种，或者说是通过递归这种代码结构来实现回溯这个目的。回溯法可以被认为是一个有过剪枝的DFS过程。

解答树角度：带回溯的dfs遍历一棵解答树

回溯的一般结构：

void dfs(int 当前状态)  {  if(当前状态为边界状态)  {  记录或输出  return;  }  for(i=0;i<n;i++)       //横向遍历解答树所有子节点  {  //扩展出一个子状态。  修改了全局变量  if(子状态满足约束条件)  {  dfs(子状态)  }  恢复全局变量//回溯部分  }  }

经典例题，比如解数独问题。

BFS与 DFS

BFS的占用的是队列的空间，DFS 占用的是栈的空间（因为递归）。BFS和DFS的空间复杂度恰好相反。对链状图，BFS最好（队列中最多只有1个元素），DFS最差（所有节点都在根节点的递归内）。对起点与其他所有点相邻的图，DFS最好（递归深度为1），BFS最差（队列中放满了所有与起点相邻的图）。
BFS一般结构：

queue<type> q;q.push(初始状态);while (!q.empty()){type t = q.front() ;q.pop();遍历 t 的各个Next状态  next{ if (next is legal)q.push(next); 计数或维护等; } }

但是BFS的状态数一多，需要的空间就会较大。
DFS 一般结构与回溯相似

DFS（顶点） {处理当前顶点，记录为已访问遍历与当前顶点相邻的所有未访问顶点{标记更改;DFS( 下一子状态);恢复更改;}}

这篇关于递归与回溯，DFS及BFS的算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---