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

Question

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

更新 1：@Paul 在 O(b + a log a) 中准备了一个不错的答案。但我搜索 O(a + b) 算法，如果有的话？

有没有其他不同的高效或最快的方法来做到这一点？

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.

Answer 2

按权重降序对所有节点进行排序，并创建g'所有边反转的图（即，如果中E存在边，则 中也存在边）。在此图中，您现在可以通过简单的 DFS 传播最大值。对所有节点迭代执行此操作，并在已分配最大权重时终止。a -> bgb -> ag'

作为伪代码：

dfs_assign_weight_reachable(node, weight):
    if node.max_weight_reachable >= weight:
        return

    node.max_weight_reachable = weight

    for n = neighbor of node:
        dfs_assign_weight_reachable(n, weight)

g' = g with all edges reversed
nodes = nodes from g' sorted descendingly by weight
assign max_weight_reachable = -inf to each node in nodes

for node in nodes:
    dfs_assign_weight_reachable(node, node.weight)

更新：
紧界是O(b + a log a)。a log a是由排序步骤引起的。每条边在反转步骤期间被访问一次，在分配最大权重期间被访问一次，从而给出max- 表达式中的第二项。

致谢：
我要感谢@SerialLazer投入时间讨论上述算法的时间复杂性并帮助我找出正确的界限。