本文實例講述了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']}找到一條路徑：
def find_path(graph, start, end, path=[]): path = path + [start] if start == end: return path if not graph.has_key(start): return None for node in graph[start]: if node not in path: newpath = find_path(graph, node, end, path) if newpath: return newpath return None
找到所有路徑：
def find_all_paths(graph, start, end, path=[]): path = path + [start] if start == end: return [path] if not graph.has_key(start): return [] paths = [] for node in graph[start]: if node not in path: newpaths = find_all_paths(graph, node, end, path) for newpath in newpaths: paths.append(newpath) return paths
找到最短路徑：
def find_shortest_path(graph, start, end, path=[]): path = path + [start] if start == end: return path if not graph.has_key(start): return None shortest = None for node in graph[start]: if node not in path: newpath = find_shortest_path(graph, node, end, path) if newpath: if not shortest or len(newpath) < len(shortest): shortest = newpath return shortest
希望本文所述對大家的Python程序設計有所幫助。
新聞熱點
疑難解答
圖片精選
