Я хочу найти количество путей между двумя узлами в DAG. O (V ^ 2) и O (V + E).
O (V + E) напоминает мне как-то использовать BFS или DFS, но я не знаю, как это сделать. Может ли кто-нибудь помочь?
Количество путей между двумя узлами в DAG
Ответ 1
Сделайте топологический вид DAG, затем отсканируйте вершины от цели назад до источника. Для каждой вершины v держите отсчет количества путей от v до цели. Когда вы дойдете до источника, значение этого счета будет ответом. Это O(V+E).
Ответ 2
Число различных путей от node u до v представляет собой сумму различных путей от узлов x до v, где x является прямым потомком u.
Сохраняйте количество путей для таргетинга node v для каждого node (временно установленное значение 0), перейдите от v (здесь значение равно 1), используя противоположную ориентацию, и пересчитайте это значение для каждого node (sum значение всех потомков), пока вы не достигнете u.
Если вы обрабатываете узлы в топологическом порядке (опять противоположная ориентация), вам гарантируется, что все прямые потомки уже вычисляются при посещении данного node.
Надеюсь, что это поможет.