在 DAG 中寻找给定长度 N 的路径

Question

给你一个有向无环图，它是一棵有根树（所以所有的边都向下，从根开始的两条路径不能相交）。您知道图中每条边的长度。我正在寻找一种算法来检查在线性时间内是否存在一些 长度为 N 的路径。

我正在考虑将图形转换为拓扑顺序，然后遍历每个顶点，同时跟踪从给定顶点开始的所有路径。我不确定这是否是正确的解决方案。我可以就如何做得更好获得任何帮助吗？

Answer 1

由于你的树是有向的，不能有先上后下的路径，下面是树节点数的线性解。

如果我们首先考虑一个更简单的问题，我觉得这更容易解释：给定一个数组 a，找出是否有一个子数组的总和为 N.

我们将为此使用前缀和：

s[0] = a[0]
s[i > 0] = s[i - 1] + a[i]

那么想法是检查，对于每个 0 <= i < a.len，如果 s[j < i] 包含一个值 p 使得 s[i] - p == N。重写这个，我们得到，p == s[i] - N.

一个天真的实现是：

s[0] = a[0]
if a[0] == N:
    found it!
for i = 1 to a.len:
    s[i] = s[i-1] + a[i]
    for j = 0 to i:
        if s[j] == s[i] - N:
            found it!

但是，我们可以用字典替换嵌套的 for 循环以获得 O(a.len log a.len) / O(a.len) 解决方案。

我们需要为树实现相同的解决方案，在深度优先搜索期间构建该字典，但在从递归调用返回时注意从中删除元素：

DFS(node, sums_dict, current_sum):

    if current_sum - N in sums_dict:
        found it!
    else:
        sums_dict.add(current_sum)
        for c in node.children: 
            DFS(c, sums_dict, current_sum + c.edge_len)
        sums_dict.remove(current_sum)

初次通话：DFS(root, <empty>, 0).

时间复杂度：O(T * D)，其中T是树中的节点数，D是我们字典的复杂度：O(log T)或O(1).

在 DAG 中寻找给定长度 N 的路径

Finding a path of given length N in a DAG

algorithm

graph-theory

path

directed-acyclic-graphs

graph-algorithm