mafulechka
mafulechkaШілде 29, 2019, 2:57 Т.Ж.

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

Прим алгоритмі - кіріс ретінде графикті қабылдайтын және әрбір төбесін қамтитын ағашты құрайтын, сондай-ақ графиктен құруға болатын барлық ағаштар арасындағы салмақтардың ең аз сомасына ие болатын сол графиктің жиектерінің ішкі жиынын табатын ең аз ауқымды ағаш алгоритмі. .


Прим алгоритмі қалай жұмыс істейді

Ол жаһандық оптимумды табу үмітімен жергілікті оптимумды табатын «ашкөз» алгоритмдер деп аталатын алгоритмдер класына жатады.

Біз бір шыңнан бастаймыз және мақсатымызға жеткенше ең аз салмағы бар жиектерді қоса береміз.

Прим алгоритмін енгізу қадамдары келесідей:

  1. Еркін шыңы бар ең аз таралатын ағашты инициализациялаңыз.
  2. Ағашты жаңа шыңдарға қосатын барлық жиектерді табыңыз, минимумды табыңыз және оны ағашқа қосыңыз.
  3. Ең аз таралу ағашын алғанша 2-қадамды қайталаңыз.

Prima алгоритмінің мысалы

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

Прим алгоритмінің псевдокоды U және VU шыңдарының екі жиынын қалай жасайтынымызды көрсетеді. U кірген шыңдардың тізімін және VU кірмеген шыңдардың тізімін қамтиды. Бір-бірден біз шыңдарды VU жиынынан U жиынына жылжытамыз, жиекті ең аз салмақпен байланыстырамыз.

С++ тілінде Прим алгоритмін енгізу

Төмендегі бағдарлама Прим алгоритмін 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

Прим алгоритмі Краскалға қарсы

Крускал алгоритмі - MST графигін табу үшін басқа логиканы пайдаланатын тағы бір танымал минималды ағаш алгоритмі. Жоғарыдан бастаудың орнына, Крускал алгоритмі барлық жиектерді төмен салмақтан жоғары салмаққа дейін сұрыптайды және цикл жасайтын жиектерді елемей, ең төменгі жиектерді қосуды жалғастырады.

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

Ол саған ұнайды ма? Әлеуметтік желілерде бөлісіңіз!

Пікірлер

Тек рұқсаты бар пайдаланушылар ғана пікір қалдыра алады.
Кіріңіз немесе Тіркеліңіз
AD

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

  • Нәтиже:50ұпай,
  • Бағалау ұпайлары-4
m
  • molni99
  • Қаз. 26, 2024, 1:37 Т.Ж.

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

  • Нәтиже:80ұпай,
  • Бағалау ұпайлары4
m
  • molni99
  • Қаз. 26, 2024, 1:29 Т.Ж.

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

  • Нәтиже:20ұпай,
  • Бағалау ұпайлары-10
Соңғы пікірлер
ИМ
Игорь МаксимовҚар. 22, 2024, 11:51 Т.Ж.
Django - Оқулық 017. Теңшелген Django кіру беті Добрый вечер Евгений! Я сделал себе авторизацию аналогичную вашей, все работает, кроме возврата к предидущей странице. Редеректит всегда на главную, хотя в логах сервера вижу запросы на правильн…
Evgenii Legotckoi
Evgenii LegotckoiҚаз. 31, 2024, 2:37 Т.Қ.
Django - Сабақ 064. Python Markdown кеңейтімін қалай жазуға болады Добрый день. Да, можно. Либо через такие же плагины, либо с постобработкой через python библиотеку Beautiful Soup
A
ALO1ZEҚаз. 19, 2024, 8:19 Т.Ж.
Qt Creator көмегімен fb3 файл оқу құралы Подскажите как это запустить? Я не шарю в программировании и кодинге. Скачал и установаил Qt, но куча ошибок выдается и не запустить. А очень надо fb3 переконвертировать в html
ИМ
Игорь МаксимовҚаз. 5, 2024, 7:51 Т.Ж.
Django - Сабақ 064. Python Markdown кеңейтімін қалай жазуға болады Приветствую Евгений! У меня вопрос. Можно ли вставлять свои классы в разметку редактора markdown? Допустим имея стандартную разметку: <ul> <li></li> <li></l…
d
dblas5Шілде 5, 2024, 11:02 Т.Ж.
QML - Сабақ 016. SQLite деректер қоры және онымен QML Qt-та жұмыс істеу Здравствуйте, возникает такая проблема (я новичок): ApplicationWindow неизвестный элемент. (М300) для TextField и Button аналогично. Могу предположить, что из-за более новой верси…
Енді форумда талқылаңыз
m
moogoҚар. 22, 2024, 7:17 Т.Ж.
Mosquito Spray System Effective Mosquito Systems for Backyard | Eco-Friendly Misting Control Device & Repellent Spray - Moogo ; Upgrade your backyard with our mosquito-repellent device! Our misters conce…
Evgenii Legotckoi
Evgenii LegotckoiМаусым 24, 2024, 3:11 Т.Қ.
добавить qlineseries в функции Я тут. Работы оень много. Отправил его в бан.
t
tonypeachey1Қар. 15, 2024, 6:04 Т.Ж.
google domain [url=https://google.com/]domain[/url] domain [http://www.example.com link title]
NSProject
NSProjectМаусым 4, 2022, 3:49 Т.Ж.
Всё ещё разбираюсь с кешем. В следствии прочтения данной статьи. Я принял для себя решение сделать кеширование свойств менеджера модели LikeDislike. И так как установка evileg_core для меня не была возможна, ибо он писался…

Бізді әлеуметтік желілерде бақылаңыз