algorithm - 计算最坏情况时间复杂度的算法？

Question

NASA 希望使用通信渠道连接遍布全国的 n 个站点。每对站都有不同的可用带宽，这是先验已知的。NASA 希望以这样一种方式选择 n-1 个通道（可能的最小值），以使所有站点都通过通道链接，并且总带宽（定义为通道的各个带宽的总和）最大。为这个问题给出一个有效的算法并确定其最坏情况的时间复杂度。考虑加权图 G = (V,E)，其中 V 是站点集合，E 是站点之间的通道集合。将边 e ∈ E 的权重 w(e) 定义为相应通道的带宽。

标签： algorithm

Answer 1

您最喜欢的最小生成树算法可以很容易地通过颠倒边权重的顺序来解决这个最大生成树问题。