DFS、BFS和Backtracking模板

Bertha 。 2022-07-15 03:43 286阅读 0赞

搜索问题的解法

  1. DFS（深度优先搜索）
  2. BFS（广度优先搜索）
  3. backtracking（回溯）

DFS模板

  1. void dfs(...) 
  2. {
  3.     // 结束递归的条件
  4.     if (...) {
  5.         ..... // 把“当前结果” 加入 “结果集容器” 中
  6.         return;
  7.     }
  9.     // 继续递归，里面可能有回溯，也可能没有
  10.     if (...) {
  12.         ... // 在容器中保存当前数据
  13.         dfs() 
  14.         ... // 在容器中删除上面保存的数据（注：这种情况下就称为回溯，很明显它是dfs的一个步骤）
  15.     }
  16. }

难点

  1. 寻找dfs结束条件
  2. 继续dfs的条件

题目

78. Subsets
93. Restore IP Addresses

BFS模板

模板1

  1. void bfs(...)
  2. {
  3.     queue q;
  4.     q.push(startRoot);
  5.     while (!q.empty()) {
  6.         // 按照节点处理
  7.         curNode = q.front();
  8.         q.pop();
  10.         if (...) {
  11.             // 处理curNode,并把curNode的相邻Nodes加入队列
  12.         }
  13.     }
  15. }

模板2

  1. void bfs(...)
  2. {
  3.     queue q;
  4.     q.push(startRoot);
  5.     while (!q.empty()) {
  6.         // 按照层次处理
  7.         size = q.size();
  8.         for (i = 0; i < size; i++) {
  9.             curNode = q.front();
  10.             q.pop();
  12.             if (... ) {
  13.                 // 处理curNode,并把curNode的相邻Nodes加入队列
  14.             }
  15.         }
  16.     }
  18. }

题目

199. Binary Tree Right Side View

参考

Restore IP Addresses

发表评论

表情：
评论列表 （有 0 条评论，286人围观）

还没有评论，来说两句吧...

相关阅读

    相关 BackTrack5R3之连网

    打开BT5后，用ifconfig 命令查看网络接口信息，发现没有分配IP： ![Center][] 原因，主机，也就是物理机，停止了虚拟机的下面服务： ![Cen

    Bertha 。Bertha 。/ 0 赞/ 316 阅读