5.4.3 Алгоритмы Крускала и Пpимa

Оба этих алгоритма следуют ранее описанной схеме, но по-разному выбира- ют безопасное ребро. В алгоритме Крускала множество рёбер А представляет собой лес, состоящий из нескольких связных компонент (деревьев). Добавляется ребро минимального веса среди всех рёбер, концы которых лежат в разных компонентах.

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