Алгоритм Прима
Материал из Википедии — свободной энциклопедии
Алгоритм Прима находит остовный лес минимального веса в данном связном графе.
[править] Реализация
Вначале текущее множество рёбер устанавливается пустым. Затем, пока это возможно, проводится следующая операция: из всех рёбер, добавление которых к уже имеющемуся множеству не вызовет появление в нём цикла и разбивания рёбер на две несвязных группы, выбирается ребро минимального веса и добавляется к уже имеющемуся множеству. Когда таких рёбер больше нет, алгоритм завершён. Подграф данного графа, содержащий все его вершины и найденное множество рёбер, является его остовным лесом минимального веса.
[править] Доказательность
Доказать, что алгоритм Прима действительно находит остовный лес минимального веса, можно, показав, что он является частным случаем алгоритма Радо — Эдмондса для графического матроида, где независимые множества — ациклические связные множества рёбер.
