algorithm - 在 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!

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

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

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) .