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

Question

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

例如，

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

Answer 1

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

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

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

希望这可以帮助！