查找特定边缘是否包含在任何MST中

Question

我有关于MST和有向图的问题。假设存在具有权重函数w的图G：E - > R并且还存在来自E组（u，v）的边e。我需要在o（E + V）中找到算法，检查e是否包含在任何MST中。

Answer 1

不使用数字作为权重，而是使用数字对的向量作为权重。添加是分量的。比较是在第一个数字上，在第二个数字上打破了关系。 （非常方便，这是Python如何比较不等式的元组的默认规则。）

为每个边缘x分配(w(x), 0)的重量。但指定你的特殊元素e重量(w(e), -1)。

现在搜索MST。当且仅当您的原始图表具有包含e的MST时，MST将包含e。