Leetcode depth first and breadth first traversal

​​

Depth-first traversal And Breadth first traversal , Do not brush algorithm problems do not know these two concepts , There are also some such scenarios in business at ordinary times , But when I meet these two words, I feel tall

What is depth first traversal

Depth-first traversal When we search for a Trees When the branches of , Meet a node , We will first traverse its child nodes until the last root node , Finally, traverse the sibling nodes , Look for its child nodes from the sibling child nodes , Until the final result is found , Then the end .

First of all, from the above paragraph , We know that the traversal object is a tree , A tree is a data structure , We are js You can simulate it in , Let's draw a picture

The above is a basic tree structure , stay js We can use the following structure to describe

const root = {
  name: '1',
  children: [
    {
      name: '2-1',
      children: [
        {
            name: '3-1',
            children: [
              {
                  name: '4-2',
                  children: null
              },
              {
                name: '4-1',
                children: null
              }
            ]
        },
        {
            name: '3-2',
            children: null
        }
      ]
    },
    {
      name: '2-2',
      children: null
    }
  ]
}

Copy

We understand the above sentence , Depth-first traversal , When I search for a branch of a tree , Encounter a node , I will search her child nodes , Until the search is over , Then go to search brother nodes , Let's use the code to verify

//  Depth-first traversal 
const deepDFS = (root, nodeList = []) => {
  if (root) {
      nodeList.push(root.name);
      //  recursive root.children, look for root Child nodes of 
      root.children && root.children.forEach(v => deepDFS(v, nodeList))
  }
  return nodeList;
}
const result = deepDFS(root, []);
console.log(JSON.stringify(deepDFS(root, []), null, 2)))
/**
[
  "1",
  "2-1",
  "3-1",
  "4-2",
  "4-1",
  "3-2",
  "2-2"
]
*/

Copy

From the result, we found that the branch from the beginning , Start with the first branch , Find a node and keep finding the deepest node , Then find the parent sibling node , Finally, find the child nodes from the brother nodes of the root child nodes .

Breadth first traversal

When searching tree branches , Start at the root node , When accessing child nodes , First, traverse to find the sibling node , Then find the corresponding child node

Let's use a graph to restore the search process

The corresponding code is as follows

//  Breadth first traversal 
const deepBFS = (root, nodeList = []) => {
  const queue = [root];
  //  Loop to determine whether the length of the queue is greater than 0
  while(queue.length > 0) {
      //  Take out the node added by the queue 
      const p = queue.shift();
      nodeList.push(p.name);
      //  Depending on whether the node contains children, If there are child nodes, they are added to the queue 
      p.children && p.children.forEach(v => queue.push(v))
  }
  return nodeList;
}
console.time('BFS-start')
const result = deepBFS(root, []);
console.log(JSON.stringify(result, null, 2));
console.timeEnd('BFS-start')
/*
[
  "1",
  "2-1",
  "2-2",
  "3-1",
  "3-2",
  "4-2",
  "4-1"
]
*/

Copy

Breadth first traversal The main idea is to put a tree in a queue , We cycle through the queue , Determine whether the length of the queue is greater than 0, We keep cycling the queue ,shift Out of queue operation , Then determine the node children, loop children, Then add the child nodes to the queue , Once the queue length is 0, Then the loop is terminated .

Let's test which is more efficient in search time

// BFS  Breadth first traversal 
console.time('BFS-start')
const result = deepBFS(root, []);
console.log(JSON.stringify(result, null, 2));
console.timeEnd('BFS-start');

Copy

// DFS  Depth-first traversal 
console.time('DFS-start');
console.log(JSON.stringify(deepDFS(root, []), null, 2));
console.timeEnd('DFS-start')

Copy

Finally found

The time efficiency of breadth first traversal is obviously higher than that of depth first traversal , Breadth first traversal records the position of each node in a queue , So it will occupy more memory , Because depth first traversal is a recursive query from the root node to the child nodes , When the child nodes are queried , Search from the sibling nodes of the root node , So it's time consuming , Breadth first traversal is more efficient .

summary

1、 understand Depth-first traversal And Breadth first traversal What is it?

Depth-first traversal From top to bottom , When we search a tree , We start from the root , Encounter a node , Just query its child nodes first , If the child node has child nodes, continue to search until there are no child nodes , Then start from the sibling nodes of the root child node and look for the nodes in turn . and Breadth first traversal Traversal starts from the root node , Look for child nodes , First traverse to find sibling nodes , From top to bottom , Search by level .

2、 With concrete code Depth-first traversal And Breadth first traversal

3、 Depth first traversal is more time-consuming than breadth first traversal

4、 Sample code of this article code example[1]

Reference material

[1]code example: https://github.com/maicFir/lessonNote/blob/master/leetcode/leetcode-deepBFS.js