Как найти максимальное связующее дерево, используя алгоритм простых чисел?

Question

Я хочу изменить алгоритм Прима, чтобы он мог найти максимальное связующее дерево, как это можно сделать

Answer 1

Алгоритм Прима не против отрицательных весов.

Просто переверните знак веса каждого ребра и используйте алгоритм минимального связующего дерева.

Answer 2

Поможет даже жадность до максимального края вместо минимального края.