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