带加权顶点的 DAG 算法

Question

设 G = (V,E) 为 DAG（有向无环图）。每个顶点 v 都有一个分配给它的权重 w(v)。给定一个顶点 u，让 f(u) = max{w(v) where v can reach u}。所以，换句话说，f(u)是所有能到达u的顶点的权值中最大的权值。目标是编写一个 线性时间 算法，为 G 中的每个顶点 u 计算 f(u)。

例如，假设这是输入图：

那么算法应该计算以下内容：

• f(A) = 5
• f(B) = 12
• f(C) = 15
• f(D) = 12
• f(E) = 12

在O(n(n+m))时间内完成这个很简单，但是如何在O(n+m)时间内完成呢？

Answer 1

进行拓扑排序，然后按此顺序遍历节点，并为每个节点分配其自身权重的最大值和直接前置节点的 f（即具有通向该节点的边的节点）当前节点）。