在所有可达顶点中找到最有价值的顶点

Question

我有一个有向图G=(V,E)，每个顶点v都有两个属性：

• r 表明价值
• m表示最高v'的r（从哪里v'是可到达的顶点v）。

我需要m为所有顶点找到sO(|V|+|E|)。

例如，

最初的 G

A(r = 1, m = 1) ? B(r = 3, m = 3) ? C(r = 2, m = 2)
?
D(r = 4, m = 4)

必须

A(r = 1, m = 4) ? B(r = 3, m = 3) ? C(r = 2, m = 3)
?
D(r = 4, m = 4)

我搜索了 SO 并找到了一些Here，但其中一个答案没有及时约束，另一个答案的解释非常糟糕。这里有什么更简单的想法吗？

Answer 1

使用以下O(E+V*log(V))算法：

- Reverse all directions
- while |V| > 0 do
    find max(v) from remaining nodes in V
    from that node execute DFS and find all reachable nodes and update their m as max(V)
    remove all updated nodes from V

该算法的时间复杂度如您的要求O(V*log(V)+E)