algorithm - 具体图和需要更多创意解决方案

Question

有向图 (|V|=a, |E|=b)给出。
每个顶点都有特定的权重。我们想要每个顶点 (1..a)找到可以从该顶点到达的具有最大权重的顶点。

Update 1: one nice answer is prepare by @Paul in O(b + a log a). but I search for O(a + b) algorithms, if any?

Is there any different efficient or fastest any other ways for doing it?

Answer 1

是的，可以修改 Tarjan 的 SCC 算法以在线性时间内解决这个问题。
Tarjan 的算法使用两个节点字段来驱动其 SCC 查找逻辑:index ，表示算法发现节点的顺序；和 lowlink , 最小值 index可以通过一系列树弧和后面的弧到达。作为相同深度优先遍历的一部分，我们可以计算另一个字段 maxweight , 具有以下两种含义之一:

对于尚未包含在完成的 SCC 中的节点，它表示一系列树弧可达到的最大权重，可选地跟随一个到另一个 SCC 的交叉弧，然后是任何后续路径。

对于已完成的 SCC 中的节点，它表示可达到的最大权重。

计算逻辑 maxweight如下。如果我们发现来自 v 的弧到新节点 w ，然后 vw是树弧，所以我们计算w.maxweight递归并更新 v.maxweight = max(v.maxweight, w.maxweight) .如 w在栈上，那么我们什么都不做，因为 vw是后弧，不包括在 maxweight 的定义中.否则，vw是一个交叉弧，我们对树弧进行相同的更新，只是没有递归调用。
当 Tarjan 的算法识别 SCC 时，是因为它有一个节点 r与 r.lowlink == r.index .自 r是这个 SCC 的深度优先搜索根，其值为 maxweight对整个 SCC 是正确的。我们没有在 SCC 中记录每个节点，而是简单地更新其 maxweight至 r.maxweight .