<tex> A = \{ \} </tex>
'''while''' <tex> A </tex> не является остовом
'''do''' найти безопасное ребро <tex> ( u, v ) \in E </tex> для <tex> A </tex> <font color = darkgreen>// нужное ребро находится с помощью "Леммы о безопасном ребре" </font color = darkgreen>
<tex> A = A \cup \{( u, v )\} </tex>
'''return''' <tex> A </tex>
В результате алгоритма получится минимальное остовное дерево <tex> A </tex>, состоящее полностью из безопасных ребер, так как на каждом шаге добавлялось безопасное ребро.
Легко заметитьТеперь, что остовное дереворассмотрим какой-нибудь разрез <tex> (S, T) </tex> уже построенного дерева <tex> A </tex> и пересекающее ребро <tex> (u, v) </tex>, не удовлетворяющее условиюпричем <tex> u \in S </tex>, не минимальноа <tex> v \in T </tex>. Если для какого-то ребра оказалосьНайдем путь, что оно легче некоторых рёбер образуемого цикласоединяющий вершины <tex> u </tex> и <tex> v </tex>. Так как они находятся в разных компонентах связности, то можно получить остов с меньшим весомкакое-нибудь ребро <tex> (a, добавив это ребро в остовb) </tex> тоже будет пересекать разрез <tex> (S, и удалив самое тяжелое ребро из циклаT) </tex>. Если же это условие не выполнилось ни для одного Очевидно, что <tex> w(a, b) \le </tex> веса ребра<tex> w(u, v) </tex>, то вес остова при добавлении не изменитсятак как второе - безопасное ребро.
}}
