Алгоритм Прима такий інший метод пошуку мінімального остовного дерева в мережі. Його можна використовувати, коли інформацію для мережі подано у вигляді графіка або матриці.
В інформатиці алгоритм Прима є жадібний алгоритм, який знаходить мінімальне остовне дерево для зваженого неорієнтованого графа. Це означає, що він знаходить підмножину ребер, яка утворює дерево, що включає кожну вершину, де загальна вага всіх ребер у дереві мінімізована.
Часова складність алгоритму Прима становить O(V2) за допомогою матриці суміжності та O((V +E) log V) за допомогою списку суміжності, де V — кількість вершин, а E — кількість ребер у графі. Складність простору становить O(V+E) для черги пріоритетів і O(V2) для подання матриці суміжності.
Мінімальне охоплююче дерево (MST) або охоплююче дерево мінімальної ваги є тоді остовне дерево, вага якого менша або дорівнює вазі будь-якого іншого остовного дерева. Загалом, будь-який неорієнтований граф (не обов’язково зв’язаний) має мінімальний охоплюючий ліс, який є об’єднанням мінімальних охоплюючих дерев для його компонентів.
Таблична форма алгоритмів Прима має наступні кроки:
- Виберіть будь-яку вершину (місто). Закресліть його рядок. …
- Перекресліть рядок із щойно виділеним значенням. Повторіть крок 1. …
- Коли всі рядки викреслені, прочитайте з’єднання.
Алгоритм Прима можна просто реалізувати за допомогою матриця суміжності або представлення графа списку суміжності, а щоб додати ребро з мінімальною вагою, потрібен лінійний пошук масиву ваг. Це вимагає O(|V|2) часу роботи.