在线性时间内由红/蓝着色的图中精确使用k条红边求生成树

Question

给定一个具有红边和蓝边且常数K的图G，设计一个确定性的线性时间算法，该算法可以找到G的一个恰好具有K条红边的生成树（或者，如果这样的生成树不存在，则返回false)。

我们迄今所做的：

让每个红边的权重为-1，每个蓝边的权重为0。

找到最小生成树（使用标准线性时间算法）。所以，我们有一个最小权重的生成树T，这意味着我们使用了尽可能多的红边，因为红边只会减少权重。

如果T中的红色边少于K条，则返回false。

如果正好有K个红边，我们就大功告成了，T是答案。

这就是我们的问题，我们如何在线性时间内做到这一点？

每增加一个蓝边就会产生一个循环，因此从循环中移除一个红边就会起作用，但我们如何才能以这种方式保证线性度呢？这是一个好方法吗？

Answer 1

您可以使用两次Prim算法在线性时间内完成此操作。（通常Prim的算法不是线性时间，但当你只有两种类型的边时，你不需要花时间排序边）。

在第一次通过时，在红色边缘之前跟随蓝色边缘，并标记任何你被迫采取的红色边缘。

如果你在这个过程中标记了C条边，那么我们就知道在任何生成树解中至少要有C条红边，所以如果C>K，那是不可能的。

假设我们在第一遍中找到了C(

在第二遍中，在蓝之前跟随红边，直到附加红边的总数达到K-C。在第二次传球中，你也可以跟随第一次传球中标记的红边（这些红边不计入你的总数）。

如果你的额外红边没有达到K-C，那么这是不可能的。