Алгоритм Прима

Алгоритм Прима находит остовный лес минимального веса в данном связном графе.

Реализация

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

Доказательность

Доказать, что алгоритм Прима действительно находит остовный лес минимального веса, можно, показав, что он является частным случаем алгоритма Радо — Эдмондса для графического матроида, где независимые множества — ациклические связные множества рёбер.

См. также

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home