这是基于Alex Martelli的答案，但是应该可以。它取决于source_node.children产生可迭代对象的表达式，该可迭代对象将遍历的所有子元素source_node。它还依赖于==操作员有一种工作方式来比较两个节点以查看它们是否相同。使用is可能是一个更好的选择。显然，在您使用的库中，对所有子项进行迭代的语法为graph[source_node]，因此您需要相应地调整代码。
def allpaths(source_node, sink_node):
if source_node == sink_node: # Handle trivial case
return frozenset([(source_node,)])
else:
result = set()
for new_source in source_node.children:
paths = allpaths(new_source, sink_node, memo_dict)
for path in paths:
path = (source_node,) + path
result.add(path)
result = frozenset(result)
return result
我主要担心的是，这需要进行深度优先搜索，当从源到节点的路径有多个路径时，这将浪费所有精力，这些路径是所有源的孙，大孙等，但不一定是宿的父级。如果它记住给定源节点和宿节点的答案，则有可能避免额外的工作。
这是一个如何工作的示例：
def allpaths(source_node, sink_node, memo_dict = None):
if memo_dict is None:
# putting {}, or any other mutable object
# as the default argument is wrong
memo_dict = dict()
if source_node == sink_node: # Don't memoize trivial case
return frozenset([(source_node,)])
else:
pair = (source_node, sink_node)
if pair in memo_dict: # Is answer memoized already?
return memo_dict[pair]
else:
result = set()
for new_source in source_node.children:
paths = allpaths(new_source, sink_node, memo_dict)
for path in paths:
path = (source_node,) + path
result.add(path)
result = frozenset(result)
# Memoize answer
memo_dict[(source_node, sink_node)] = result
return result
这也使您可以在两次调用之间保存备忘录字典，因此，如果您需要计算多个源节点和宿节点的答案，则可以避免很多额外的工作。
602392714
清零编程群