Algorithm Cheatsheet (continuously updated)

Photo by Michael Dziedzic on Unsplash

Purpose:

This is a continuous updated post to summarize typical algorithms in Python3 templates. My expectation is to train my muscle memory to these Python3 algorithm implemetations so that whenever I need them in problem solving, I don’t need to think too much (just apply those algorithm implemetation templates) and make little (if not zero) mistakes.

Python3 Templates for Typical Algorithms

1. Typical DFS Python3 template

#params are normally those will change in each round of dfs
#for example, a position that something inside dfs will start with
#I'd suggest a more meaningful name to use than "dfs"
#like rollFrom(postion)
visited = []
def dfs(current_node):
  #processing current_node to generate more leads(nodes)
  nodes = processing of current_node
  visited.append(current_node)
  for node in nodes:
    if node not in visited:
      dfs(params_turning_from_branch_info)
dfs(start_node) #kick start dfs

Above template will check each path one by one, but sometimes I will need to abort the checking if an answer is found in some path. In that case, the template can be slightly modified to be:

#params are normally those will change in each round of dfs
#for example, a position that something inside dfs will start with
#I'd suggest a more meaningful name to use than "dfs"
#like rollFrom(postion)
visited = []
def dfs(current_node):
  #processing current_node to generate more leads(nodes)
  nodes = processing of current_node
  visited.append(current_node)
  #during above processing, some required criteria are met
  if(criteria are met):
    return True
  for node in nodes:
    if node not in visited:
      if dfs(node): 
        return True
  return False
return dfs(start_node) #kick start dfs

2. Typical BFS Python3 template
Similarly to DFS, I may use BFS to find ALL possible answers (which means I need to navigate all nodes). Also, I may just stop by the first answer, which below template applies to.

Also, below template is not using recursive calls.

visited = []
toVisit = [start_node]
while(len(toVisit) > 0):
  toVisitInNextLayer = []
  for current_node in toVisit:  
    #processing node to generate more leads(nodes)
    nodes = processing of current_node
    visited.append(current_node)
  
    #during above processing, some required criteria are met
    if(criteria are met):
      return True
    for node in nodes:
      if node not in visited:
        toVisitInNextLayer.append(node)
   
  toVisit = toVisitInNextLayer
return False

Extended Reading

1. Python3 cheatsheet:

Python3 Cheatsheet (continuously updated)