我想做一个更新/计算的图算法
节点的值f(n)是
相邻节点。
图是有向的。
每个节点都有初始f（n）值。
每条边都没有成本（0）。
每个节点的值是其当前值的最大值。
每个相邻节点的值（有向图，因此相邻节点是
从节点具有传入边的位置）。
更正式地说，
f(n) = max(f(n),max_i(f(n_i))), where i from neighbor 1 to neighbor k.
我可以想象一些这样做的方法，但是我不知道到了什么程度
它们是最优的。
有人能给我建议和评论吗（你是否认为
你的建议是最优的，或者建议任何我能适应的存在的图形算法？
最佳答案
声称：
在图中的每个Strongly Connected ComponentV中，此scc中所有顶点的值具有相同的最终得分。
“证明”（指南）：通过在这个SCC中进行扩展，可以将所有分数迭代设置为SCC中找到的最大值。
在aDAG中，每个顶点的值都是max{v,parent(v) | for all parents of v}（定义），分数可以在从开始到结束的单个迭代中找到。
“proof”（准则）：没有“back edges”，因此如果知道所有父节点的最终值，就知道每个顶点的最终值。通过归纳（基础是所有的来源）-你可以得到一个事实，一次迭代就足以确定最终得分。
此外，已知表示SCC的图
graphG'是一个dag。
从上面我们可以得到一个简单的算法：
在图中求最大SCC（可以用Tarjan algorithm完成），并创建SCC图。让它g。注意G'是一个dag。
对于每个sccG'：设置V（直观地-将每个scc的值设置为该scc中的最大值）。
Topological sort图表f'(V) = max{v | v in V}。
根据（3）中的拓扑排序执行一次遍历，并根据其父节点计算G'中每个顶点的f'（v）。
设置G'（其中v在scc v中）
复杂性：
tarjan和创建f(v) = f'(V)是G'
在图的大小中，发现f'也是线性的-O(V+E)
拓扑排序在O(V+E)中运行
单次遍历-线性：O(V+E)
给出最终分数：线性！
所以上面的算法在图的大小上是线性的-O(V+E)