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

Question

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

• 该图是有向图。
• 每个节点都有初始的f(n)值。
• 每条边没有成本（为0）。
• 每个节点的值是其当前值和每个相邻节点（有向图，因此相邻节点是从其具有入射边的节点中选择）的值的最大值。

更正式地说，

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

我可以想象几种方法来做到这一点，但我不知道它们到什么程度上是最优的。

请问有谁能提出建议和评论（无论您认为您的建议是否最佳），或者建议任何我可以适应的现有图形算法？

- user1528976

---

你熟悉Page Rank及其矩阵实现吗？ - amit

另外：这些值是否保证收敛？（PageRank通过使用“随机跳转”来处理它，使得图形应用Perron-Frobenius定理的条件）。 - amit

扩展Amit的评论：您是否打算重复运行此算法，直到它收敛（没有f(n)值发生变化）？ - j_random_hacker

非常感谢您非常有用的评论。我对pagerank矩阵实现并不太熟悉，但在您的提示下，我正在研究它。至于收敛性，我想使用max函数（没有任何sum函数）可以保证收敛...网络中每个节点的最高值将始终小于或等于最高（初始节点值加上边值）的组合。我打算在每次应用程序启动时运行此算法，或者如果在服务器上使用，则定期运行（例如，每秒钟一次，在一个包含100个节点的图上）...但我希望一直运行，直到值完全准确。 - user1528976

抱歉，我的问题提得有些笼统，是为了更好地找到已知算法。事实上，在我的情况下，边的成本始终为0。 - user1528976

Answer 1

声明：

1. 在图中的每个强连通分量 V 中，该SCC中所有顶点的值都具有相同的最终分数。
   "证明"（指导方针）：通过在该SCC中进行传播，可以迭代地将所有分数设置为在该SCC中找到的最大值。

2. 在DAG中，每个顶点的值为max{v，parent(v) | 对于v的所有父项}（定义），并且可以在从开头到结尾的单次迭代中找到得分。
   "证明"（指导方针）：没有“反向边”，因此如果您知道所有父项的最终值，则知道每个顶点的最终值。通过归纳法（基础是所有源） - 可以得出一个事实，即单次迭代足以确定最终得分。

3. 此外，已知表示图g SCC的图G'是DAG。

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

1. 在图中找到最大的SCCs(可以用Tarjan算法完成)，并创建SCC图。 让它成为G'。注意，G'是一个DAG。
2. 对于每个SCC V：设置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)

- amit