Ця симуляція анімує два класичні жадібні алгоритми — Краскала та Пріма — які обчислюють мінімальне кістяне дерево (МКД) зваженого графа: підмножину ребер, що з'єднує кожен вузол, утримуючи сумарну вагу ребер якомога меншою. Вузли розкидані по полотну та з'єднані зі своїми найближчими сусідами, причому кожне ребро несе числову вартість. Спостерігаючи, як дерево росте ребро за ребром, видно, як зовсім різні стратегії приходять до однакової оптимальної структури — результат, гарантований властивістю розрізу кістяних дерев.
Випадковий зважений граф із 8–40 вузлів, кожен з яких з'єднаний приблизно зі своїми чотирма найближчими сусідами, з вагами, похідними від екранної відстані. Алгоритм Краскала сортує всі ребра за вагою та додає найдешевше, яке не утворює цикл, використовуючи структуру системи непересічних множин (Union-Find) для виявлення циклів. Алгоритм Пріма натомість нарощує одне дерево від вузла 0, повторно додаючи найдешевше ребро, що сягає невідвіданого вузла. Обидва завершуються рівно з N−1 ребрами та однаковою мінімальною сумарною вагою.
Перемикайтеся між Краскалом та Прімом, потім задайте кількість вузлів повзунком «Вузли» (8–40). Оберіть швидкість відтворення: «Повільно», «Норм.» чи «Швидко». Натисніть Грати для безперервної анімації або Крок, щоб просуватися на одне рішення за раз, спостерігаючи за ребрами-кандидатами (жовті), прийнятими (зелені) та відхиленими (червоні). Новий граф генерує свіже розташування. Бічна панель відстежує кількість вузлів, усього ребер, ребра МКД та поточну вагу МКД.
Обидва алгоритми доведено оптимальні, проте алгоритм Краскала було опубліковано 1956 року, а Пріма — 1957 року (і вперше описано Ярніком у 1930 році). На графі з унікальними вагами ребер мінімальне кістяне дерево єдине, тож Краскал і Прім завжди сходяться на ідентичному наборі ребер, попри дослідження у зовсім різному порядку.
Кістяне дерево — це набір ребер, що з'єднує кожен вузол графа без утворення жодного циклу, для N вузлів завжди використовуючи рівно N−1 ребер. Мінімальне кістяне дерево — це кістяне дерево, ваги ребер якого дають найменшу можливу суму. Воно широко застосовується для проєктування малозатратних мереж, як-от кабелі, трубопроводи та дорожні сполучення.
Алгоритм Краскала орієнтований на ребра: він сортує кожне ребро за вагою та жадібно додає наступне найдешевше ребро, доки воно не створює цикл, використовуючи структуру системи непересічних множин для перевірки зв'язності. Алгоритм Пріма орієнтований на вузли: він починає з одного вузла та завжди розширює наявне дерево найдешевшим ребром до невідвіданого вузла. Вони досліджують у різному порядку, але дають однакову оптимальну вагу.
Кожне ребро підписане своєю цілою вагою, обчисленою з відстані між його двома вузлами. Бліді ребра не оброблені, жовті ребра — поточні кандидати, зелені ребра прийнято до дерева, а червоні ребра відхилено за утворення циклу. У режимі Пріма зафарбовані зелені вузли — це ті, що вже є частиною зростаючого дерева.
Краскал розглядає ребра від найдешевшого до найдорожчого, але додавання ребра між двома вузлами, які вже з'єднані, утворило б цикл, а не розширило дерево. Структура системи непересічних множин виявляє це майже за сталий час, тож таке ребро позначається відхиленим (червоне) та пропускається, забезпечуючи, щоб результат залишався коректним деревом.
Обидва завжди дають мінімальне кістяне дерево, тож сумарна вага ідентична. Коли всі ваги ребер різні, саме МКД єдине, а отже Краскал і Прім обирають рівно ті самі ребра. Якщо деякі ваги збігаються, обрані ребра можуть трохи відрізнятися, але загальна мінімальна вага все одно та сама.