作者yjc1 (..........)
看板Python
标题Re: [问题] 找graph中两点的所有可能路径
时间Thu Dec 10 00:09:12 2009
既然 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