algorithm - 用于计算有向无环图中每个顶点的不同路径数量的线性时间算法

Question

我正在研究算法模块的以下过去的纸质问题:

设 G = (V, E) 是一个简单的有向无环图 (DAG)。
对于 V 中的一对顶点 v、u，如果 G 中存在从 u 到 v 的(有向)路径，则我们说 v 从 u 可达。
(我们假设每个顶点都可以从自身到达。)
对于V中的任意顶点v，设R(v)为顶点v的可达数，即V中从v可到达的顶点u的数量。
设计一种算法，对于给定的 DAG，G = (V, E)，计算 V 中所有顶点 v 的 R(v) 值。
提供算法的分析(即正确性和运行时间 分析)。
(最好的情况是，人们应该尝试设计一种运行在 O(n + m) 时间。)

到目前为止，我有以下想法:

以下用于查找 DAG 拓扑排序的算法可能有用:

TopologicalSort(G)
  1. Run DFS on G and compute a DFS-numbering, N // A DFS-numbering is a numbering (starting from 1) of the vertices of G, representing the point at which the DFS-call on a given vertex v finishes.
  2. Let the topological sort be the function a(v) = n - N[v] + 1 // n is the number of nodes in G and N[v] is the DFS-number of v.

我的第二个想法是动态编程也可能是一种有用的方法。
但是，我目前不确定如何将这两个想法结合成一个解决方案。

如果有任何提示，我将不胜感激!

Answer 1

编辑:不幸的是，下面的方法通常是不正确的。它可能会对通过多条路径可以到达的节点进行多次计数。

如果 DAG 是 polytree，则以下想法是有效的，因为这保证了任意两个节点之间至多有一条路径。

You can use the following steps:

• find all nodes with 0 in-degree (i.e. no incoming edges).

This can be done in O(n + m), e.g. by looping through all edges and marking those nodes that are the end of any edge. The nodes with 0 in-degree are those which have not been marked.

• Start a DFS from each node with 0 in-degree.

After the DFS call for a node ends, we want to have computed for that node the information of its reachability.

In order to achieve this, we need to add the reachability of the successors of this node. Some of these values might have already been computed (if the successor was already visited by DFS), therefore this is a dynamic programming solution.

The following pseudocode describes the DFS code:

function DFS(node) {
    visited[node] = true;
    reachability[node] = 1;

    for each successor of node {
        if (!visited[successor]) {
            DFS(successor);
        }
        reachability[node] += reachability[successor];
    }
}

After calling this for all nodes with 0 in-degree, the reachability array will contain the reachability for all nodes in the graph.

The overall complexity is O(n + m).