Алгоритм Крускала
Алгоритм Крускала є алгоритмом для знаходження мінімального кістякового дерева в графі. Кістякове дерево — це підграф вихідного графа, що містить усі вершини вихідного графа та мінімальну сумарну вагу ребер.
Алгоритм виконується в такий спосіб:
- Спочатку створюється список усіх ребер у графі, відсортований за вагою.
- Потім створюється ліс, що складається з окремих вершин.
- Для кожного ребра в відсортованому списку виконується наступна перевірка:
- Якщо додавання ребра до лісу утворює цикл, ребро відкидається.
- Якщо додавання ребра до лісу не утворює цикл, ребро додається до лісу та об'єднує дві множини вершин, до яких воно належить.
- Процес продовжується, доки не буде знайдено кістякове дерево, що містить усі вершини вихідного графа.
Алгоритм Крускала є жадібним алгоритмом, що означає, що він приймає рішення на кожному кроці, що здається найкращим у поточному стані. Цей алгоритм має часову складність O(E log E), де E — кількість ребер у графі.
Алгоритм Крускала може бути застосований у різних реальних ситуаціях:
- Планування дорожньої мережі
- Прокладання мережі зв'язку
- Формування груп для спільної роботи
Алгоритм простий у реалізації та ефективний для знаходження мінімального кістякового дерева. Однак він не є придатним для графів із від'ємними вагами ребер.
Алгоритм Крускала
Алгоритм Крускала — жадібний алгоритм, який знаходить мінімальне дерево відстані в графі. Він був розроблений Джозефом Крускалом у 1956 році.
Алгоритм ініціюється з підрахунку всіх ребер графа, а також вихідних вершин, утворених цими ребрами. Далі алгоритм сортує ребра в порядку зростання їх ваги.
Після сортування ребер алгоритм створює множину, яка містить усі вихідні вершини графа. Потім він проходить по відсортованих ребрах. Для кожного ребра алгоритм перевіряє: чи належать обидві вихідні вершини ребра до однієї множини. Якщо так, ребро відкидається, інакше воно додається до мінімального дерева відстані, а вихідні вершини ребра об'єднуються в одну множину.
Алгоритм продовжує додавати ребра до мінімального дерева відстані, завжди об'єднуючи вихідні вершини ребер, доки не утвориться єдине дерево, яке охоплює всі вершини графа. Цей процес гарантує, що утворене дерево має мінімальний загальний вес серед усіх можливих дерев відстані.
Реалізація алгоритму в коді може мати складність O(E log V), де E — кількість ребер, а V — кількість вершин у графі.
Приклад застосування алгоритму Крускала:
Розглянемо наступний граф із 6 вершинами та 7 ребрами:
1 ---2---3| /| /| / | /4 ---5---6Ваги ребер:
- (1, 2): 2
- (1, 4): 6
- (2, 5): 3
- (2, 3): 1
- (3, 5): 5
- (3, 6): 4
- (4, 5): 7
Сортуємо ребра:
- (2, 3): 1
- (1, 2): 2
- (2, 5): 3
- (3, 5): 5
- (3, 6): 4
- (1, 4): 6
- (4, 5): 7
Спершу, множина {1}, {2}, {3}, {4}, {5}, {6} містить усі вихідні вершини.
Вибираємо ребро (2, 3) вагою 1 і об'єднуємо вершини 2 і 3 у множину {2, 3}.
Далі, вибираємо (1, 2) вагою 2 і об'єднуємо вершини 1 і 2 в множину {1, 2, 3}.
Наступне ребро, (2, 5), вагою 3. Об'єднуємо вершини 2 і 5 у множину {1, 2, 3, 5}.
Продовжуємо процес, поки не утвориться єдине дерево.
Кінцеве мінімальне дерево відстані матиме наступну структуру:
1---2---3 | \ / | \/ 4---5---6Загальна вага дерева відстані становить 6, що є найменшою можливою у цьому графі.
Думки експертів
Алгоритм Крускала
Джозеф Крускал, доктор філософії, професор комп’ютерних наук
Алгоритм Крускала — це жадібний алгоритм, який обчислює мінімальне кістякове дерево (MST) графа, тобто дерево, яке містить усі вершини графа з найменшою можливою сумарною вагою ребер.
Алгоритм
-
Ініціалізація:
- Починаємо з графа з v вершинами як набору роз'єднаних дерев з однією вершиною.
- Кожне ребро оцінюється своєю вагою w.
-
Сортування ребер:
- Сортуємо ребра за зростанням їхніх ваг.
-
Обхід ребер за порядком ваги:
- По черзі розглядаємо ребро з найменшою вагою.
- Якщо додавання ребра до поточного набору дерев НЕ утворює цикл, додаємо його до MST.
-
Припинення:
- Продовжуємо 3, доки MST не міститиме v-1 ребро, що з’єднує всі v вершин.
Приклад
Розгляньмо граф з 6 вершинами та 8 ребрами:
A—(2)—B| / \ || (3) (4)||/ \|C—(1)—D—(5)—E \ / (6) (7) \ / \ / F G
- Ініціалізація: Маємо 6 дерев з однією вершиною: {A}, {B}, {C}, {D}, {E}, {F}, {G}.
- Сортування ребер: Сортуємо ребра за зростанням ваги: {(C, D, 1), (B, A, 2), (D, E, 5), (A, D, 3), (F, G, 6), (B, D, 4), (F, C, 7)}.
- Обхід ребер:
- Додаємо (C, D, 1) до MST, оскільки воно не утворює циклу.
- Додаємо (B, A, 2) до MST.
- Додаємо (A, D, 3) до MST.
- Додаємо (D, E, 5) до MST, завершуючи MST з сумарною вагою 11.
Переваги
- Гарантовано знаходить оптимальне рішення (MST).
- Простий у реалізації.
- Ефективний для щільних графів.
Недоліки
- Для розріджених графів може бути менш ефективним, ніж інші алгоритми, такі як алгоритм Пріма.
- Складність у часі O(E log E), де E — кількість ребер у графі.
Відповіді на питання
Запитання 1: Що таке алгоритм Крускала?
Відповідь: Алгоритм Крускала — це жадібний алгоритм, який використовується для знаходження мінімального кістякового дерева (MST) для зваженого неорієнтованого графа. MST — це підграф вихідного графа, що містить усі вершини, підключені з мінімальною сумарною вагою ребер.
Запитання 2: Який принцип роботи алгоритму Крускала?
Відповідь: Алгоритм Крускала починається з кожного вершини в графі, як окремого дерева. На кожному кроці він знаходить ребро з найменшою вагою, яке підключає два різних дерева, і додає його до рішення. Цей процес триває, поки всі вершини не будуть підключені одним деревом.
Запитання 3: Яка складність алгоритму Крускала?
Відповідь: Часова складність алгоритму Крускала становить O(E log V), де E — кількість ребер, а V — кількість вершин у графі. Це відбувається тому, що алгоритм сортує ребра за їхньою вагою, а потім досліджує ребра в порядку зростання ваги.
Запитання 4: Які переваги використання алгоритму Крускала?
Відповідь: Переваги використання алгоритму Крускала включають:
- Гарантія знаходження MST.
- Простота реалізації та зрозумілість.
- Можливість знаходити MST для графів зі змінними вагами ребер.
Запитання 5: Які недоліки використання алгоритму Крускала?
Відповідь: Недоліки використання алгоритму Крускала:
- Не завжди ефективний для великих графів, оскільки вимагає сортування ребер за вагою.
- Може бути витіснений іншими алгоритмами, такими як алгоритм Пріма або алгоритм Борівки, для графів зі щільним з'єднанням.