This is the ninth day of my participation in the First Challenge 2022. For details: First Challenge 2022.

Breadth-first search

Breadth first Search, English name Breadth first search, abbreviated as BFS.

Why is there breadth-first search

To improve search efficiency

For example, Chapter 6 of Graphic Algorithms introduces breadth-first search with some examples:

  • Write a chess AI that calculates the minimum number of moves to win.
  • Write a spell checker that calculates the minimum number of places you can edit to change a misspelled word into a correct word.
  • Use your network to find the closest doctor.

To abstract these problems into data structures and algorithms is to find the elements we want in a large set, be it a set of states, a tree, or a graph.

For example, here is an example of finding a node from a tree:

If someone came to this node, looked at it, looked at the whole tree, they would know where this node was.

But the computer is not, the computer can only a node a node to see, that is, to mop up again.

So how do you sweep all the nodes when you only sweep once?

Hence the breadth-first algorithm, which starts at the root of the tree and sweeps down layer by layer, as shown below:

Looking for a relationship

To take another example from a graphical algorithm, suppose you run a mango farm and need to find a seller of mangoes to sell them to.

Look for your relationships. First, create a list of friends and check each one in turn to see if he or she is a mango seller.

If you don’t have mango sellers among your friends, you’ll have to look them up among your friends.

That way, you look not only among friends, but among friends of friends, even among friends of friends, until you find the mango seller you need.

The process of finding a mango seller, let’s abstract it:

“Is there A seller of mangoes in your relationship?” is essentially starting at node A, is there A path to node B

To extend this, if I ask: Which mango seller is closest to you?

This is the shortest path problem, which can also be found using breadth-first search to see how many layers of friends it takes to find a mango seller.

“Which mango seller is closest to you” is essentially the shortest path from node A to node B.

Implementation of breadth-first search

To implement breadth-first search, you need to use a queue. The elements to be retrieved are queued, and if they are not found, the elements are removed from the queue.

Take finding a mango seller as an example. First, the friend relationship is abstracted into the following data structure, assuming that friend 6 is the mango seller:

Const friedsRelations = {name: 'I ', friedsList: [{name:' frislist ', friedsList: [{name: 'frislist'}, {name: Friends' 5 '}}, {name: '2' friend, friedsList: [{name: 6 ', 'friends isTarget: true}]}, {name: friends' 3'}]}Copy the code

Then use the breadth-first algorithm to find the mango seller as follows:

Function breadthFirstSearch (root) {const queue = [] // Define a queue. Unshift (root) // add the first node to the queue while (queue.length) { Const top = queue.shift(); // If (top.istarget) {// If (top.istarget) {// If (top.istarget); Direct return to return the top. The name} const friedsList = top. FriedsList | | [] / / if can't find a friend, you need to go looking for a friend of a friend. for (let i = 0, len = friedsList.length; i < len; I ++) {queue. Push (friedsList[I]) {queue. Push (friedsList[I])Copy the code

Run the test:

Console. log(' Mango Dealer :>> ', breadthFirstSearch(Fried Relations))Copy the code

Follow the previous thinking to write code, so easy to implement a breadth-first search, graphical algorithm YYDS!

Time complexity: O(n), because each node enters and exits the queue once.

Space complexity: O(n), because there are no more than n elements in the queue.

The breadth-first search algorithm traverses the Dom tree

A classic interview question, almost identical to the one above about finding a mango seller.

function breadthFirstSearch (root) {
  const res = []
  if (root) {
    const queue = []
    queue.unshift(root)
    while (queue.length) {
      const top = queue.shift()
      res.push(top)
      const children = top.children
      for (let i = 0; i < children.length; i++) {
        queue.push(children[i])
      }
    }
  }
  return res
}
Copy the code

Open Taobao and put the code in:

Traversal successful!

Sequential traversal of binary trees

const levelOrder = function (root) { const queue = [] queue.unshift(root) while (queue.length) { const top = queue.shift() res.push(top.val) if (top.left) { queue.push(top.left) } if (top.right) { queue.push(top.right) } } return  res }Copy the code

It’s the same routine, isn’t it?!

Leetcode breadth First search experience

leetcode 102

You are given the root node of the binary tree, root, and return the sequential traversal of its node value. (That is, layer by layer, all nodes are accessed from left to right).

This problem is actually a binary tree sequence traversal, but the return format is a bit troublesome, is a two-dimensional array.

const levelOrder = function (root) { const queue = [] const res = [] queue.unshift(root) while (queue.length) { res.push([]) for (let i = 0, len = queue.length; i < len; i++) { const top = queue.shift() res[res.length - 1].push(top.val) if (top.left) { queue.push(top.left) } if (top.right)  { queue.push(top.right) } } } return res }Copy the code

There are some slight changes in the code, but it’s still a routine.

summary

If someone asks you, what is breadth-first search?

Ask him how you usually find relationships among friends.

The shortest path problem was found through several layers of friends.

Of course, implementing breadth-first search through code requires the help of queues, and a little understanding of the logic of queue entry and queue exit, but trust me, you’ll get the hang of it when you write your own code.

Here is a very detailed explanation of BFS by way of GIF that I saw. You can read it further.

13 BFS LeetCode examples: | usage scenarios: sequence traversal, the shortest path problem

Besides, algorithms are not metaphysical, and two weeks ago, I was a bona fide algorithm beginner. In the past two weeks, I gradually got familiar with some algorithms by understanding the cause and effect of the birth of data structure or algorithm and combining with coding practice.

You can too!

Previous algorithms related articles

Forest Algorithms – Introduction to Linked Lists (JS)

Write a brief introduction to the front-end development algorithm

Forest Algorithms – Tree Knowledge (JS)

Divide-and-conquer and Quicksort (JS) for beginners

Write a hash table introduction for front-end development