Depth-first search and breadth first search

About search & traversal

For search, the vast majority of cases we deal with are called “search” so-called violence, or relatively simple search, that is to say, when you are in the search without any so-called smart in consideration, in many cases it do a thing to traverse all the nodes, then find the results you want.

Based on such a data structure, if the data structure itself has no characteristics, it is said to be a very ordinary tree or a very ordinary graph. So one thing we’re going to do is go through all the nodes. Ensure that each point is accessed once and only once to find the result.

So let’s just simplify the whole thing, and let’s just zoom in and search in this tree.

If we want to find a value that we want, what do we do in this tree? So the obvious way to do this is to start at the root and go to the left subtree, and then go down point by point, and then go to the right subtree, until we find our point, and that’s the way we do it.

Going back to our data structure definition, it only has left and right subtrees.


If we’re going to implement a traversal or a search like this, there’s no doubt that one of the things we want to ensure is that

  • Each node has to be accessed once
  • Each node is accessed only once
  • There is no limit to the order in which nodes can be accessed
    • Depth First: Depth First Search
    • Our lines First Search

This means that we are in search and we don’t want to make too many useless calls, otherwise our access efficiency will be very slow.

Of course, you can have other searches, and the other searches are not depth first or breadth first, but priority first. Of course you can define it any way you want, like middle first or something like that, but you just have to define it in a real world context. So you can think of it in general as depth first, breadth first, or priority first. In fact, priority search is more suitable for many business scenarios in reality, and such algorithm is generally called heuristic search, which is more applied in the field of deep learning. This is the reason why, for example, priority priority has been applied to various recommendation algorithms and advanced search algorithms in many cases, so that you can find the content that you are most interested in, and when you open Tiktok and Kuaishou every day, you can recommend the content that you are most interested in.

Depth-first Search (DFS)

Recursive writing

The way to write recursion is to start with the termination condition of the recursion, then process the current layer, and then go down.

  • So dealing with the current layer is like accessing the nodenodeAnd then put this nodenodeAdd to the accessed node;
  • So the termination condition is that if this node has been accessed before, it doesn’t matter;
  • So if you go down, you’re going to go to its children, which in the case of a binary tree is the left child and the right child, which in the case of a graph is the adjacent node of the tree, which in the case of a multi-fork tree is onechildrenAnd then put all thechildrenIf so, go through it once.
  1. Binary tree template
def dfs(node):
   if node in visited:
     # already visited
     return
   visited.add(node)
 # process current node  #... # logic here  dfs(node.left)  dfs(node.right) Copy the code
  1. Multi-fork tree template
visited = set(a)def dfs(node, visited):
    if node in visited: # terminator
     # already visited 
     return 
 visited.add(node)  # process current node here.  . for next_node in node.children():  if next_node not in visited:  dfs(next_node, visited) Copy the code

Non-recursive writing

def DFS(self, tree): 
 if tree.root is None: 
  return [] 
 visited, stack = [], [tree.root]
 while stack: 
 node = stack.pop()  visited.add(node)  process (node)  nodes = generate_related_nodes(node)  stack.push(nodes)  # other processing work  .Copy the code

Traversal sequence

If we look at depth-first search or depth-first traversal, there’s no doubt that the whole traversal order is that root node 1 always starts first, and it’s the same as going to that branch, but let’s just keep it simple and go from the far left, so it’s depth-first and it’s going to go to the end.


Using the multifork tree template we can either keep it in our head or draw a picture of it recursively, of the recursive state tree, and that’s the structure.

  • Like when it first came in, the message wasrootWords,rootI’m going to put it firstvisitedInside, representsrootHas beenvisit,visitedThen from theroot.childernfindnext_nodeAll of itnext_nodeIt’s never been visited, so it’s going to visit the leftmost node first, and notice that when it takes the leftmost node out first, it’s not invisitedInside, because apart fromrootNone of the other nodes have been destroyedvisitedYes, then if not, it goes straightdfs.next_nodeYou put the leftmost node in, and you put thevisitedPut it in, too.
  • One of the special things about recursive calls is that it doesn’t wait for the loop to run out, it just goes straight to the next level, which is the current dream where there’s a loop, but at the first level of the loop, I’m going to start drilling down into a new dream. So in this case,

Graph traversal order


Breadth First Search (BFS)

Breadth-first traversal of it doesn’t use recursion anymore, it doesn’t use a stack anymore, it uses something called a queue. You can think of it as a drop of water, dropping into position one, and then its ripples spread out layer by layer.


Both comparisons


BFS code template

# Python
def BFS(graph, start, end):
  visited = set(a) queue = [] 
 queue.append([start]) 
 while queue:  node = queue.pop()  visited.add(node)  process(node)  nodes = generate_related_nodes(node)  queue.push(nodes)  # other processing work  .Copy the code

Some pictures from the network, copyright to the original author, delete.Copy the code