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

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

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

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

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

Читати повністю

Алгоритм Прима

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

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

algoritm_prima1

В якості початкової вибираємо будь-яку вершину графа, нехай вона буде під номером 1. Вершина №1 з'єднана з вершинами  №2, №3 і №4. Вибираємо серед них ту, яка має з вершиною 1 ребро найменшої довжини. В нашому прикладі такою є вершина 3 (довжина ребра рівна одиниці). Додаємо її до дерева.

Читати повністю