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

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

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

Как работает алгоритм Прима

Он подпадает под класс алгоритмов, называемых «жадными» алгоритмами , которые находят локальный оптимум в надежде найти глобальный оптимум.

Мы начинаем с одной вершины и продолжаем добавлять ребра с наименьшим весом, пока не достигнем нашей цели.

Шаги для реализации алгоритма Прима следующие:

  1. Инициализируйте минимальное остовное дерево с произвольно выбранной вершиной.
  2. Найдите все ребра, которые соединяют дерево с новыми вершинами, найдите минимум и добавьте его в дерево.
  3. Продолжайте повторять шаг 2, пока не получите минимальное остовное дерево.

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

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

Псевдокод для алгоритма Прима показывает, как мы создаем два набора вершин U и V-U. U содержит список вершин, которые были посещены, а V-U – список вершин, которые не были посещены. Один за другим мы перемещаем вершины из набора V-U в набор 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 графа. Вместо того, чтобы начинать с вершины, алгоритм Краскала сортирует все ребра от малого веса к большему и продолжает добавлять самые нижние ребра, игнорируя те ребра, которые создают цикл.

Virtual hosting with 10 percent discount
Virtual hosting with 10 percent discount
EVILEG offers reliable hosting with a 10% discount for virtual hosting and 5% for VPS
Support the author Donate

Comments

Only authorized users can post comments.
Please, Log in or Sign up
D
Aug. 16, 2019, 11:58 a.m.
Damir

C++ - Тест 003. Условия и циклы

  • Result:92points,
  • Rating points8
D
Aug. 16, 2019, 11:46 a.m.
Damir

C++ - Test 005. Structures and Classes

  • Result:75points,
  • Rating points2
u
Aug. 14, 2019, 1:55 p.m.
unrealproro

C++ - Test 005. Structures and Classes

  • Result:83points,
  • Rating points4
Last comments
Aug. 19, 2019, 6:41 a.m.
Andrej Jankovich

это проблема дистрибутива, попробуйте установить через пакетный менеджер snap Суть проблемы: libQt5Core которая лежит в дистрибутиве требует версию glibc >= 2.25 у вас видимо …
b
Aug. 18, 2019, 5:09 a.m.
bbb116

cqtdeployer /home/aleks/CQtDeployer/bin/cqtdeployer: /lib/x86_64-linux-gnu/libc.so.6: version `GLIBC_2.25' not found (required by /home/aleks/CQtDeployer/lib/libQt5Core.so.5) linux mint …
D
Aug. 17, 2019, 8:04 a.m.
Damir

github ChekableTView Правой групповая смена значения при перетаскивании левой как обычно.
Aug. 16, 2019, 12:03 p.m.
Evgenij Legotskoj

Потому, что в минуте 60 секунд
Aug. 16, 2019, 11:16 a.m.
Dmitrij

а почему делитель 60000, а не 1000?
Now discuss on the forum
Aug. 20, 2019, 12:17 p.m.
Evgenij Legotskoj

Добрый день. Вы делаете некорректную попытку создать исключение. Исключения генерируются кодом, то есть любое исключение, которое вы перехватываете, всегда генерируется оператором th…
Aug. 20, 2019, 11:44 a.m.
Evgenij Legotskoj

Ну вообще это я вам не решение вашей задачи кинул, а просто как пример... Регулярку вам надо было бы самому придумать.. Ну вот так будет работать TextField { validator: RegExpValida…
Aug. 20, 2019, 8:04 a.m.
IscanderChe

Ещё раз здравствуйте. Собираю Qt-проект с помощью CMake. Применяю к полученному exe-файлу windeployqt. В результате подцепляются почему-то dll-ки, оканчивающиеся в наименованиях на "d": Qt…
Aug. 20, 2019, 7:46 a.m.
IscanderChe

Да, с таргетом тоже работает. Спасибо!
Aug. 20, 2019, 7:25 a.m.
Evgenij Legotskoj

вы можете испльзовать QList, просто помещайте туда QPair, будет примерно тоже самое. Просто QMap автоматически сортируется по ключу. QList<QPair<QString, QString>> list_with_pair;…
Looking for a Job?
14,000.00 руб. - 40,000.00 руб.
Разработчик Qt
Annino, Moscow Oblast, Russia
5,000.00 руб. - 15,000.00 руб.
Дизайнер
Moskovskiy, Moscow, Russia
25,000.00 руб. - 30,000.00 руб.
Разработчик Qt/C++
Barnaul, Altai Krai, Russia

For registered users on the site there is a minimum amount of advertising

EVILEG
About
Services
© EVILEG 2015-2019
Recommend hosting TIMEWEB