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

Question

Я хочу найти количество путей между двумя узлами в DAG. 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), используя противоположную ориентацию, и пересчитайте это значение для каждого узла (суммируйте значение всех потомков), пока не достигнете и.

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

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

Answer 3

Этот вопрос задавался в другом месте на SO, но нигде не упоминалось более простое решение с использованием DFS + DP; все решения, кажется, используют топологическую сортировку. Более простое решение выглядит так (пути от s до t ):

Добавьте поле в представление вершины для хранения целочисленного счетчика. Первоначально установите количество вершин t равным 1, а количество других вершин равным 0. Запустите DFS с вершиной s в качестве начальной. Когда t обнаружен, он должен быть немедленно помечен как завершенный (BLACK), без дальнейшей обработки, начиная с него. Впоследствии, каждый раз, когда DFS заканчивает вершину v , установите счетчик v равным сумме счетчиков всех вершин, смежных с v. Когда DFS завершит работу с вершиной s , остановится и вернет счетчик, вычисленный для s . Временная сложность этого решения равна O(V+E).

Псевдокод:

      simple_path (s, t) 
    if (s == t) 
        return 1 
    else if (path_count != NULL)
        return path_count 
    else 
        path_count = 0
        for each node w ϵ adj[s] 
            do path_count = path_count + simple_path(w, t) 
        end 
    return path_count 
end