На верхнем уровне алгоритм работает следующим образом:
- Убедитесь, что у вас есть несколько связующих деревьев для некоторых подграфов.Первоначально каждая вершина графа является mst без ребер.
- В каждой итерации для каждого из ваших связующих деревьев найдите самое дешевое ребро, соединяющее его с другим остовным деревом.(Это упрощение.)
В худшем случае с точки зрения итераций вы всегда объединяете пары деревьев.В этом случае количество деревьев у вас будет уменьшаться вдвое на каждой итерации, поэтому количество итераций будет логарифмическим по количеству узлов.
Также обратите внимание, что при выборе ребер для добавления требуется особая хитрость: если вы не будете осторожны, вы можете ввести круг, когда дерево A соединяется с деревом B, дерево B соединяется с деревом C, а дерево C соединяется с деревом A. (Это может произойти, только если все три выбранных ребра имеют одинаковый вес.Хитрость заключается в том, чтобы иметь произвольный, но фиксированный прерыватель связи, как фиксированный порядок краев.)
Итак, вот мой обзор обратной карточки.