Жадные алгоритмы
Представим себе зимовщика, которому предоставили некоторый запас продуктов на всю
зиму. Конечно, он может сначала съесть все самое вкусное – шоколад, мясо и т.п., но за такой подход придется жестоко расплачиваться в конце зимовки, когда останется только соль и маргарин.
Подобным образом, если оптимальное решение строится по шагам, обычно нельзя выбирать на каждом этапе «самое вкусное» – за это придется расплачиваться на последних шагах. Такие алгоритмы называют жадными.
Для решения задачи Прима-Краскала используется жадный алгоритм:
Требуется проверить, чтобы циклов не было. Сделать это можно так: в самом начале покрасим все вершины в разные цвета и затем, выбрав очередное ребро между вершинами i и j, где i и j имеют разные цвета, перекрасим вершину j и все соединенные с ней (то есть имеющие ее цвет) в цвет i. Таким образом, при выборе ребер, соединяющих вершины разного цвета, цикл не возникнет никогда, а после n-1 шагов все вершины будут иметь один цвет.
В цикле n-1 раз выбрать из оставшихся ребер самое короткое ребро, которое не образует цикла с уже выбранными.