algorithm - 最小生成树变异算法

Question

我在面试中被问到以下问题，我无法找到有效的解决方案。

问题是:

We want to build a network and we are given n nodes and m edges. Edges are bidirectional and we know the cost of the edge. All the costs of the edges are hold in an array C, so C[i,j] which denotes the cost of the edge i-j. If nodes i,j are not connected then C[i,j] is infinite.

Now we also know that exactly K of the nodes are able to communicate wireless to other nodes which have also this property (for wireless transmission). To set up wireless technology to node i costs B[i]. So node i in order to use the ability of wireless transmission to node j this will costs B[i] to set up the wireless technology to node i and B[j] for j.

So the question is to find the minimum cost required to build the network where any two nodes i,j could communicate (there will be a path connecting them).

As path we mean that either there are edges that lead from node i to j or we can also use wireless transmission between nodes that support it.

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

一个简单的例子:

假设我们有 4 个节点 和 3 个边 C[1,2]=9 , C[1,3]=3 , C[3 ,4]=5(其他C[i,j]是无限的)。

节点 2 和 3 支持无线技术，设置成本 B[2]=2 和 B[3]=1。

在此示例中，最低成本为:16 = 8(对于边缘 1-3)+ 5(对于边缘 3-4)+ 2(对于设置成本 2)+ 1(对于设置成本在节点 3).

如果我们不在边缘 2-3 中使用无线技术，那么要构建网络，我们应该包括成本为 9 的 edge 1-2，因此总成本将为 9+8+ 5 = 22。

我正在为这种最小生成树问题寻找一种有效的算法。任何帮助将不胜感激，感谢您抽出宝贵时间!!

Answer 1

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

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

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