java - 最小产品生成树

Question

在这个minimum product spanning tree问题中，树的成本是树中所有边权重的乘积，而不是权重之和。您可以假设所有边都具有正权重。我想得到以下问题的答案。

(1)给出一个最小乘积生成树与最小权重生成树不同的图。

(2)给出一种计算最小乘积生成树的有效算法。（提示：考虑对数）。

Answer 1

最小乘积生成树的问题可以通过对树进行转换来解决，方法是取边权重的对数，然后找到这棵修改后的树的 MST。

记住对数的性质，log(ab) = log(a) + log(b)。因此，最小产品生成树可以转换为最小成本生成树问题。