树/图遍历：查找最大值路径

Question

我试图，给定一个具有整数值和 N 级的图 G，对从根节点到叶节点的值求和。找出这些路径值的最大总和。子节点可以有多个父节点，这就是为什么它更像是一个图而不是一棵树。

例如，

我尝试通过 BFS 为一个小型 Java 小程序实现这一点，但我不确定这是最好的方法。是否有其他建议可以使它与节点数量保持一致，即 O(n)。我想不出任何扩展到 O(n) 的方法。有任何想法吗？

Answer 1

您可以通过使用动态编程算法将信息从底层节点向上传播，从而在线性时间内解决此问题。

这样想：如果图只有一层，那么最佳答案必须是从该层中获取最大的值。另一方面，假设该图有 n + 1 层，并假设您已经（递归地）计算了最底部 n 层的最佳解决方案。在这种情况下，您可以通过查看顶层并计算每个条目的总和加上其任何直接子项的最佳解决方案（您已经预先计算）来找到整体最佳解决方案。所有这些中的最大值为您提供整体最大值。

这种方法最终只会访问每条边一次，因此总运行时间最终为 O(n + m)，其中 n 是节点数，m 是边数。

希望这可以帮助！