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

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

We recommend hosting TIMEWEB
We recommend hosting TIMEWEB
Stable hosting, on which the social network EVILEG is located. For projects on Django we recommend VDS hosting.
Support the author Donate

Comments

Only authorized users can post comments.
Please, Log in or Sign up
Looking for a Job?
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

DP
Oct. 19, 2019, 1:45 a.m.
Dmitrij Pasynkov

C++ - Test 001. The first program and data types

  • Result:26points,
  • Rating points-10
AS
Oct. 18, 2019, 1:27 p.m.
Artem Sergeevich

C++ - Test 001. The first program and data types

  • Result:13points,
  • Rating points-10
MB
Oct. 18, 2019, 11:05 a.m.
Mihail Bulatov

C++ - Test 001. The first program and data types

  • Result:86points,
  • Rating points6
Last comments
Oct. 17, 2019, 2:17 a.m.
Evgenij Legotskoj

Используем, там где требуется :)
MP
Oct. 17, 2019, 2:15 a.m.
Mikhail Petrov

Совет: подключайте ресурсы динамически. Используйте Resource Compiler: https://doc.qt.io/qt-5/rcc.html
Oct. 16, 2019, 6:45 a.m.
Evgenij Legotskoj

Если это не чистой воды спам, а по делу, то без проблем. Но в таком случае лучше создавайте отдельный вопрос на форуме . При создании вопроса есть поле, в котором можно указать статью…
KK
Oct. 16, 2019, 6:39 a.m.
Kirill Kirilych

А тут можно ссылки на сторонний ресурс показывать? Нашёл на habr похожую статью, только там чуток отличается код и про локальный сервер написано, нужно чтоб кто то понимающий посмотрел и своё …
Now discuss on the forum
Oct. 18, 2019, 1:30 p.m.
Evgenij Legotskoj

Добрый день. У вас там пробелы находятся в тексте, поэтому и не может сконвертировать. фукция map применяет float ко все символам в каждой строке. В том числе и к символам пробела. А пробе…
Oct. 17, 2019, 10:31 a.m.
Ruslan Volshebnik

Я вас понял) Спасибо ещё раз. Вы помогли мне во всём разобраться.
t
Oct. 17, 2019, 4:13 a.m.
tupo_chel

И тебе спасибо за помощь)
Oct. 17, 2019, 2:14 a.m.
Evgenij Legotskoj

Добрый день. Ну да, этот вариант жизнеспособен. Есть только один момент, который вам необходимо понимать в данном случае. И чего в этой статье или нет, или сказано как-то совсем вскользь, …
EVILEG
About
Services
© EVILEG 2015-2019
Recommend hosting TIMEWEB