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程序设计有所帮助。