DAG 中两个节点之间的路径数

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。以 s 作为起始顶点开始运行 DFS。当发现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 

Answer 4

您可以使用动态编程或记忆递归调用有效地计算通过有向图的路径。就我个人而言，我发现递归比带表的 DP 更容易思考。下面是递归版本。

要理解此实现，请注意，对于所有 x，从 s 到 t 的路径数等于从 x 到 t 的路径数之和，其中 x 是 s 的直接后继（正如 @stalker 在另一个答案中提到的） ）。我们递归地实现这个想法并记住递归。

下面是一些 C++：

#include <iostream>
#include <unordered_map>

namespace {

    using digraph = std::unordered_map<char, std::vector<char>>;
    using memoization_tbl = std::unordered_map<char, int>;

    int count_paths(memoization_tbl& memos, const digraph& dag, char s, char t) {
        if (s == t) {
            return 1;
        }

        if (memos.contains(s)) {
            return memos.at(s);
        }

        int sum = 0;
        for (auto x : dag.at(s)) {
            sum += count_paths(memos, dag, x, t);
        }

        memos[s] = sum;
        return sum;
    }

    int count_paths(const digraph& dag, char s, char t) {
        memoization_tbl memos;
        return count_paths(memos, dag, s, t);
    }

}

int main() {
    digraph dag;

    dag['a'] = { 'd', 'b' };
    dag['b'] = { 'c', 'd' };
    dag['c'] = { 'd', 'e' };
    dag['d'] = { 'e' };

    std::cout << "number of paths = " << count_paths(dag, 'a', 'e');

    return 0;
}