最小生成树变异算法

Question

我在一次面试中被问到以下问题，我无法找到一个有效的解决办法。

以下是问题所在：

我们希望建立一个网络，并给出n个节点和m个边。边是双向的，我们知道边的代价。边的所有费用都保持在数组C中，所以i，j表示边的费用。如果节点i，j不连通，则Ci，j是无限的。 现在，我们还知道，确切地说，K节点能够与具有此属性的其他节点(用于无线传输)进行无线通信。若要将无线技术设置到节点I，则需要花费Bi。因此，节点i为了利用无线传输到节点j的能力，这将花费Bi将无线技术设置到节点i和Bj for j。 因此，问题是找到构建网络所需的最小成本，其中任意两个节点i，j都可以通信(将有一条连接它们的路径)。 作为路径，我们意味着要么有从节点i到j的边缘，要么我们也可以使用支持它的节点之间的无线传输。

很明显，它被要求最小生成树，但困难是，例如，如果我们使用无线技术对节点i，j和k，然后我们添加可能的边i-j，i-k，j-k，如果我们只在i，j中使用，那么我们只有额外的边i-j，所以边取决于我们选择用于无线传输的节点。

一个简单的例子：

假设我们有4 nodes和3 edges C[1,2]=9 , C[1,3]=3 , C[3,4]=5 (其他C[i,j] are infinite)。

节点2和节点3支持设置成本为B2=2和B3=1的无线技术。

在本例中，最小成本为：16 = 8 (for edge 1-3) + 5 (for edge 3-4) + 2 (for set up cost 2) + 1 (for set up cost in node 3).

如果我们没有在edge 2-3中使用无线技术，那么要使这个网络包括成本为9的edge 1-2，那么总成本将是9+8+5 = 22.。

我正在寻找一种有效的算法来解决这种最小生成树问题。任何帮助将不胜感激，感谢您的时间！

Answer 1

首先解决最小生成树问题，这给你一个现任的答案来尝试击败。

现在，创建与原始图相同的另一个图，向这个网络添加一个新的节点。将所有K节点连接到此新节点，边缘权重等于Bi。此边缘表示将无线添加到节点i的成本。现在查找新图的最小生成树。节点现在可以通过此节点连接为"wifi“。

(我假设它们告诉您哪些K节点支持wifi，而不是说您必须从N个节点中选择K，否则如果这个新的最小生成树与新节点的连接超过K个，就会出现问题)。