Алгоритм Краскала

1. Выбрать в графе ребро минимального веса, не принадлежащее множеству и такое, чтобы его добавление в множество не создавало в дереве цикл.

2. Добавить это ребро в множество ребер .

3. Продолжать действия первого и второго шагов до тех пор, пока имеются ребра, обладающие указанными свойствами.

Принципиальное отличие алгоритма Прима состоит в том, что всегда имеется дерево, к которому ребра добавляют до тех пор, пока не получится остовное дерево.