#java #algorithm #greedy #minimum-spanning-tree
#java #алгоритм #жадный #минимальное связующее дерево
Вопрос:
Я хочу изменить алгоритм Prim, чтобы он находил максимальное связующее дерево, как это можно сделать
Ответ №1:
Алгоритм Prim не возражает против отрицательных весов.
Просто переверните знак веса каждого ребра и используйте алгоритм минимального связующего дерева.
Комментарии:
1. вы уверены, что это не предполагает, что вы не можете уменьшить «вес» дерева, добавив новые ветви?
Ответ №2:
Поможет даже стремление к максимальному краю вместо минимального края.