这是基于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这也使您可以在两次调用之间保存备忘录字典，因此，如果您需要计算多个源节点和宿节点的答案，则可以避免很多额外的工作。
