Нахождение достижимых вершин в ориентированном графе

Question

Я хотел бы спросить о следующей проблеме:

Учитывая ориентированный граф (не обязательно DAG), для каждой вершины v вычислите число достижимых вершин из v.

Таким образом, используя подход грубой силы (n раз DFS), мы можем получить ответ за O (n ^ 2) временной сложности.Есть ли способ рассчитать это быстрее?Я могу определенно сделать DAG из данного графика, используя SCC.Я пытался использовать ранее вычисленные значения, чтобы я мог посетить каждую вершину только один раз, но это не работает вообще.Самая большая проблема заключается в таком графике:

  2 -> 1
  3 -> 2
  3 -> 1
  1 -> 4

Я запускаю DFS из вершины 1 и возвращаю результат 1. Затем, используя его, я могу сразу вычислить ответ для 2 (я больше не вхожу в вершину 1во втором DFS я использую его ответ вместо этого), то есть 2. Затем я добираюсь до вершины 3, и ... алгоритм суммирует результат 1 и 2, так как я могу достичь обеих этих вершин.Но вершина 1 уже вычислена в результате для вершины 2. Таким образом, я получаю ответ, равный 4, что неверно.

Answer 1

Я думаю, что лучший алгоритм запуска O (| V | * | E |) .

Алгоритм:

1 - сделать SCC на графике.

2 - Построить уменьшенный график Gr .

3 - Выполнить один dfs для каждой вершины v в Gr и для каждого посещенного другого SCC (включая SCC из v ) накапливает количество вершин в них (предварительно рассчитанное с шага 1).

С помощью этого алгоритма вы исключаете коэффициент | V | * | V | из грубой силы O (| V | * | V | + | V | * | E |)) .

Это лучший и простой алгоритм, который я знаю для этой проблемы. У меня нет демонстрации, но я уверен, что лучшего способа нет.

Answer 2

Я действительно подозреваю, что не существует лучшего лучшего алгоритма для общих графиков. Все статьи, которые я нашел по теме [1] [2], описывают алгоритмы, работающие за O (| V | * | E |) время.

На странице википедии [3] говорится, что самые быстрые алгоритмы сводят проблему к умножению матриц.

[1] http://ion.uwinnipeg.ca/~ychen2/conferencePapers/tranRelationCopy.pdf

[2] http://www.vldb.org/conf/1988/P382.PDF

[3] http://en.wikipedia.org/wiki/Transitive_closure#Algorithms