Описание

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

Строим граф  , где   — множество рёбер нулевого веса графа   c весовой функцией  . Если в этом графе найдётся остовное дерево с корнем в  , то оно и будет искомым.

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

Продолжим с пункта 2, используя граф   вместо  .

В   построено MST  . Построим теперь MST   в   с весовой функцией  . Добавим к   все вершины компоненты сильной связности графа  , которой принадлежит   (по путям нулевого веса из  ). Пусть в   есть ребро  , где   отвечает компоненте сильной связности  , а   — компоненте сильной связности   графа  . Между   и   в графе   с весовой функцией   есть ребро  , вес которого равен весу ребра  . Добавим это ребро к дереву  . Добавим к   все вершины компоненты   по путям нулевого веса из  . Сделаем так для каждого ребра дерева  .

Полученное дерево   — MST в графе  .