algorithm - 修改后的 MST

Question

谁能想出一种方法来修改 Kruskal 的最小生成树算法，使其必须包含某个边（u，v）？

Answer 1

我可能会感到困惑，但据我记得，kruskal 可以处理负权重，所以你可以给这个边缘-infinity权重。

• 当然它实际上不会是-infinity，而是一个足够低的数字，足够重要以至于它不能被忽略，就像-1 * sigma(|weight(e)|)E 中的每个 e一样。

Answer 2

如果您可以修改图形结构，您可以删除顶点u和v，并用具有边 u 和 v 的新顶点 w 替换它们。在重复边的情况下，选择权重最小的边。

Answer 3

假设我们知道 (u,v) 的边权重，我们也可以简单地将其添加到边权重排序列表的前面（因为 Kruskal 以升序对边权重进行排序）。在这种情况下，边 (u,v) 将是我们树中包含的第一条边，并且 Kruskal 将正常运行，找到具有 (u,v) 的最小权重的生成树。