枚举有向非循环图中的所有路径

Question

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

Answer 1

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

您可以查看代码http://pastebin.com/p6ciRJCU

Answer 2

这是一个修改过的DFS的简短python示例来实现这个目的:

data = {1 : [2,3],   # Directed acyclic graph adjacency list
        2 : [3],
        3 : [4,5],
        4 : [5]}

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

输入:

print dfs(data = data, path = [1], paths = []) # adjacency list; a list containing the node to start from; and initialize an empty list for all possible paths

输出:

[[1, 2, 3, 4, 5], 
[1, 2, 3, 5], 
[1, 3, 4, 5], 
[1, 3, 5]]