1. Положить k=1.
2. Выбрать ребро с минимальным весом и включить его в дерево Т.
3. Если k<n-1, то перейти к п.4, иначе – к п.6.
4. Из оставшихся ребер выбрать ребро с минимальным весом и включить его в дерево Т, если оно не образует цикла с построенной частью.
5. Положить k=k+1. Перейти к п.3.
6. Конец алгоритма.
Пример. Рассмотрим на рис. 6.2а связный взвешенный граф G(X, U, W), |X|=n=6, |U|=m=9, |W|=m=9.
Процесс построения минимального остовного дерева при помощи жадного алгоритма изображен на рис. 6.2.
а) взвешенный граф б) выбор 1-го ребра в) выбор 2-го ребра
г) выбор 3-го ребра д) выбор 4-го ребра е) выбор 5-го ребра
Рис. 6.2. Построение минимального остовного
дерева жадным алгоритмом
Пунктиром обозначены ребра, среди которых на следующем шаге алгоритма ищется ребро с минимальным весом. Построенное дерево Т имеет суммарный вес ребер, равный 23.
При внимательном рассмотрении жадный алгоритм оставляет двойственное впечатление. С одной стороны он прост, но запрограммировать его – далеко не тривиальная задача. Дело в том, что в п.4 алгоритма содержится скрытый под алгоритм, заключающийся в определении возможного цикла в построенном дереве Т. Реализация же данного пол-алгоритма может сделать неэффективным сам жадный алгоритм.
Рассмотренный ниже алгоритм Прима свободен от этого недостатка. Он настолько прост, что трудно поверить в его корректность.
