【算法】BFS、DFS、递归

时间:2020-9-5 作者:admin

递归

递归的三个条件

  • 子问题实现相同的功能
  • 结束条件:空值、边界等
  • 递归关系式:满足某个条件,递归前进,不满足,递归返回

核心代码

/**
 * 斐波那契数列
 * @param {number} n
 * @return {number}
 */
var fib = function (n) {
  if ([0, 1].includes(n)) return n; // 结束条件
  return fib(n - 1) + fib(n - 2); //递归关系式,子问题实现相同的功能
};

相关题

剑指 Offer 10- I. 斐波那契数列

DFS

定义:深度优先搜索算法(DFS)是一种用于遍历或搜索树或图的算法。这个算法会尽可能深的搜索树的分支。

核心代码

function DFS(board, i, j) {
  if (满足成功条件) return true;
  if (失败条件,控制、边界等) return false;
  const temp = board[i][j];
  board[i][j] = true; // 设置被访问标识
  res = dfs(board, i + 1, j + 1) || dfs(board, i - 1, j - 1) // 递归关系式
  board[i][j] = temp; // 回退,重置源起点被访问标识
  return res;
}

相关题

剑指 Offer 12. 矩阵中的路径

BFS

定义:广度优先算法(Breadth-First-Search),简称BFS,是一种图形搜索演算法。简单的说,BFS是从根节点开始,沿着树的宽度遍历树的节点,如果发现目标,则演算终止。

核心代码

/**
 * 广度优先搜索
 * @param Vs 起点
 * @param Vd 终点
 */
function BFS(Vs, Vd) {
  const queue = [Vs]; // 声明队列
  visit(Vs) = true; // 标记被访问过的项
  while (queue.length) {
    const node = queue.shift(); // 取出队列中第一项

    // 到达终点
    if (node === Vd) {
      return true;
    }
    const nextNode = compute(node); // nextNode是通过node的某种运算可以访问到
    if (isValid(nextNode) && !visit(nextNode)) {
      queue.push(nextNode); // 将nextNode纳入队列中
      visit(nextNode) = true;
    }
  }
  return false
}

相关题

剑指 Offer 32 – II. 从上到下打印二叉树 II

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。