Жадный алгоритм

Жадный алгоритм на взвешенном графе (G, w).

1. А? 0

2. Отсортировать Е в порядке возрастания весов

3. for x Î E (перебирать все элементы в указанном порядке)

4. do if AÇ{x} Î E проверка на независимость (добавление ребра не даёт цикла)

5. then A? AÇ{x}

6. return A

Этот алгоритм строит максимальное независимое подмножество. Если выбрать некоторый вес w₀, заведомо больший всех прочих весов, и переопределить: w_i ™v_i = w₀– w_i, то алгоритм найдёт минимальное подмножество (например, остов кратчайшей длины).