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