Знаходження мінімального кістякового дерева графа за допомогою алгоритму Крускала

Нагадаємо, що у параграфі алгоритм Прима нами було розглянуто алгоритм, який реалізує процес побудови мінімального кістяка за допомогою жадібного включення в нього найближчої вершини. Цікаво, що існує й інший «жадібний» алгоритм, який вирішує задачу побудови мінімального кістякового дерева і також дає оптимальне рішення. Це алгоритм Крускала, названий так по імені Джозефа Крускала, який відкрив його, будучи студентом-другокурсником.

Алгоритм Крускала, як і алгоритм Прима, будує кістяк по одному ребру за раз. Але замість того, щоб здійснювати побудову дерева з початкової вершини, алгоритм Крускала паралельно будує декілька дерев, зливаючи результати в єдине дерево тільки в кінці алгоритму. Таким чином, на відміну від алгоритму Прима, який був обмежений вибором ребра найкоротшої довжини, алгоритм Крускала у такому виборі вільний — розглядаються всі ребра графа і віддається перевага найкоротшому з них, що не створює цикл.

Алгоритм Крускала

Ілюстрація роботи алгоритму Крускала

Побудова кістякового дерева починається з дерев, кожне з яких складається з однієї вершин. На кожному наступному кроці виконується операція об'єднання двох дерев, використовуючи для цього ребро найкоротшої довжини (до прикладу, для графа, зображеного на рисунку вище, на першій ітерації, за допомогою ребра було здійснено злиття двох дерев, що складаються з вершин та відповідно). Процес продовжується поки не отримаємо єдине дерево (кістяковим деревом найменшої довжини (вартості)), яке охоплює всі  вершин, і не містить циклів.

Знаходження мінімального кістякового дерева використовуючи алгоритм Крускала — приклад:

Використовуючи алгоритм Крускала, побудувати дерево мінімальної вартості для неорієнтованого графа наступного вигляду:

Алгоритм Крускала приклад

Неорієнтований граф задачі

Зазначимо, що у нашому прикладі алгоритм Крускала починається з шести дерев, кожне з яких містить по одній вершині. Отже, на першому кроці, вибираємо ребро найменшої довжини, що зв'язує два з них. В результаті будемо мати одне дерево, яке складається з вершин «1» і «3» та ребра та чотири дерева, які містять вершини «2», «4», «5» та «6» відповідно.

На наступному кроці, скориставшись ребром , знову-таки, об'єднаємо два дерева, що складаються з однієї вершини  (вершини «4» та «6»). Як наслідок, отримаємо два дерева по дві вершини та одному ребру, і два дерева, які складаються з однієї вершини.

Алгоритм Крускала приклад

Дерево найкоротших шляхів

Продовжуючи ітераційни процес далі, на п'ятому кроці, отримаємо єдине дерево, яке охоплює всі шість вершин і в якому сума довжин ребер мінімальна:

  1. Крок №3: ребро  найкоротше серед тих що залишились і таке, що не створює цикл; дерева, яким належать вершини «2» та «5», зливаються (за його допомогою) в єдине.
  2. Крок №4: ребро найкоротше серед тих що залишились і таке, що не створює цикл; дерева, яким належать вершини «3» та «6» зливаються в єдине.
  3. Крок №5: ребро  найкоротше серед тих що залишились і таке, що не створює цикл; дерева, яким належать вершини «2» та «3» зливаються в єдине.
Блок-схема алгоритму Крускала

Алгоритм Крускала блок-схема

Матеріал був корисним, поділись в соціальних мережах:
Якщо тобі сподобалась дана тема, залиш свій коментар