Пусть - ациклический ориентированный граф, такой что out-степень любой вершины равна O ( log | V | ) . Для каждой вершины G мы можем подсчитать количество достижимых вершин, просто запустив dfs из каждой вершины, и это займет O ( | V | | E | ) время. Есть ли лучший способ решить эту проблему?
11
Ответы:
Лучший точный алгоритм будет выполняться за время O (min {mn, n ^ 2.38}) с использованием быстрого умножения двоичных матриц. Однако существует случайный алгоритм, который выполняется за время O (m + n) и оценивает число достижимых узлов каждого узла с небольшой относительной ошибкой, см. Статью « Структура оценки размера с приложениями к транзитивному замыканию и достижимости». "Эдит Коэн.
источник
Я не эксперт здесь, я попробую.
1) Поскольку это DAG, он должен иметь вершину-приемник, то есть вершину с выходом 0. Найдите вершину-приемник, скажем, x, и добавьте {x} в качестве достижимой вершины в Neighbor (x). удалите x и повторяйте процесс, пока график не станет пустым
источник
(Аналогично решению Прабу ... но более подробно)
источник