python数据结构之图的实现方法
本文实例讲述了python数据结构之图的实现方法。分享给大家供大家参考。具体如下：
下面简要的介绍下：
比如有这么一张图：
A->B
A->C
B->C
B->D
C->D
D->C
E->F
F->C
可以用字典和列表来构建
graph={'A':['B','C'],
'B':['C','D'],
'C':['D'],
'D':['C'],
'E':['F'],
'F':['C']}
找到一条路径：
deffind_path(graph,start,end,path=[]): path=path+[start] ifstart==end: returnpath ifnotgraph.has_key(start): returnNone fornodeingraph[start]: ifnodenotinpath: newpath=find_path(graph,node,end,path) ifnewpath:returnnewpath returnNone
找到所有路径：
deffind_all_paths(graph,start,end,path=[]): path=path+[start] ifstart==end: return[path] ifnotgraph.has_key(start): return[] paths=[] fornodeingraph[start]: ifnodenotinpath: newpaths=find_all_paths(graph,node,end,path) fornewpathinnewpaths: paths.append(newpath) returnpaths
找到最短路径：
deffind_shortest_path(graph,start,end,path=[]): path=path+[start] ifstart==end: returnpath ifnotgraph.has_key(start): returnNone shortest=None fornodeingraph[start]: ifnodenotinpath: newpath=find_shortest_path(graph,node,end,path) ifnewpath: ifnotshortestorlen(newpath)<len(shortest): shortest=newpath returnshortest
希望本文所述对大家的Python程序设计有所帮助。
热门推荐
6 保研的祝福语简短
10 年轻20岁祝福语简短
11 朋友结婚祝福语信息简短
12 女孩婚礼贺卡祝福语简短
13 30段点歌简短祝福语
14 虎年春节祝福语图文简短
15 写给后妈祝福语大全简短
16 简短回复生日祝福语
17 校长送毕业祝福语简短
18 毕业立体贺卡祝福语简短