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

Question

我想要查找DAG中两个节点之间的路径数。 O（V^2）和O（V + E）是可接受的。 O（V + E）提醒我以某种方式使用BFS或DFS，但我不知道如何使用BFS或DFS，但我不知道如何使用BFS或DFS。 有人可以帮忙吗？

Answer 1

做一个拓扑排序的DAG，然后将目标的顶点向后扫描到源。对于每个顶点v，保留从v到目标的路径数量。当你到达源头时，计数值就是答案。那是O(V+E)。

Answer 2

从节点u到v的不同路径的数量是从节点x到v的不同路径的总和，其中x是u的直接后裔。

存储每个节点（临时设置为0）的目标节点v的路径数量，使用相反方向从v（此处值为1）开始，并为每个节点重新计算此值（将所有子节点的值）直到你到达你。

如果按拓扑顺序处理节点（又是相反的方向），则可以保证在访问给定节点时已经计算了所有直接后代。

希望它有帮助。