python实现 多叉树 寻找最短路径
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了python实现 多叉树 寻找最短路径,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2046字,纯文字阅读大概需要3分钟。
内容图文
完全原创,能力有限,欢迎参考,未经允许,请勿转载 !
完全原创,能力有限,欢迎参考,未经允许,请勿转载 !
完全原创,能力有限,欢迎参考,未经允许,请勿转载 !
完全原创,能力有限,欢迎参考,未经允许,请勿转载 !
多叉树的最短路径:
思想:
传入start 和 end 两个 目标值
1 找到从根节点到目标节点的路径
2 从所在路径,寻找最近的根节点,
3 对根节点 拼接路径
1
import
copy
2
3
#
节点数据结构
4
class
Node(object):
5
#
初始化一个节点
6
def
__init__(self,value = None):
7 self.value = value # 节点值 8 self.child_list = [] # 子节点列表 9# 添加一个孩子节点10def add_child(self,node):
11 self.child_list.append(node)
121314# 初始化一颗测试二叉树15def init():
16‘‘‘17 初始化一颗测试二叉树:
18 A
19 B C D
20 EFG HIJ
21‘‘‘22 root = Node(‘A‘)
23 B = Node(‘B‘)
24 root.add_child(B)
25 root.add_child(Node(‘C‘))
26 D = Node(‘D‘)
27 root.add_child(D)
28 B.add_child(Node(‘E‘))
29 B.add_child(Node(‘F‘))
30 B.add_child(Node(‘G‘))
31 D.add_child(Node(‘H‘))
32 D.add_child(Node(‘I‘))
33 D.add_child(Node(‘J‘))
34return root
353637# 深度优先查找 返回从根节点到目标节点的路径38def deep_first_search(cur,val,path=[]):
39 path.append(cur.value) # 当前节点值添加路径列表40if cur.value == val: # 如果找到目标 返回路径列表41return path
4243if cur.child_list == []: # 如果没有孩子列表 就 返回 no 回溯标记44return‘no‘4546for node in cur.child_list: # 对孩子列表里的每个孩子 进行递归47 t_path = copy.deepcopy(path) # 深拷贝当前路径列表48 res = deep_first_search(node,val,t_path)
49if res == ‘no‘: # 如果返回no,说明找到头 没找到 利用临时路径继续找下一个孩子节点50continue51else :
52return res # 如果返回的不是no 说明 找到了路径5354return‘no‘# 如果所有孩子都没找到 则 回溯5556# 获取最短路径 传入两个节点值,返回结果57def get_shortest_path( start,end ):
58# 分别获取 从根节点 到start 和end 的路径列表,如果没有目标节点 就返回no59 path1 = deep_first_search(root, start, [])
60 path2 = deep_first_search(root, end, [])
61if path1 == ‘no‘or path2 == ‘no‘:
62return‘无穷大‘,‘无节点‘63# 对两个路径 从尾巴开始向头 找到最近的公共根节点,合并根节点64 len1,len2 = len(path1),len(path2)
65for i in range(len1-1,-1,-1):
66if path1[i] in path2:
67 index = path2.index(path1[i])
68 path2 = path2[index:]
69 path1 = path1[-1:i:-1]
70break71 res = path1+path2
72 length = len(res)
73 path = ‘->‘.join(res)
74return‘%s:%s‘%(length,path)
757677787980# 主函数、程序入口81if__name__ == ‘__main__‘:
82 root = init()
83 res = get_shortest_path(‘F‘,‘I‘)
84print(res)
原文:http://www.cnblogs.com/Lin-Yi/p/7780777.html
内容总结
以上是互联网集市为您收集整理的python实现 多叉树 寻找最短路径全部内容,希望文章能够帮你解决python实现 多叉树 寻找最短路径所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。