在具有多个起始节点的有向无环图 (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)

但是，当图很大或者起始节点很多时，我的代码会变得很慢。众所周知，在一个DAGG(V,E)中寻找所有路径的DFS时间复杂度是O(V+E)。所以我的方法的时间复杂度是O(m(V+E))，其中m是起始节点的数量。在我的代码中，每个节点都被访问了 m 次，但我觉得仍然可以只访问每个节点一次，特别是考虑到 levels 并且我没有使用它。也许 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 中的每个 s 添加一个新的起始节点 S0 和边 (S0, s)。单个 DFS 完成后，您可以简单地从每个路径中删除 S0，留下原始图中的路径。

这可能会减少运行 dfs 多次创建的一些重复，但不会解决不可避免的事实，即您的运行时间与路径数量成正比待找到。

Answer 2

通过从最后一级的节点开始，您可以创建一个散列，这样您就可以先从叶子开始构建，然后逐级向上构建。我也猜测你在问题中的 dag 与你发布的数字不完全相同：

from collections import defaultdict
dag = [[5, 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]]


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]

结果：

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

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

Fastest way to find all paths in a directed acyclic graph (DAG) with multiple starting nodes?

python

algorithm

performance

time-complexity

graph-theory

编辑