在 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)。