最近有人问我是否可以找到一种算法来计算给定图的最小成本生成树,其中生成树的总成本由边成本的乘积而不是它们的总和给出。
有几种算法可以计算常规最小生成树,但我不确定如何针对上述情况调整它们。有什么想法吗?
谢谢。
最佳答案
由于 log(product of edge costs) = sum (log(edge costs)),只需对边权重进行对数变换,并找到这些权重的最小成本生成树。
关于通过乘以边权重给出成本时找到最小生成树的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4218746/