厦门专业网站建设建站,公需科目在哪个网站做,推广的公司,装修设计网站哪个平台最好本文实例讲述了Python实现的多叉树寻找最短路径算法。分享给大家供大家参考#xff0c;具体如下#xff1a;多叉树的最短路径#xff1a;思想#xff1a;传入start 和 end 两个 目标值1 找到从根节点到目标节点的路径2 从所在路径#xff0c;寻找最近的公共祖先节点#…本文实例讲述了Python实现的多叉树寻找最短路径算法。分享给大家供大家参考具体如下多叉树的最短路径思想传入start 和 end 两个 目标值1 找到从根节点到目标节点的路径2 从所在路径寻找最近的公共祖先节点3 对最近公共祖先根节点 拼接路径Python代码# -*- coding:utf-8 -*-import copy#节点数据结构class Node(object):# 初始化一个节点def __init__(self,value None):self.value value # 节点值self.child_list [] # 子节点列表# 添加一个孩子节点def add_child(self,node):self.child_list.append(node)# 初始化一颗测试二叉树def init():初始化一颗测试二叉树:AB C DEFG HIJroot 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# 深度优先查找 返回从根节点到目标节点的路径def deep_first_search(cur,val,path[]):path.append(cur.value) # 当前节点值添加路径列表if cur.value val: # 如果找到目标 返回路径列表return pathif cur.child_list []: # 如果没有孩子列表 就 返回 no 回溯标记return nofor node in cur.child_list: # 对孩子列表里的每个孩子 进行递归t_path copy.deepcopy(path) # 深拷贝当前路径列表res deep_first_search(node,val,t_path)if res no: # 如果返回no说明找到头 没找到 利用临时路径继续找下一个孩子节点continueelse :return res # 如果返回的不是no 说明 找到了路径return no # 如果所有孩子都没找到 则 回溯# 获取最短路径 传入两个节点值返回结果def get_shortest_path( start,end ):# 分别获取 从根节点 到start 和end 的路径列表如果没有目标节点 就返回nopath1 deep_first_search(root, start, [])path2 deep_first_search(root, end, [])if path1 no or path2 no:return 无穷大,无节点# 对两个路径 从尾巴开始向头 找到最近的公共根节点合并根节点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]breakres path1path2length len(res)path -.join(res)return %s:%s%(length,path)# 主函数、程序入口if __name__ __main__:root init()res get_shortest_path(F,I)print(res)运行结果5:F-B-A-D-I希望本文所述对大家Python程序设计有所帮助。
