mafulechka
mafulechka29 июля 2019 г. 2:57

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

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


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

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

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

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

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

Рекомендуем хостинг TIMEWEB
Рекомендуем хостинг TIMEWEB
Стабильный хостинг, на котором располагается социальная сеть EVILEG. Для проектов на Django рекомендуем VDS хостинг.

Вам это нравится? Поделитесь в социальных сетях!

Комментарии

Только авторизованные пользователи могут публиковать комментарии.
Пожалуйста, авторизуйтесь или зарегистрируйтесь
AD

C++ - Тест 004. Указатели, Массивы и Циклы

  • Результат:50баллов,
  • Очки рейтинга-4
m
  • molni99
  • 25 октября 2024 г. 22:37

C++ - Тест 004. Указатели, Массивы и Циклы

  • Результат:80баллов,
  • Очки рейтинга4
m
  • molni99
  • 25 октября 2024 г. 22:29

C++ - Тест 004. Указатели, Массивы и Циклы

  • Результат:20баллов,
  • Очки рейтинга-10
Последние комментарии
i
innorwall14 ноября 2024 г. 8:42
Как Копировать Файлы в Linux If only females relatives with DZ offspring were considered these percentages were 23 order priligy online uk
i
innorwall14 ноября 2024 г. 6:09
Qt/C++ - Урок 068. Hello World с использованием системы сборки CMAKE в CLion ditropan pristiq dosing With the Yankees leading, 4 3, Rivera jogged in from the bullpen to a standing ovation as he prepared for his final appearance in Chicago buy priligy pakistan
i
innorwall14 ноября 2024 г. 1:05
EVILEG-CORE. Использование Google reCAPTCHA 2001; 98 29 34 priligy buy
i
innorwall14 ноября 2024 г. 1:00
PyQt5 - Урок 007. Работаем с QML QtQuick (Сигналы и слоты) priligy 30mg Am J Obstet Gynecol 171 1488 505
Сейчас обсуждают на форуме
i
innorwall14 ноября 2024 г. 0:39
добавить qlineseries в функции priligy amazon canada 93 GREB1 protein GREB1 AB011147 6
i
innorwall11 ноября 2024 г. 7:55
Всё ещё разбираюсь с кешем. priligy walgreens levitra dulcolax carbs The third ring was found to be made up of ultra relativistic electrons, which are also present in both the outer and inner rings
9
9Anonim25 октября 2024 г. 6:10
Машина тьюринга // Начальное состояние 0 0, ,<,1 // Переход в состояние 1 при пустом символе 0,0,>,0 // Остаемся в состоянии 0, двигаясь вправо при встрече 0 0,1,>…
ИМ
Игорь Максимов3 октября 2024 г. 1:05
Реализация навигации по разделам Спасибо Евгений!

Следите за нами в социальных сетях