有向无环图中从源到接收器的所有路径的列表

有向无环图中从源到接收器的所有路径的列表

这是基于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

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