java - 最小积生成树

Question

在最小乘积生成树问题中，一棵树的成本是树中所有边权值的乘积，而不是权值之和。您可以假设所有边都具有正权重。我想得到以下问题的答案。

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

(2) 给出一个计算最小乘积生成树的高效算法。 (提示:想想对数)。

Answer 1

Minimum Product Spanning tree 的问题可以通过取边权的对数转换树，然后找到这个修改后的树的 MST 来解决。

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