用于基于相邻节点计算节点值的图算法

Question

我想制作一个图算法,根据相邻节点f(n)的每个值更新/计算节点的f(n)值.

• 该图是针对性的.
• 每个节点具有初始f(n)值.
• 每条边都有NO成本(0).
• 每个节点的值是其当前值的最大值和每个相邻节点的值(有向图,因此邻居是节点具有传入边的位置).

更正式的,

f(n) = max(f(n),max_i(f(n_i))), where i from neighbor 1 to neighbor k.

我可以想象一下这样做的几种方法,但是我不知道它们在什么范围内是最佳的.

任何人都可以提出建议和评论(你认为你的建议是否最优)或建议我能适应的任何现有的图算法？

Answer 1

声明:

1. 在图中的每个强连通分量 V中,此SCC中所有顶点的值具有相同的最终分数.
   "证明"(指南):通过在此SCC中进行传播,您可以迭代地将所有分数设置为此SCC中找到的最大值.

2. 在DAG中,每个顶点的值是max{v,parent(v) | for all parents of v}(定义),并且可以在从开始到结束的单个迭代中找到分数.
   "证明"(准则):没有"后边缘",因此如果您知道所有父项的最终值,您就知道每个顶点的最终值.通过归纳(基础是所有来源) - 您可以了解单次迭代足以确定最终得分的事实.

3. 而且,已知表示图G'的SCC的图g是DAG.

从上面我们可以推导出一个简单的算法:

1. Fing图中的最大SCC(可以用Tarjan算法完成),并创建SCC图.就这样吧G'.请注意,这G'是一个DAG.
2. 对于每个SCC V:set f'(V) = max{v | v in V}(直观地 - 将每个SCC的值设置为此SCC中的最大值).
3. 拓扑排序图G'.
4. 根据(3)中的拓扑排序进行单次遍历 - 并G'根据其父项计算每个顶点的f'(V).
5. 设置f(v) = f'(V)(其中v在SCC V中)

复杂:

1. Tarjan和创造G'是O(V+E)
2. 查找f'在图表的大小上也是线性的 - O(V+E)
3. 拓扑排序运行 O(V+E)
4. 单遍历 - 线性: O(V+E)
5. 给出最终得分:线性!

所以上面的算法在图形的大小上是线性的 -O(V+E)