Минимальное остовное дерево: различия между версиями

Морет и Шапиро [ ] оценили эффективность жадных MST-алгоритмов, используя разные очереди с приоритетами. Они обнаружили, что лучшим является алгоритм Ярника [7] (также его авторами считаются Прим и Дейкстра, см. [3,7,12]) в варианте реализации с кучей для пар [   ]. Катриэль, Сандерс и Трафф [10] разработали и реализовали нежадный рандомизированный MST-алгоритм на базе алгоритма Карджера и коллег [9]. Они пришли к выводу, что на относительно плотных графах он работает значительно быстрее жадных алгоритмов, протестированных Моретом и Шапиро.