枚举有向无环图中的所有路径

Question

是否有任何标准算法可以在有向无环图中找到所有可能的路径。如果没有，我如何在BFS / Dijkstra /任何其他算法中进行更改以枚举DAG中的所有路径

Answer 1

我的想法是扩展所有的路径，当没有候选路径时，从插入第一条边开始，然后通过扩展路径集合中的每条边在头部、尾部继续，或者当考虑的边产生分歧(冲突路径)时，分割一条路径。

这是一种基于稳定性思想的迭代方法：每次都考虑所有边缘，如果在一个回合中没有动作可做，那么转弯是稳定的，没有更多的工作要做。这种方法需要注意的一件事是不要太快地分叉路径：第一个转弯是准备转弯，因此分叉阶段仅在下一个转弯处处于活动状态。我正在评估交替前叉和延长阶段是否更好（我的意思是：更正确），并将stable_turn视为稳定的几圈

代码如下：

https://gist . github . com/daniele Cr/6 Abd 8 ad 48461347238 ad 1 caf 3714 fe6a

(抱歉，这是javascript，不太容易阅读，但我需要这种语言的版本)

Answer 2

下面是一个简短的python示例，通过修改DFS来实现这一点:

data = {1 : [2,3],   # Directed acyclic graph adjacency list
        2 : [3],
        3 : [4,5],
        4 : [5],
        6 : [7,8]}   # These nodes are disconnected from the rest of the graph

def dfs(data, path, paths):
    datum = path[-1]              
    if datum in data:
        for val in data[datum]:
            new_path = path + [val]
            paths = dfs(data, new_path, paths)
    else:
        paths += [path]
    return paths

def enumerate_paths(graph):
    nodes = list(graph.keys())
    all_paths = []
    for node in nodes:
        node_paths = dfs(graph, [node], [])
        all_paths += node_paths
    return all_paths

输入：

enumerate_paths(data)

输出:

[[1, 2, 3, 4, 5], [1, 2, 3, 5], [1, 3, 4, 5], [1, 3, 5], [2, 3, 4, 5], [2, 3, 5], [3, 4, 5], [3, 5], [4, 5], [6, 7], [6, 8]]

Answer 3

在指数中查找任何图形中的所有可能路径。它可以通过使用回溯来解决。对于DAG，我们可以使用深度优先搜索（DFS）来完成。在 DFS 代码中，从任何节点开始，转到极端死胡同路径，并使用某个数组或列表记下在该路径中访问的所有节点。一旦找到死胡同，就会打印包含已访问节点的数组，并弹出最后存储的节点，并从（n-1）个节点的另一个路径开始。如果 （n-1） 个节点的所有路径都已用尽，请从列表中弹出该节点，并从 （n-2） 节点开始。这样做，直到你到达所有的死胡同，到达第一个节点。所有打印的路径都是给定 DAG 中的路径。

你可以检查代码http://pastebin.com/p6ciRJCU