🌳 Алгоритми Крускала vs Прима – будуємо мінімальне остовне дерево Коли у вас є зв'язний зважений граф і ви хочете з'єднати всі вершини з мінімальною сумарною вагою — вам потрібне мінімальне остовне дерево (MST). І тут на сцену виходять два класики: Крускал та Прим. 🔹 Алгоритм Крускала 🧠 Ідея: Будуємо дерево, додаючи найменші ребра, уникаючи циклів. Як працює: 1. Сортуємо всі ребра за вагою. 2. Ідемо по списку та додаємо ребро, якщо воно не створює цикл. 3. Для перевірки циклів використовуємо структуру Disjoint Set (Union-Find). Складність: O(E log E) Підходить для розріджених графів. 🔹 Алгоритм Прима 🧠 Ідея: Починаємо з будь-якої вершини і поступово розширюємо дерево, додаючи найменше ребро до нової вершини. Як працює: 1. Вибираємо стартову вершину. 2. Додаємо до MST найменше ребро, що веде до ще не включеної вершини. 3. Повторюємо, поки всі вершини не включено. Зазвичай використовують чергу з пріоритетом (heap) для оптимізації. Складність: O(E log V) Добре працює для щільних графів. 👉 Обидва алгоритми — маст-хев у скарбниці алгоритміста. А ти яким користувався частіше – Крускалом чи Примом? 💬#алгоритми #структуриданих #графи #mstCode Ukraine