алгоритм Круськала
Інший жадібний алгоритм для задачі про оптимальний каркасі відомий як алгоритм Круськала. У ньому теж на кожному кроці розглядається часткове вирішення. Відмінність від алгоритму Прима полягає в тому, що в алгоритмі Круськала часткове рішення завжди являє собою кістяк ліс 
графа 
, Тобто ліс, що складається з усіх вершин графа і деяких його ребер. На початку не містить жодного ребра, тобто складається з ізольованих вершин. Потім до нього послідовно додаються ребра, поки не буде побудований каркас графа . нехай - ліс, побудований до чергового кроку. Ребро графа, що не належить , Назвемо червоним, якщо вершини цього ребра належать одній компоненті зв'язності лісу , І зеленим, якщо вони належать різним компонентам. якщо до додати червоне ребро, то утворюється цикл. Якщо ж до додати зелене ребро, то вийде новий ліс, в якому буде на одну компоненту зв'язності менше, ніж в , Так як в результаті додавання ребра дві компоненти зіллються в одну. Таким чином, до не можна додати ніяке червоне ребро і можна додати будь-зелене. Для вибору додається ребра застосовується той же "жадібний" принцип, що і в алгоритмі Прима - з усіх зелених ребер вибирається ребро найменшої ваги. Для того щоб полегшити пошук цього ребра, спочатку все ребра графа впорядковуються за зростанням ваг: 
. Тепер послідовність ребер 
досить переглянути один раз і для чергового розглянутого ребра потрібно тільки вміти визначати, чи є воно червоним або зеленим щодо побудованого до цього моменту лісу . Червоні ребра просто пропускаються, а зелені додаються до .
Для більш формального опису алгоритму зауважимо, що поточний ліс визначає розбиття множини вершин графа на області зв'язності цього лісу: 
і що червоне ребро - це таке ребро, у якого обидві вершини належать одній частині розбиття. нехай 
- функція, яка повертає для кожної вершини 
ім'я тієї частини розбиття, якій належить , а 
- процедура, яка по іменах і 
двох частин розбиття будує нове розбиття, замінюючи ці дві частини їх об'єднанням. нехай 
, 
. Тоді алгоритм Круськала (після згаданого упорядкування ребер) можна записати в такий спосіб.
Алгоритм 2. Побудова оптимального каркаса методом Круськала
- for
to 
do 
- if
then 
, 
Більш докладно алгоритм Круськала розглядається у другій частині (в розділі, присвяченому розділеним безлічам). Коректність цього алгоритму випливає із загальної теореми Радо-Едмондс, яка буде розглянута в "Наступній лекції" .