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

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

Розглянемо деякий неорієнтований граф, і спробуємо побудувати для нього дерево мінімальної вартості за вище розглянутим алгоритмом.

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

Крок 1: вибираємо ребро найменшої вартості: 1−3=1. В результаті отримаємо одне дерево, яке складається з двох вершин і одного ребра (на малюнку позначено зеленим кольором) та 4 дерева, які містять по одній вершині.

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

Крок 2: на другому кроці об'єднаємо два дерева ребром 4−6=2 (є найменшої довжини). Отримаємо два дерева по дві вершини та одному ребру, і два дерева, які складаються з однієї вершини.

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

Крок 3: на третьму кроці обєднаємо два дерева ребром 2−4=3. Результатом даного кроку буде три дерева, які складаються з наступних компонентів: дві вершини і одне ребро.

algoritm_kryskala4

Крок 4: знову об'єднюємо два дерева ребром 3−6=4. Отримуємо:

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

Крок 5: на останньому кроці використаємо ребро 2−3=5 і з його допомогою об'єднаємо два дерева. В резельтаті отримуємо остаточне  дерево (мінімальної вартості), яке зображено на наступному малюнку.

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

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

Якщо тобі сподобалась дана тема, залиш свій коментар