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

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

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

algoritm_prima1

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

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

Знаходження дерева мінімальної вартості за алгоритмом Прима на Delphi(1)

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

14

Запустимо проект на виконання, в результаті на екрані монітора появиться форма наступного виду:

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