algorithm - 包含一条边并生成具有边的生成树中权重最小的生成树

Question

我希望找到图 G 的最小生成树，使其包含边 e，并且它的权重是所有具有边 e 的生成树中的最小值。如果我包含边 e，然后运行 ​​prime 或 kruskals，它会工作吗？

Answer 1

您可以通过将其权重设置为 0 并运行您最喜欢的 MST 算法来设置该边的边权重（以及您想要包含在生成树中以使其保持树的任何其他边）。