使用Prim算法尋找最大生成樹

Question

我們可以通過改變算法來選擇最大頂點而不是選擇最小生成樹來計算最大生成樹嗎？

我碰到了解決方案，通過否定邊緣並應用正常的Prim的最小生成樹算法。

Answer 1

將算法輸入到輸入圖形中，但重量爲負。 Prim中沒有什麼假設權重是正數。重量的最小值取決於原始重量的最大值。