Python笔记 之 使用Python实现简单的图结构及寻径算法

本文主要介绍使用Python自带的数据结构实现简单的图及寻径算法。

构建图

有一张图，描述如下
节点A可以直接抵达节点B，E，G代价分别是1,4,6
节点B可以直接抵达节点C代价为1
节点C可以直接抵达节点D，E代价分别为1,2
节点D可以直接抵达节点F代价为2
节点E可以直接抵达节点C，F，G代价分别为1,1,2
节点F无直接可抵达节点
节点G可以直接抵达节点A代价为6
可以通过Python的数据结构可以表示为：

Graph={'A':[('B',1),('E',4),('G',6)],'B':[('C',1)],'C':[('D',1),('E',2)],'D':[('F',2)],'E':[('C',1),('F',1),('G',2)],'F':[],'G':[('A',6)]}

寻径算法

#查找节点1到节点2的所有路径及代价

def search(start,goal,graph):'''从图中查询路径及代价:param start: 起始节点:param goal: 目标节点:param graph: 图:return: 返回所有路径及代价'''paths=[]# 使用迭代遍历路径generate(([start],0),goal,paths,graph)# 按代价排序paths.sort(key=lambda x:x[-1])return paths

#迭代查询

def generate(path,goal,paths,graph):'''迭代计算路径及代价:param path: 途径路径:param goal: 目的节点:param paths: 已有路径:param graph: 图:return: 返回一条路径'''# 获取当前节点state=path[0][-1]# 获取当前代价costs=path[1]# 找到目标，添加路径if state==goal:paths.append(path)else:# 遍历图for arc in graph[state[0]]:# 如果节点不包含在当前路径则添加if arc[0] not in path[0]:# 迭代generate((path[0]+[arc[0]],costs+arc[1]),goal,paths,graph)

测试结果

#测试路径

print('ED',searcher('E','D',Graph))
for x in ['AG','GF','BA','DA']:print(x,searcher(x[0],x[1],Graph))

#运行结果

ED [(['E', 'C', 'D'], 2), (['E', 'G', 'A', 'B', 'C', 'D'], 11)]
AG [(['A', 'B', 'C', 'E', 'G'], 6), (['A', 'E', 'G'], 6), (['A', 'G'], 6)]
GF [(['G', 'A', 'B', 'C', 'D', 'F'], 11), (['G', 'A', 'B', 'C', 'E', 'F'], 11), (['G', 'A', 'E', 'F'], 11), (['G', 'A', 'E', 'C', 'D', 'F'], 14)]
BA [(['B', 'C', 'E', 'G', 'A'], 11)]
DA []

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！