0
A
回答
1
将算法输入到输入图形中，但重量为负。 Prim中没有什么假设权重是正数。重量的最小值取决于原始重量的最大值。
+0
“Prim中的任何内容都假设权重是正数”（但请注意，例如，Boost Graph Library，其实现IIRC）。 –
答案是肯定的。 – Zotta
如果你有一个最小的查找树实现并且不能或不想改变它，那么使用负权重可能是合理的。但是如果你正在实施你自己，最好做你最初提出的建议。 Prim的算法很贪婪。贪婪地寻求最大限度的工作，贪婪地寻求最低限度的工作。 – Gene