An example of Python multi tree searching shortest path algorithm

An example of Python is presented in this paper. To share for your reference, the details are as follows:

The shortest path of multi-tree:

Thought:

The start and end target values are passed in
Find the path from the root node to the target node
2. Find the nearest common ancestor node from its path,
3 Splicing paths for the nearest common ancestor root node

Python code:

# -*- coding:utf-8 -*-
import copy
# Node data structure 
class Node(object):
  #  Initialize the 1 A node 
  def __init__(self,value = None):
    self.value = value #  Node values 
    self.child_list = []  #  List of child nodes 
  #  add 1 Child node 
  def add_child(self,node):
    self.child_list.append(node)
#  Initialize the 1 A test 2 tree 
def init():
  '''
   Initialize the 1 A test 2 tree :
      A
    B  C  D
   EFG    HIJ
  '''
  root = Node('A')
  B = Node('B')
  root.add_child(B)
  root.add_child(Node('C'))
  D = Node('D')
  root.add_child(D)
  B.add_child(Node('E'))
  B.add_child(Node('F'))
  B.add_child(Node('G'))
  D.add_child(Node('H'))
  D.add_child(Node('I'))
  D.add_child(Node('J'))
  return root
#  Depth-first search   Returns the path from the root node to the target node 
def deep_first_search(cur,val,path=[]):
  path.append(cur.value) #  The current node value adds a path list 
  if cur.value == val:  #  If you find the target   Return path list 
    return path
  if cur.child_list == []:  #  If there is no list of children   it   return  no  Back in the tag 
    return 'no'
  for node in cur.child_list: #  For each of the children in the list   recursively 
    t_path = copy.deepcopy(path)  #  Deep copy of the current path list 
    res = deep_first_search(node,val,t_path)
    if res == 'no': #  If the return no , which means find the head   Did not find   Use the temporary path to continue 1 Child node 
      continue
    else :
      return res #  If the return is not no  instructions   Find the path 
  return 'no' #  If all the children are not found   the   back 
#  Get the shortest path   Pass in two node values and return the result 
def get_shortest_path( start,end ):
  #  Respectively to obtain   From the root node   to start  and end  Path list if there is no destination node   It returns no
  path1 = deep_first_search(root, start, [])
  path2 = deep_first_search(root, end, [])
  if path1 == 'no' or path2 == 'no':
    return ' infinity ',' No node '
  #  Two paths   Start at the tail and head   Locate the nearest common root node and merge the root node 
  len1,len2 = len(path1),len(path2)
  for i in range(len1-1,-1,-1):
    if path1[i] in path2:
      index = path2.index(path1[i])
      path2 = path2[index:]
      path1 = path1[-1:i:-1]
      break
  res = path1+path2
  length = len(res)
  path = '->'.join(res)
  return '%s:%s'%(length,path)
#  Main function, program entry 
if __name__ == '__main__':
  root = init()
  res = get_shortest_path('F','I')
  print(res)

Operation results:

5:F- > B- > A- > D- > I

For more information about Python, please refer to Python Data Structure and Algorithm Tutorial, Python Coding Skills Summary, Python Function Usage Skills Summary, Python String Manipulation Skills Summary and Python Introductory and Advanced Classic Tutorial.

I hope this article has been helpful in Python programming.