preface

Two days ago, I saw an interview question of Ali about DFS and BFS algorithm. I searched a lot on the Internet, but didn’t have an exact answer. Today we’re going to work on this problem

Title: Implementing a depth-first search algorithm (Requirement: no recursion)

Var tree = {name: 'cn ', children: [{name:' cn ', children: [{name: 'cn ', children: [{name:' cn ', children: [{name: 'cn ', children: [{name:' cn ', children:] '0521',}}, {name: ', haidian district,}, {name: "changping district,},],}, {name: 'in zhejiang province, the children: [{name: hangzhou, code: '0571',}, {name: "jiaxing",}, {name: 'shaoxing,}, {name: ningbo,},],},],}; Var node = DFS/BFS (tree, 'BFS '); console.log(node); {name: 'xining ', code: '0521'}Copy the code

So how do we do the search without recursion?

If we do it recursively, it’s very simple: paste code

Function DFS (tree, name){if(tree.name === name){return tree; } if(! tree.name && ! tree.children){ return null } for(let i = 0; i < tree.children.length; i++){ var result = dfs(tree.children[i], name) if(result){ return result; } } return null }Copy the code

answer

Scheme 1: Depth-first traversal

Based on the fifo principle, we go from right to left, facilitating by depth (finding the termination loop break).

DFS (tree, name){var stack = [], result = {}; stack.push(tree) while(stack.length ! = 0){ var item = stack.pop(); if(item.name == name){ result = item; break } let children = item.children; if(children){ for(let i = children.length - 1; i >= 0; i--){ stack.push(children[i]) } } } return result }Copy the code

Plan 2: breadth-first traversal

First in, first out (FIFO), we go from top to bottom, layer by layer (find the termination loop break)

Function BFS (tree,name){var queue = [],result = {}; queue.unshift(tree); while(queue.length! =0){ var item = queue.shift(); if(item.name == name){ result = item; break } var children=item.children; if(children){ for(let i = 0; i < children.length; i++){ queue.push(children[i]) } } } return result }Copy the code

Depth-first algorithm occupies less memory but is slower, while breadth-first algorithm occupies more memory but is faster, which can get the optimal solution faster when distance is proportional to depth.

Conclusion:

Deep search optimalLack ofpoint

  1. Can find all the solutions
  2. Search one subtree first, then another, so it has the advantage of requiring relatively little memory compared to extensive search
  3. You go through it multiple times, looking for all possible paths, and then you cancel it.
  4. It’s inefficient at great depths

Advantages and disadvantages of extensive search

  1. It is particularly effective for solving the shortest or least problem, and the search depth is small

  2. Each node is accessed only once, and the node is always accessed in the shortest path, so the second path is guaranteed to be no shorter than the first

  3. High memory consumption (need to open a large number of array units to store state)

My name is Steven. If you feel like it, please like it in the upper left corner. If you have any questions, please comment or send a private message