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

Question

我想找到DAG中两个节点之间的路径数.O(V ^ 2)和O(V + E)是可接受的.

O(V + E)提醒我以某种方式使用BFS或DFS,但我不知道如何.有人可以帮忙吗？

Answer 1

对拓扑进行拓扑排序,然后将目标顶点向后扫描到源.对于每个顶点v,记录从v目标到目标的路径数.当您到达源时,该计数的值就是答案.那是O(V+E).

Answer 2

从节点u到v的不同路径的数量是从节点x到v的不同路径的总和,其中x是u的直接后代.

存储每个节点的目标节点v的路径数(临时设置为0),使用相反的方向从v(此处值为1)开始,并为每个节点重新计算此值(将所有后代的值相加),直到达到ü.

如果以拓扑顺序处理节点(再次相反方向),则可以保证在访问给定节点时已经计算了所有直接后代.

希望能帮助到你.