Количество путей между двумя узлами в DAG

#algorithm #graph-theory

#алгоритм #теория графов

Вопрос:

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

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

Ответ №1:

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

1. Но как вести подсчет количества путей от каждой вершины к цели? Например, если какая-либо i-я вершина в DAG имеет прямое соединение с целью, мы знаем, что соединение есть, поэтому увеличиваем счетчик. Но у i-й вершины может быть много других вершин, которые, в свою очередь, могут быть явно или неявно связаны с целью. Итак, как обработать эту часть? Каким будет время выполнения?

Ответ №2:

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

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

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

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

Ответ №3:

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

Добавьте поле к представлению вершины для хранения целого числа. Изначально установите количество вершин t равным 1, а количество других вершин равным 0. Запустите DFS с s в качестве начальной вершины. При обнаружении t оно должно быть немедленно помечено как завершенное (ЧЕРНЫМ ЦВЕТОМ), без дальнейшей обработки, начиная с него. Впоследствии, каждый раз, когда 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