python - 在具有多个起始节点的有向无环图(DAG)中查找所有路径的最快方法？

Question

我正在尝试查找具有多个起始节点的有向无环图(DAG)中的所有路径。我已经有了由列表列表表示的 DAG，以及从开始到终止的每个级别的节点:

dag = [[4, 6, 7], [5, 6, 7], [4, 5, 6], [4, 5, 7],
       [], [], [], [], [1, 3], [1, 2], [0, 2, 3]]
levels = [[8, 9, 10], [0, 1, 2, 3], [4, 5, 6, 7]]

按级别着色的 DAG 示例如下所示:

由于我有 3 个起始节点[8, 9, 10]，所以我的第一个想法是执行 3 个 DFS。下面是我的代码:

def get_all_paths(dag, sources):

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

    all_paths = []
    for i in sources:
        paths = dfs(data=dag, path=[i], paths=[])
        all_paths += paths

    return all_paths

all_paths = get_all_paths(dag, sources=levels[0])
print(all_paths)

输出:

[[8, 1, 5], [8, 1, 6], [8, 1, 7], [8, 3, 4], [8, 3, 5], [8, 3, 7], 
 [9, 1, 5], [9, 1, 6], [9, 1, 7], [9, 2, 4], [9, 2, 5], [9, 2, 6], 
 [10, 0, 4], [10, 0, 6], [10, 0, 7], [10, 2, 4], [10, 2, 5], 
 [10, 2, 6], [10, 3, 4], [10, 3, 5], [10, 3, 7]]

%timeit 24.6 µs ± 577 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

但是，当图很大或者起始节点很多时，我的代码会变得非常慢。众所周知，在 DAG G(V,E) 中查找所有路径的 DFS 时间复杂度为 O(V+E)。所以我的方法的时间复杂度为O(m(V+E))，其中m是起始节点的数量。在我的代码中，每个节点都被访问m次，但我觉得仍然有可能只访问每个节点一次，特别是考虑到级别并且我没有利用它。也许 BFS 可以，但我不知道如何写。有什么建议吗？

编辑

以下是一些答案的基准测试

我根据@chepner的评论调整了我的BFS代码。

def get_all_paths(dag, sources):

    def dfs(data, path, paths=None):
        if paths is None:
            paths = []
        prev = path[-1]
        if data[prev]:
            for val in data[prev]:
                new_path = path + [val]
                paths = dfs(data, new_path, paths)
        else:
            paths.append(path[1:])

        return paths

    dag.append(sources)
    
    return dfs(data=dag, path=[len(dag)-1], paths=[])

%timeit get_all_paths(dag, sources=levels[0])

输出:

9.73 µs ± 112 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

测试@aminrd的答案:

from collections import defaultdict

def aminrd(dag, levels):
    paths = defaultdict(list)
    levels_reversed = levels[::-1]

    for node in levels_reversed[0]:
        paths[node] = [[node]]

    for lvl in levels_reversed[1:]:
        for src in lvl:
            for dst in dag[src-1]:
                paths[src] += [[src] + p for p in paths[dst]]

    result = []
    for lvl_0 in levels[0]:
        result += paths[lvl_0]
        
%timeit aminrd(dag, levels)

输出

10.7 µs ± 164 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

Answer 1

在单个增强图中查找路径。如果您的起始节点集是 S，请为每个 s< 添加一个新的起始节点 S0 和边 (S0, s)/code> 在 S 中。单个 DFS 完成后，您只需从每条路径中删除 S0 即可，留下原始图中的路径。

这可能会减少多次运行 dfs 所产生的一些重复，但无法解决运行时间与要找到的路径数量成正比这一不可避免的事实。