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

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

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

algoritm_prima1

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

algoritm_prima2

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

algoritm_prima3

Наступною верштною, яку ми добавимо до дерева буде вершина під номуром 4, бо саме вона з'єднана ребром найменшої довжини з вершинами, що вже належать дереву мінімальної вартості, а саме з вершиною №6.

algoritm_prima4

І так далі, проводимо аналогічні дії, поки всі вершини вхідного графа не будуть включені до дерева мінімальної вартості. У підсумку отримаємо граф.

algoritm_prima5

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

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