在DAG中两个节点之间的路径数 [英] Number of paths between two nodes in a DAG

问题描述

我想找到的DAG中的两个节点之间的路径数量。 Ø（V ^ 2）和O（V + E）是可以接受的。

I want to find number of paths between two nodes in a DAG. O(V^2) and O(V+E) are acceptable.

O（V + E）让我想起了以某种方式使用BFS或DFS，但我不知道怎么办。 有人可以帮忙吗？

O(V+E) reminds me to somehow use BFS or DFS but I don't know how. Can somebody help?

推荐答案

做一个拓扑排序的DAG，然后扫描从目标顶点向后源。对于每一个顶点 v ，保持路径数的计数从 v 目标。当你到达的来源，那算不算值就是答案。这就是 O（V + E）。

Do a topological sort of the DAG, then scan the vertices from the target backwards to the source. For each vertex v, keep a count of the number of paths from v to the target. When you get to the source, the value of that count is the answer. That is O(V+E).

这篇关于在DAG中两个节点之间的路径数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！