最小生成树算法变异

Question

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

以下是问题所在：

，

• ，我们想要建立一个网络，我们得到了c节点/城市和D个可能的边/连接。边是双向的，我们知道边的代价。边的成本可以表示为di，j，它表示边i的成本。注意，并非所有的c节点都可以直接连接(D是可能的边集)。
• 现在给出了一个没有成本的k个势边/连接的列表。但是，您只能在k条边列表中选择一个边来使用(比如获得免费资金在两个城市之间建造一个机场)。

所以问题是..。找到一套道路(和一个免费机场)，以尽量减少建设网络所需的总成本，在一个有效的运行时连接所有城市。

所以简单地说，解决最小生成树问题，但是可以在k个势边列表中选择1条边，这样就不需要花费。我不知道怎么解决..。我试着找到所有的生成树，按照增加成本和选择最低成本的顺序，但我仍然面临着如何考虑k个势自由边列表中的一个自由边的问题。我还试着找出D势连接的MST，然后根据k中的选项进行调整，以得到结果。

谢谢你的帮助！

Answer 1

首先生成一个MST。现在，如果您添加了一个自由的边，您将创建准确的一个周期。然后，你可以去掉自行车中最重的边缘，得到一棵更便宜的树。

若要通过添加一个空闲边来找到最佳树，您需要在MST中找到最重的边缘，您可以用一个空闲的边缘来替换它。

您可以通过一次测试一个空闲边缘来做到这一点：

vertices

• Remember

1. 选择一个自由边
2. ，在树中(从它的任意根中)找到它的最小的公共祖先，这是在自由边顶点

之间的路径上最重的边。

当你完成的时候，你知道要使用哪一种自由的边缘--这是与最沉重的树边相关的一种，你也知道它取代了哪一种边缘。

为了使步骤(2)和(3)更快，您可以记住每个节点的深度，并像跳过列表一样将其连接到多个祖先。然后，您可以在O(log区)时间内完成这些步骤，从而导致O ( |E|+k) log \v)的总复杂性，这是非常好的。

编辑:更简单的方式

在考虑了这一点之后，似乎有一种超级简单的方法来确定要使用哪一种免费边缘，以及要替换哪一种MST边缘。

忽略k个可能的自由边，使用Kruskal的算法从其他边缘构建MST，但是修改通常不相交的集合数据结构如下：

• 按大小或级别使用联合，但不使用路径压缩。然后，每个联合操作都将建立精确的一个链接，并采用O(log )时间，所有路径长度最多为O(log )长。
• 对于每个链接，请记住创建该链接的边的索引。

那么，对于每个可能的自由边，您可以沿着不相交的集合结构中的链接走上，找出它的端点到底是在哪个点连接到同一个连接组件中。得到最后一个所需边缘的索引，即它要替换的边，而具有最大替换目标索引的自由边是您应该使用的边。

Answer 2

其中一个想法是将您最喜欢的MST算法作为一个黑匣子，并在请求MST之前考虑更改图形中的边缘。例如，您可以尝试这样的方法：

for each edge in the list of possible free edges:
    make the graph G' formed by setting that edge cost to 0.
    compute the MST of G'

return the cheapest MST out of all the ones generated this way

这种方法的运行时间是O(kT(m，n))，其中k是要测试的边数，T(m，n)是使用您最喜欢的黑箱算法计算MST的成本。

我们可以做得更好。有一个众所周知的问题是以下形式：

假设图G有一个MST，然后降低某些边{u，v}的成本。在新的图G‘中找到一个MST’。

有很多算法可以有效地解决这个问题。这里有一个：

Run a DFS in T starting at u until you find v.
If the heaviest edge on the path found this way costs more than {u, v}:
   Delete that edge.
   Add {u, v} to the spanning tree.
Return the resulting tree T'.

(证明这是一项乏味但可行的工作。)这将给出代价O(T(m，n) + kn)的算法，因为您将构建初始MST (time T(m，n))，然后在有n个节点的树中运行k个DFS。

但是，如果您可以使用一些更高级的算法，这可能会得到进一步的改进。Demaine等人的“关于笛卡儿树和范围最小查询”的论文表明，在O(n)时间内，可以预处理最小生成树，以便在时间O(1)中，形式的查询“这棵树中节点u和v之间的路径上的最低代价边是什么？”时间O(1)。因此，您可以构建这个结构，而不是使用DFS来查找u和v之间的瓶颈边缘，从而将整个运行时减少到O(T(m，n) +n+ k)。如果T(m，n)很低(最著名的界是O(mα(m))，其中α(m)是阿克曼反函数，在可行的单位内所有输入都小于5)，这是一个非常快速的算法！