Жадный алгоритм на взвешенном графе (G, w).
1. А? 0
2. Отсортировать Е в порядке возрастания весов
3. for x Î E (перебирать все элементы в указанном порядке)
4. do if AÇ{x} Î E проверка на независимость (добавление ребра не даёт цикла)
5. then A? AÇ{x}
6. return A
Этот алгоритм строит максимальное независимое подмножество. Если выбрать некоторый вес w0, заведомо больший всех прочих весов, и переопределить: wi vi = w0– wi, то алгоритм найдёт минимальное подмножество (например, остов кратчайшей длины).