Алгоритм Prima

Дерево, Алгоритм, Tree

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

Як працює алгоритм Пріма

Він підпадає під клас алгоритмів, які називаються «жадібними» алгоритмами, які знаходять локальний оптимум, сподіваючись знайти глобальний оптимум.

Ми починаємо з однієї вершини і продовжуємо додавати ребра з найменшою вагою, доки не досягнемо нашої мети.

Кроки для реалізації алгоритму Прима наступні:

1. Ініціалізуйте мінімальне остовне дерево з довільно обраною вершиною.
2. Знайдіть усі ребра, які з'єднують дерево з новими вершинами, знайдіть мінімум і додайте його до дерева.
3. Продовжуйте повторювати крок 2, доки не отримаєте мінімальне остовне дерево.

Приклад алгоритму Prima

Алгоритм Пріма. Псевдокод.

Псевдокод для алгоритму Прима показує, як ми створюємо два набори вершин U та VU. U містить список вершин, що були відвідані, а VU – список вершин, що не були відвідані. Один за одним ми переміщуємо вершини з набору VU до набору U, з'єднуючи ребро з найменшою вагою.

Реалізація алгоритму Прима в C++

Програма нижче реалізує алгоритм Прима у C++. Незважаючи на те, що використовується матриця суміжності для представлення графа, цей алгоритм може бути реалізований з використанням списку суміжності для підвищення його ефективності.

#include <iostream>
#include <cstring>
using namespace std;
 
#define INF 9999999
 
// number of vertices in grapj
#define V 5
 
// create a 2d array of size 5x5
//for adjacency matrix to represent graph
 
int G[V][V] = {
  {0, 9, 75, 0, 0},
  {9, 0, 95, 19, 42},
  {75, 95, 0, 51, 66},
  {0, 19, 51, 0, 31},
  {0, 42, 66, 31, 0}
};
 
int main () {
 
  int no_edge;            // number of edge
 
  // create a array to track selected vertex
  // selected will become true otherwise false
  int selected[V];
 
 // set selected false initially
  memset (selected, false, sizeof (selected));
 
 // set number of edge to 0
  no_edge = 0;
 
  // the number of egde in minimum spanning tree will be
  // always less than (V -1), where V is number of vertices in
  //graph
 
  // choose 0th vertex and make it true
  selected[0] = true;
 
  int x;            //  row number
  int y;            //  col number
 
  // print for edge and weight
  cout << "Edge" << " : " << "Weight";
  cout << endl;
  while (no_edge < V - 1) {
 
  //For every vertex in the set S, find the all adjacent vertices
  // , calculate the distance from the vertex selected at step 1.
  // if the vertex is already in the set S, discard it otherwise
  //choose another vertex nearest to selected vertex  at step 1.
 
      int min = INF;
      x = 0;
      y = 0;
 
      for (int i = 0; i < V; i++) {
        if (selected[i]) {
            for (int j = 0; j < V; j++) {
              if (!selected[j] && G[i][j]) { // not in selected and there is an edge
                  if (min > G[i][j]) {
                      min = G[i][j];
                      x = i;
                      y = j;
                  }
 
              }
          }
        }
      }
      cout << x <<  " - " << y << " :  " << G[x][y];
      cout << endl;
      selected[y] = true;
      no_edge++;
    }
 
  return 0;
}

Запустивши наведений вище код, ми отримаємо висновок у вигляді:

Edge : Weight
0 - 1 :  9
1 - 3 :  19
3 - 4 :  31
3 - 2 :  51

Алгоритм Прима vs Фарбала

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