Количество достижимых вершин в DAG для каждой вершины

11

Пусть - ациклический ориентированный граф, такой что out-степень любой вершины равна O ( log | V | ) . Для каждой вершины G мы можем подсчитать количество достижимых вершин, просто запустив dfs из каждой вершины, и это займет O ( | V | | E | ) время. Есть ли лучший способ решить эту проблему?G(V,E)O(log|V|)GO(|V||E|)

MikleB
источник
1
@Radu это прямой дубликат? это звучит так
Суреш Венкат
@Suresh, по сравнению с моим вопросом, этот вопрос имеет верхнюю границу степени вершины и не требует нижней границы. По моему мнению, это небольшие различия, поэтому я бы посчитал это дубликатом, но я не очень к этому отношусь.
Раду GRIGore
1
Хорошо, поэтому мы оставим все как есть.
Суреш Венкат
4
Ответ Вирджи на мой вопрос подразумевает алгоритм для этого. O(|V|2)
Раду GRIGore

Ответы:

5

Лучший точный алгоритм будет выполняться за время O (min {mn, n ^ 2.38}) с использованием быстрого умножения двоичных матриц. Однако существует случайный алгоритм, который выполняется за время O (m + n) и оценивает число достижимых узлов каждого узла с небольшой относительной ошибкой, см. Статью « Структура оценки размера с приложениями к транзитивному замыканию и достижимости». "Эдит Коэн.

user22547
источник
-1

Я не эксперт здесь, я попробую.

1) Поскольку это DAG, он должен иметь вершину-приемник, то есть вершину с выходом 0. Найдите вершину-приемник, скажем, x, и добавьте {x} в качестве достижимой вершины в Neighbor (x). удалите x и повторяйте процесс, пока график не станет пустым

Prabu
источник
Так как внешняя степень ограничена, было бы более полезно начать с источника?
Андрас Саламон
@ andras-salamon: нет, потому что вы не знаете, сколько узлов доступно из источника. Вы не делаете этого (ноль) для раковины все же.
Мартин Б.
O(|V||E|)xO(|V|)O(|V|)O(|V|)O(|V||E|)
-2

(Аналогично решению Прабу ... но более подробно)

N(v)vreach(v)

  1. O(|V|+|E|)
  2. vreach(v)=nN(v)reach(n)

|E|O(|V|+|E|)

Мартин Б.
источник