В чем отличие алгоритма Крускала от алгоритма Прима при построении минимального остовного дерева?

Отличие алгоритма Крускала от алгоритма Прима при построении минимального остовного дерева заключается в принципе выбора очередного ребра. 7

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

Алгоритм Крускала работает иначе: весь единый список рёбер упорядочивается по неубыванию весов ребра. 7 Далее рёбра перебираются от рёбер с меньшим весом к большему, и очередное ребро добавляется к каркасу, если оно не образовывает цикла с ранее выбранными рёбрами. 7 В частности, первым всегда выбирается одно из рёбер минимального веса в графе. 7

Таким образом, алгоритм Прима выбирает ребро, исходя из уже построенного фрагмента дерева, а алгоритм Крускала — из отсортированного списка рёбер, при условии, что добавляемое ребро не создаёт цикл с ранее выбранными. 79