我希望找到图 G 的最小生成树，使其包含边 e 并且它的权重是所有具有边 e 的生成树中的最小值。如果我包含边 e 然后运行 prime 或 kruskals 它会起作用吗？
最佳答案
您可以通过将其权重设置为 0 并运行您最喜欢的 MST 算法来设置该边的边权重(以及您想要包含在生成树中以使其保持树结构的任何其他边)。
关于algorithm - 包含一条边并在有边的树中生成权重最小的生成树，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/17008259/