algorithm - 使用 Prim 算法寻找最大生成树

Question

我们可以通过将算法更改为选择最大顶点而不是选择最小顶点来计算最大生成树吗？

我通过否定边缘并应用正常的 Prim 的最小生成树算法遇到了解决方案。

Answer 1

将输入图输入算法，但权重被否定。Prim 中的任何内容都没有假设权重是正数。被否定的权重的最小值是通过原始权重的最大值来实现的。