Алгоритм линейного времени для количества различных путей из каждой вершины в ориентированном ациклическом графе

Я работаю над следующим прошлым бумажным вопросом для модуля алгоритмов:

Пусть G = (V, E) — простой ориентированный ациклический граф (DAG).
Для пары вершин v, u в V мы говорим, что v достижима из u, если существует (направленный) путь из u в v в G.
(Мы предполагаем, что каждая вершина достижима из самой себя.)
Для любой вершины v в V пусть R(v) будет числом достижимости вершины v, то есть числом вершин u в V, которые достижимы из v.
Разработайте алгоритм, который для данного DAG, G = (V, E), вычисляет значения R(v) для всех вершин v в V.
Предоставьте анализ вашего алгоритма (т. е. анализ корректности и времени выполнения).
(Оптимально нужно попытаться разработать алгоритм, работающий за время O(n + m).)

Итак, пока у меня следующие мысли:

Может оказаться полезным следующий алгоритм нахождения топологического вида DAG:

TopologicalSort(G)
  1. Run DFS on G and compute a DFS-numbering, N // A DFS-numbering is a numbering (starting from 1) of the vertices of G, representing the point at which the DFS-call on a given vertex v finishes.
  2. Let the topological sort be the function a(v) = n - N[v] + 1 // n is the number of nodes in G and N[v] is the DFS-number of v.

Вторая моя мысль заключается в том, что динамическое программирование тоже может быть полезным подходом.
Однако в настоящее время я не знаю, как объединить эти две идеи в решение.

Буду признателен за любые подсказки!


directed-acyclic-graphs algorithm dynamic-programming topological-sort
person Caleb Owusu-Yianoma    schedule 23.05.2016    source источник

Ответы (2)


arrow_upward
2
arrow_downward

EDIT: К сожалению, приведенный ниже подход в целом неверен. Он может несколько раз подсчитывать узлы, к которым можно добраться по нескольким путям.

Приведенные ниже идеи действительны, если DAG является полидеревом, так как это гарантирует, что существует не более одного путь между любыми двумя узлами.

Вы можете использовать следующие шаги:

  • найти все узлы с нулевой степенью вхождения (т. е. без входящих ребер).

Это можно сделать в O(n + m), например, перебирая все ребра и отмечая те узлы, которые являются концом любого ребра. Узлы с нулевой степенью входа - это те, которые не были отмечены.

  • Запустите DFS с каждого узла с нулевой степенью входа.

После завершения вызова DFS для узла мы хотим вычислить для этого узла информацию о его достижимости.

Чтобы добиться этого, нам нужно добавить достижимость преемников этого узла. Некоторые из этих значений могли быть уже вычислены (если преемник уже посещался DFS), поэтому это решение для динамического программирования.

Следующий псевдокод описывает код DFS:

function DFS(node) {
    visited[node] = true;
    reachability[node] = 1;

    for each successor of node {
        if (!visited[successor]) {
            DFS(successor);
        }
        reachability[node] += reachability[successor];
    }
}

После вызова этого для всех узлов с нулевой степенью вхождения массив reachability будет содержать достижимость для всех узлов в графе.

Общая сложность O(n + m).

person qwertyman    schedule 23.05.2016
comment
Шаги полезны; однако я думаю, что в псевдокоде для DFS может быть ошибка. Я применил его к произвольной DAG, которую я нарисовал, и все записи достижимости остались со значением 0. - person Caleb Owusu-Yianoma; 23.05.2016
comment
Действительно, достижимость должна была быть инициализирована с 1 в DFS (каждый узел может достичь себя) — сейчас отредактировано. Существует также еще одна проблема, которая делает алгоритм недействительным (некоторые узлы могут учитываться несколько раз). Я думаю о том, как справиться с этим. - person qwertyman; 23.05.2016

arrow_upward
0
arrow_downward

Я бы предложил использовать подход Поиск в ширину.

Для каждого узла добавьте все узлы, подключенные к очереди. В дополнение к этому поддерживайте отдельный массив для вычисления достижимости.

Например, если А->В, то

1.) Mark A as traversed
2.) B is added to the queue
3.) arr[B]+=1

Таким образом, мы можем получить R(v) для всех вершин за время O(|V| + |E|) через arr[].

person attaboy182    schedule 23.05.2016