Какие существуют способы нахождения минимального остовного дерева во взвешенном графе?

Для нахождения минимального остовного дерева во взвешенном графе существуют два основных алгоритма: Прима и Краскала. 24

Алгоритм Прима находит подмножество рёбер, которое включает каждую вершину графа, так что сумма весов рёбер может быть минимизирована. 1 Алгоритм состоит из трёх шагов: 3

1. Из вариативности путей, исходящих от стартовой вершины, выбирают минимальное по весу ребро, дотягиваясь до очередной точки. 3
2. Из множества рёбер графа, один конец которых уже принадлежит дереву, выбирают путь наименьшего веса. 3
3. Новое ребро присоединяют к дереву, если исключена цикличность. 3
4. Повторяют второй шаг, взращивая дерево до полного задействования всех исходных вершин графа. 3

Алгоритм Краскала используется для нахождения минимального остовного дерева для связного взвешенного графа. 1 Основная цель алгоритма — найти подмножество рёбер, с помощью которых можно обойти каждую вершину графа. 1 Алгоритм заключается в следующем: 1

1. Отсортировать все рёбра по весу (от наименьшего к наибольшему). 1
2. Взять ребро с наименьшим весом и добавить его в остовное дерево. 1
3. Если добавляемое ребро создаёт цикл, не брать такое ребро. 1
4. Продолжать добавлять рёбра, пока не достигнут всех вершин и не будет создано минимальное остовное дерево. 1

У этих алгоритмов общий подход — они добавляют некоторые рёбра графа по одному так, что в любой момент выбранные рёбра составляют часть некоторого минимального остовного дерева. 4