Python实现的多叉树寻找最短路径算法示例
本文实例讲述了Python实现的多叉树寻找最短路径算法。分享给大家供大家参考,具体如下:
多叉树的最短路径:
思想:
传入start和end两个目标值
1找到从根节点到目标节点的路径
2从所在路径,寻找最近的公共祖先节点,
3对最近公共祖先根节点拼接路径
Python代码:
#-*-coding:utf-8-*- importcopy #节点数据结构 classNode(object): #初始化一个节点 def__init__(self,value=None): self.value=value#节点值 self.child_list=[]#子节点列表 #添加一个孩子节点 defadd_child(self,node): self.child_list.append(node) #初始化一颗测试二叉树 definit(): ''' 初始化一颗测试二叉树: A BCD EFGHIJ ''' 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')) returnroot #深度优先查找返回从根节点到目标节点的路径 defdeep_first_search(cur,val,path=[]): path.append(cur.value)#当前节点值添加路径列表 ifcur.value==val:#如果找到目标返回路径列表 returnpath ifcur.child_list==[]:#如果没有孩子列表就返回no回溯标记 return'no' fornodeincur.child_list:#对孩子列表里的每个孩子进行递归 t_path=copy.deepcopy(path)#深拷贝当前路径列表 res=deep_first_search(node,val,t_path) ifres=='no':#如果返回no,说明找到头没找到利用临时路径继续找下一个孩子节点 continue else: returnres#如果返回的不是no说明找到了路径 return'no'#如果所有孩子都没找到则回溯 #获取最短路径传入两个节点值,返回结果 defget_shortest_path(start,end): #分别获取从根节点到start和end的路径列表,如果没有目标节点就返回no path1=deep_first_search(root,start,[]) path2=deep_first_search(root,end,[]) ifpath1=='no'orpath2=='no': return'无穷大','无节点' #对两个路径从尾巴开始向头找到最近的公共根节点,合并根节点 len1,len2=len(path1),len(path2) foriinrange(len1-1,-1,-1): ifpath1[i]inpath2: 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) #主函数、程序入口 if__name__=='__main__': root=init() res=get_shortest_path('F','I') print(res)
运行结果:
5:F->B->A->D->I
更多关于Python相关内容感兴趣的读者可查看本站专题:《Python数据结构与算法教程》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》
希望本文所述对大家Python程序设计有所帮助。