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

Задача MST обычно рассматривается [7, 12] как одна из первых комбинаторных задач, исследовавшихся с алгоритмической точки зрения. Формальное определение было дано Борувкой в 1926 году [ ] (еще до возникновения теории вычислимости, комбинаторной оптимизации и в немалой степени – теории графов), и с тех пор этот базовый алгоритм широко использовался. Задача MST способствовала исследованиям в таких сферах, как оптимизация матроидов [3], и разработке эффективных структур данных – таких как очереди с приоритетами (или кучи) и структуры непересекающихся множеств [2, 18].