Минимальный охваченный алгоритм охват дерева Соллина

Question

Да, это домашнее задание. Мне было интересно, может ли кто-то объяснить процесс алгоритма Соллина (или Borůvka) для определения минимального охватавания дерева. Также, если бы вы могли объяснить, как определить количество итераций в худшем случае, это было бы здорово.

Answer 1

На верхнем уровне алгоритм работает следующим образом:

• Удерживайте, что у вас есть ряд охваченных деревьев для некоторых подграфов. Первоначально каждая вершина графа является MST без краев.
• В каждой итерации для каждого из ваших охваченных деревьев найдите дешевый край, соединяющий его к другому охваченному дереву. (Это упрощение.)

В худшем случае с точки зрения итераций вы всегда сливаются пары деревьев. В этом случае количество деревьев, которое вы имеете вдвое, будут вдвое итерацию, поэтому количество итераций является логарифмическим в количестве узлов.

Также обратите внимание, что в выборе краев есть особый трюк: если вы не были осторожны, вы можете ввести круг, когда дерево A подключается к дереву B, дерево B подключается к дереву C и дерево C подключается к дереву A. ( Это может произойти только в том случае, если все три края выбрали одинакового веса. Хитрость состоит в том, чтобы иметь произвольный, но фиксированный стягивающий выключатель, как фиксированный порядок краев.)

Итак, это моя задняя часть индекса-карты обзор.

Answer 2

Я использую терминологию Лэймана.

• Сначала выберите вершину
• Проверьте все края из этой вершины и выберите один с минимальным весом
• Сделайте это для всех вершин (некоторые края могут быть выбраны более одного раза)
• Вы получите подключенные компоненты.
• Из этих подключенных компонентов выберите один край с минимальным весом.

Ваше связующее дерево с минимальным весом будет сформировано