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

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

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

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

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