Re: [問題] 找graph中兩點的所有可能路徑
既然 python 對 recursion 不怎麼友善，
那在考慮 graph algorithm 時除了用 DFS 衝遞迴之外，
也可以試試用 BFS。
========8<========= CUT HERE ========8<=========
# simple full-connected graph for node 0, 1, 2, 3, 4
Graph = [ [ 1, 2, 3, 4],
[ 0, 2, 3, 4],
[ 0, 1, 3, 4],
[ 0, 1, 2, 4],
[ 0, 1, 2, 3] ]
def find_all_path(graph, start_node, end_node):
def extend_path(path):
return [ p+[node] for node in graph[ path[-1] ] if not node in path ]
paths = [ [start_node] ]
result = []
while paths:
result.extend([p for p in paths if p[-1] == end_node])
new_paths = []
[ new_paths.extend(extend_path(p)) for p in paths]
paths = new_paths
return result
all_paths = find_all_path(Graph, 0, 4)
print "Total %d path(s)" % len(all_paths)
print all_paths
========8<========= CUT HERE ========8<=========
--
... 我一定是太閒了..
--
凡祈求的，就得著；尋找的，就尋見；叩門的，就給他開門。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.23.102
討論串 (同標題文章)
完整討論串 (本文為第 2 之 3 篇)：
Python 近期熱門文章
PTT數位生活區 即時熱門文章
