When it comes to enumerating all cases and so on, think of DFS and BFS! It’s like seeing a right triangle and thinking of the Pythagorean theorem, nine times out of ten!

TL; DR

To list all situations, two ideas are often used:

  • DFS (Deep First Search) : Don’t turn back until you hit the south wall. If you hit the south wall, turn back and start again. General and binary tree first order traversal is closely related to the implementation of recursion, the essence is the stack structure, last in first out
  • BFS (Breath First Search – breadth First Search) : move forward with radar scanning, remember new roads as you see them and abandon the ones you have taken. In general, it is closely related to the sequence traversal of the binary tree, implemented by queue, fifO

DFS

DFS: Following the principle of “don’t hit the south wall and don’t look back”, if you are in a maze, as long as you don’t hit the wall, you will never choose another path, but keep digging deep into the current path. Such a search method with “depth” as the first factor of progress is called “depth-first search”.

The core idea of depth-first search is to try to exhaust all the complete paths.

  • A-b-c, south wall of C, back to B
  • A-b-d, D south wall, back to B
  • A-b-e-f, south wall of F, fall back to E
  • A-b-e-g-h, H south wall, back to G
  • A-b-e-g-i, clear exit

The depth-first search process can be transformed into a series of loading and unloading operations, often using recursion to simulate the loading and unloading logic.

DFS is closely related: sequential traversal of binary trees

{
  val:'A'.left: {val:'B'.left: {val:'C'}}}Copy the code

Sequential traversal:

// The input of all traversal functions is the root object of the tree
function preorder(root) {
  // Recursive boundary, root is empty
  if(! root) {return;
  }

  // Outputs the value of the node currently traversed
  console.log("The node value of the current traversal is:", root.val);

  // Recursively traverse the left subtree
  preorder(root.left);
  // Recursively traverse the right subtree
  preorder(root.right);
}
Copy the code

In this recursive function, the recursion is used to traverse the left subtree and the right subtree (exploring different paths respectively), and the recursive boundary returns when it recognizes that the node is empty (hitting the south wall).

You can think of recursion as the process by which we choose our path, and recursive boundaries as dead ends. The sequential traversal of binary tree is the recursive realization of depth-first search.

Why is depth-first search essentially a stack?

There are two ways to understand this:

  • First, the nature of recursion is to call functions, and calling functions uses the system stack.

  • Second, DFS as an idea doesn’t always use recursion, and sometimes you need to write the stack structure by hand

BFS

  • A-b goes to A and sees B
  • B, C, D, E go to B, abandon A, see CDE
  • C-d-e goes to C, abandons B, doesn’t see much
  • D-e goes to D, abandons D, doesn’t see much
  • E-F-G goes to E, abandons D, and sees FG
  • F-g goes to F, abandons E, doesn’t see much
  • G-h-i goes to G, abandons F, sees HI
  • H-i goes to H, abandons G, doesn’t see much
  • Exit I-go to I, abandon H, see exit
  • Exit to exit, abandon I, problem solved
  • Empty out of the exit, problem solved

In the process of hierarchical traversal, there are two rules:

  • Each time a coordinate is accessed, it is no longer needed in subsequent traversals and can be discarded.
  • The coordinates directly reachable by standing at certain coordinates need to be recorded because they will be used in subsequent traversals.

The sequence of discarding the visited coordinates and recording the newly observed coordinates undoubtedly conforms to the principle of “first in, first out”. Therefore, the implementation process of the whole BFS algorithm is closely related to the queue.

Pseudocode represents the above logic:

function BFS(Entrance coordinates) {
    // Initialize the queue
    const queue = []
    // Enter the queue firstQueue.push (entry coordinates)// The queue is not empty, indicating incomplete traversal
    while(queue.length) {
        // Fetch the header element
        const top = queue[0]
        // Here is some logic related to top, such as recording its corresponding information, checking its properties, etcAccess to the top// Note that you can also use the for loop, depending on the topic
        forQueue. Push (top can reach directly)}// The visit is complete. Remove the team leader element from the team
        queue.shift()
    }
}
Copy the code

BFS is closely related: sequential traversal of binary trees

The sequential traversal of binary trees is actually the idea of BFS:

const root = {
  val: "A".left: {
    val: "B".left: {
      val: "D",},right: {
      val: "E",}},right: {
    val: "C".right: {
      val: "F",}}};function BFS(root) {
  let queue = [];
  // the root node joins the queue first
  queue.push(root);
  // The queue is not empty, indicating incomplete traversal
  while (queue.length) {
    // Where the queue is constantly updated
    const top = queue[0];
    / / the output value
    console.log(top.val);

    // Queue reachable points
    top.left && queue.push(top.left);
    top.right && queue.push(top.right);

    // When the visit is complete, the header element exits the queue
    queue.shift();
  }
}

BFS(root);
Copy the code

reference

  • The front-end algorithm and data structure of xiuyan