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

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

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

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

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