Нахождение пути заданной длины N в DAG

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) решения.

Нам нужно реализовать то же решение для дерева, собирая этот словарь при первом глубинном поиске, но стараясь удалить из него элементы при возврате из рекурсивных вызовов:

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