Количество путей между двумя узлами в группе обеспечения доступности баз данных

Question

Я хочу найти количество путей между двумя узлами в группе доступности баз данных. O (V ^ 2) и O (V + E) являются приемлемыми.

O (V + E) напоминает мне как-то использовать BFS или DFS, но я не знаю как. Может кто-нибудь помочь?

Answer 1

Выполните топологическую сортировку DAG, затем отсканируйте вершины от цели назад к источнику. Для каждой вершины v ведется подсчет количества путей от v до цели. Когда вы добираетесь до источника, значение этого количества является ответом. Это O(V+E).

Answer 2

Количество различных путей от узла u к v является суммой различных путей от узлов x до v, где x является прямым потомком u.

Сохранение количества путей к целевому узлу v длякаждый узел (временно установлен на 0), перейдите от v (здесь значение 1), используя противоположную ориентацию, и пересчитайте это значение для каждого узла (суммируйте значение всех потомков), пока не достигнете u.

Если выобрабатывая узлы в топологическом порядке (опять противоположная ориентация), вы гарантируете, что все прямые потомки уже вычислены при посещении данного узла.

Надеюсь, это поможет.