[Algorithm] BFS, DFS, recursion

recursive

Three conditions for recursion

• Subproblems implement the same functionality
• End conditions: null value, boundary, etc
• Recursive relation: meet a condition, recursive forward, not meet, recursive return

The core code

/** * Fibonacci sequence *@param {number} n
 * @return {number}* /
var fib = function (n) {
  if ([0.1].includes(n)) return n; // End condition
  return fib(n - 1) + fib(n - 2); // Recursive relations, subproblems achieve the same function
};
Copy the code

Related to the topic

Offer 10-i. Fibonacci sequence

DFS

Definition: A depth-first search algorithm (DFS) is an algorithm used to traverse or search a tree or graph. The algorithm searches the branches of the tree as deep as possible.

The core code

function DFS(board, i, j) {
  if(Success conditions are met)return true;
  if(Failure conditions, controls, boundaries, etc.)return false;
  const temp = board[i][j];
  board[i][j] = true; // Set the access identifier
  res = dfs(board, i + 1, j + 1) || dfs(board, i - 1, j - 1) // this is a recursive relationship
  board[i][j] = temp; // Rollback to reset the access identifier of the source starting point
  return res;
}
Copy the code

Related to the topic

Refer to the path in the Offer 12 matrix

BFS

Definition: Breadth First Search algorithm, BFS for short, is a graphic Search algorithm. Simply put, BFS starts at the root node, traverses the tree’s nodes along the width of the tree, and terminates the calculus if a target is found.

The core code

/** * breadth first search *@param Vs starting point *@param Vd end * /
function BFS(Vs, Vd) {
  const queue = [Vs]; // Declare a queue
  visit(Vs) = true; // Marks the items that have been accessed
  while (queue.length) {
    const node = queue.shift(); // Fetch the first item in the queue

    // get to the end
    if (node === Vd) {
      return true;
    }
    const nextNode = compute(node); NextNode is accessible through some node operation
    if(isValid(nextNode) && ! visit(nextNode)) { queue.push(nextNode);// Queue nextNode
      visit(nextNode) = true; }}return false
}
Copy the code

Related to the topic

Finger Offer 32-ii. Print binary tree II from top to bottom