Графы. Алгоритм Прима

Опубликовано 12.12.2012 | Автор: admin

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

Чтобы понять что такое ребро, вес смотрим рисунок

Вершины графа на этом рисунке обозначены кружками.
Номер вершины — цифра в кружке.
Ребро — отрезок, соединяющий вершины
Вес ребра — синяя цифра над отрезком.

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

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

• На рисунке изображено мысленное дополнение неполного графа до полного.

Чтобы искать максимальную оценку маршрута, нужно взять минимальное значение, т.е. это будет (минус Бесконечность), но я буду опсиывать алогритм для минимальной оценки.

Чтобы компьютер смог использовать алгоритм на графе, нужно этот граф перевести в понятный компьютеру вид — в цифры. Чтобы это сделать, составляют или матрицу смежности или матрицу инцендентности.

Показать алгоритм заполнения матрицы смежности

Я уже описывал как создавать матрицу смежности, но не поленюсь и даже создам анимированный рисунок, на котором показан алгоритм заполнения такой матрицы.

Могу пояснить, что 1-2 — обозначает первую колонку второй столбец и далее по аналогии
Я назвал ребра ребрами, но в контексте алгоритма, изображенного на рисунке их можно назвать дугами.

Созданная матрица смежности для нарисованного графа

∞      10      ∞      ∞
10     ∞       9      20
∞      9        ∞      15
∞      20      15     ∞

В дальнейшем под бесконечностью будет число, которое компилятор воспринимает как максимальное.

C++

unsigned int inf=-1; // Беззнаковый -1 = максимальное число для типа int

1	unsigned int inf=-1; // Беззнаковый -1 = максимальное число для типа int

На разных машиеах int может иметь разный размер, поэтому на одном ПК может быть один максимум, на другом другой, но это к сведению, а к теме не относится.

А к теме относиться понимание алгоритма Прима. Если вы его понимаете — то это просто великолепно и значит своими силами вполне способны написать программу для его выполнения, если же не понимаете, то придется помучаться и понять теорию.

Для лучшего понимания этой статьи хорошо бы знать, что такое остовное дерево Минимальное остовное дерево
Вот замечательно показанные примеры теоритического выполнения некоторых алгоритмов на графах. Среди этих примеров есть пример работы алгоритма Прима Минимальные остовные деревья
Если кому-то покажется, что этого мало, то вот мое личное художество, анимированный рисунок, только немного не того графа, который я описывал выше. Я посчитал, что тот граф не очень подходит для иллюстрации расчетов, поэтому немного изменил веса ребер.

Показать псевдокод

C++

MST-PRIM(G, w, r) for each u  V [G] do key[u] ← ∞ π[u] ← NIL key[r] ← 0 Q ← V [G] while Q ≠ Ø do u ← EXTRACT-MIN(Q) for each v  Adj[u] do if v  Q and w(u, v) < key[v] then π[v] ← u key[v] ← w(u, v)

1 2 3 4 5 6 7 8 9 10 11 12

MST-PRIM(G, w, r) for each u  V [G] do key[u] ← ∞ π[u] ← NIL key[r] ← 0 Q ← V [G] while Q ≠ Ø do u ← EXTRACT-MIN(Q) for each v  Adj[u] do if v  Q and w(u, v) < key[v] then π[v] ← u key[v] ← w(u, v)

А вот пример реализации алгоритма Прима, правда пример не мой, поэтому я особо его не смогу прокомментировать. Но, несмотря на это, этот пример не должен быть очень сложным для его понимания.

C++

#include<conio.h> #include<iostream.h> int a,b,u,v,n,i,j,ne=1; int visited[10]={0},min,mincost=0,cost[10][10]; void main() { int path[100]={0}; //В этот массив будут записываться вершины, по которым составиться путь int path_index=0; clrscr(); cout<<"Введи количество вершин "; cin>>n; cout<<"Введи матрицу смежности\n"; for(i=1;i<=n;i++) for(j=1;j<=n;j++) { cin>>cost[i][j]; if(cost[i][j]==0) cost[i][j]=999; //999 - это что-типа бесконечности. Должно быть больше чем значения веса каждого из ребер в графе } visited[1]=1; cout<<"\n"; while(ne < n) { for(i=1,min=999;i<=n;i++) for(j=1;j<=n;j++) if(cost[i][j]< min) if(visited[i]!=0) { min=cost[i][j]; a=u=i; b=v=j; } if(visited[u]==0 || visited[v]==0) { path[path_index]=b; path_index++; //cout<<"\n "<<ne++<<" "<<a<<" "<<b<<min; //Можно вывести так ne++; //если строчку выше раскомментировать - эту закомментировать mincost+=min; visited[b]=1; } cost[a][b]=cost[b][a]=999; } cout<<"\n"; cout<<1<<" --> "; for (int i=0;i<n-1;i++) { cout<<path[i]; if (i<n-2) cout<<" --> "; } cout<<"\n Минимальная стоимость "<<mincost; cin.get(); cin.get(); }

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67

#include<conio.h> #include<iostream.h>   int a,b,u,v,n,i,j,ne=1; int visited[10]={0},min,mincost=0,cost[10][10];   void main() { int path[100]={0}; //В этот массив будут записываться вершины, по которым составиться путь int path_index=0;   clrscr(); cout<<"Введи количество вершин  "; cin>>n; cout<<"Введи матрицу смежности\n";       for(i=1;i<=n;i++) for(j=1;j<=n;j++) { cin>>cost[i][j]; if(cost[i][j]==0) cost[i][j]=999; //999 - это что-типа бесконечности. Должно быть больше чем значения веса каждого из ребер в графе } visited[1]=1; cout<<"\n";   while(ne < n) { for(i=1,min=999;i<=n;i++) for(j=1;j<=n;j++) if(cost[i][j]< min) if(visited[i]!=0) { min=cost[i][j]; a=u=i; b=v=j; } if(visited[u]==0 || visited[v]==0) { path[path_index]=b; path_index++; //cout<<"\n "<<ne++<<"  "<<a<<"  "<<b<<min; //Можно вывести так ne++; //если строчку выше раскомментировать - эту закомментировать mincost+=min; visited[b]=1;   } cost[a][b]=cost[b][a]=999; }     cout<<"\n";   cout<<1<<" --> "; for (int i=0;i<n-1;i++) {   cout<<path[i];   if (i<n-2) cout<<" --> "; }   cout<<"\n Минимальная стоимость  "<<mincost;     cin.get(); cin.get(); }

Пример работы

Отличная статья13 Плохая статья4

Рубрика: Без рубрики

21 комментарий на «“Графы. Алгоритм Прима”»

1. Евгений:

   04.02.2015 в 6:52 пп

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

   Ответить
   • Арсений:

     18.12.2016 в 6:04 пп

     Потому что прямого пути из 2 в 2 нет. Матрица инцидентности подразумевает под собой написание именно прямых путей.

     Ответить
2. Фелагунд:

   13.01.2016 в 1:45 дп

   Условие if(visited[i]!=0) во вложенном цикле при поиске ребра с наименьшим весом лучше переместить во внешний цикл сразу после for(i=1,min=999;i<=n;i++)

   Гораздо оптимальней

   Ответить
3. Карим:

   06.03.2016 в 1:59 пп

   в коде есть недароботки, например вы не определяете возможно ли вообще соединить все вершины или нет

   1

   Ответить
4. Михаил:

   11.10.2016 в 11:28 дп

   У меня выдает ошибку «С2872 неоднозначный символ min». Если изменить имя переменной, то я не знаю, где какую вставить… Что посоветуете?

   Ответить
   • admin:

     11.10.2016 в 3:14 пп

     Заменить все min на min_

     Это произошло, потому что в STL есть функция min, которая сравнивает два значения и возвращает наименьшее. А в коде использована одноимённая переменная. Компилятор поэтому не врубился. В этих случаях просто меняются имена переменных.

     Ответить
     • Михаил:

       20.10.2016 в 5:17 пп

       действительно! Но теперь не могу понять, почему была проблема. Можете объяснить? И почему «_» все решило?

       Ответить
       • Олег:

         03.12.2017 в 3:22 пп

         Ну, компилятору не понятно имел ты в виду min() как функцию или как переменную — вот он и пишет о неоднозначности. Добавлением «_» вы четко отделяете имя переменной от функции.

         Ответить
5. Михаил:

   20.10.2016 в 5:18 пп

   Все. Сам разобрался, почему так было ) Спасибо за помощь! Давно на этом сайте занимаюсь.

   Ответить
6. Илья:

   06.12.2016 в 8:31 пп

   Сколько максимально вершин можно вбить?

   1

   Ответить
   • admin:

     06.12.2016 в 10:40 пп

     Я не знаю.

     2

     1

     Ответить
7. Аноним:

   10.12.2016 в 5:48 пп

   не правильно выводит для теста:

   4

   0 1 0 0

   0 0 2 0

   0 0 0 5

   4 0 0 0

   выводит 8, а должен 7

   не все варианты смотрит

   Ответить
8. Shel:

   15.12.2016 в 9:53 пп

   Может быть потому что у вас не матрица смежности, не?))

   Ответить
   • Олег:

     03.12.2017 в 3:26 пп

     Там что-то типа опечатки. Скорее всего имелась в виду матрица расстояний, ибо в том же примере вводятся не нули и единицы, как в матрице смежности, а вес ребёр

     Ответить
9. alalala:

   18.11.2017 в 7:27 пп

   почему все переменные глобальные? что за жесть?

   Ответить
10. big_boss:

    15.02.2021 в 8:43 пп

    Здравствуйте. Скажите пожалуйста блок-схема, которая содержится по ссылке http://www.mathros.net.ua/algorytm-pryma.html подходит для размещенной Вами программы или нет? Блок -схему нашел, а с реализацией не очень получается.

    Ответить
    • admin:

      17.02.2021 в 11:10 дп

      Не могу точно ответить. Я не знаком с блок-схемами, чтобы что-то о них утверждать.

      Ответить
      • big_boss:

        17.02.2021 в 8:53 пп

        Понятно. Спасибо за то, что ответили на мой комментарий. Придется пытаться реализовать программу самому.

        Ответить
11. Дима:

    23.02.2021 в 3:38 пп

    cannot bind ‘std::istream {aka std::basic_istream}’ lvalue to ‘std::basic_istream&&’
    In file included from /usr/include/c++/4.9/iostream: Выдает данную ошибку если ввести в код.

    Ответить
    • admin:

      23.02.2021 в 7:46 пп

      1. Какой компилятор используете?
      2. Какой код туда пишете?

      Код, приведённый на этой странице, написан для старых компиляторов, поэтому ему нужны некоторые изменения, чтобы он работал в современных. Но я понятия не имею, что и как Вы делаете, поэтому не могу сказать, почему возникает ошибка.

      У меня работает:

      C++

      //Visual Studio C++ #include <iostream> using std::cout; using std::cin; int a, b, u, v, ne = 1; int visited[10] = {0}, min = 0, mincost=0, cost[10][10]; int main() { int n = 0; int path[100] = {0}; //В этот массив будут записываться вершины, по которым составиться путь int path_index = 0; //clrscr(); cout << "Введи количество вершин "; cin >> n; cout << "Введи матрицу смежности\n"; for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++){ cin >> cost[i][j]; if(cost[i][j] == 0) cost[i][j] = 999; //999 - это что-типа бесконечности. Должно быть больше чем значения веса каждого из ребер в графе } } visited[1] = 1; cout << "\n"; while(ne < n){ int min = 999; int i = 1; for(; i<=n; i++){ for(int j=1; j<=n; j++){ if(cost[i][j] < min){ if(visited[i] != 0) { min = cost[i][j]; a = u = i; b = v = j; } } } } if(visited[u] == 0 || visited[v] == 0) { path[path_index] = b; path_index++; //cout<<"\n "<<ne++<<" "<<a<<" "<<b<<min; //Можно вывести так ne++; //если строчку выше раскомментировать - эту закомментировать mincost+= min; visited[b] = 1; } cost[a][b] = cost[b][a] = 999; } cout << "\n"; cout << 1 << " --> "; for (int i=0; i<n-1; i++) { cout << path[i]; if (i < n-2) cout <<" --> "; } cout << "\n Минимальная стоимость " << mincost; }

      1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77

      //Visual Studio C++ #include <iostream>   using std::cout; using std::cin;   int a, b, u, v, ne = 1; int visited[10] = {0}, min = 0, mincost=0, cost[10][10];   int main() {     int n = 0; int path[100] = {0}; //В этот массив будут записываться вершины, по которым составиться путь int path_index = 0;   //clrscr(); cout << "Введи количество вершин  ";     cin >> n;      cout << "Введи матрицу смежности\n";           for(int i=1; i<=n; i++){         for(int j=1; j<=n; j++){             cin >> cost[i][j];             if(cost[i][j] == 0)                 cost[i][j] = 999; //999 - это что-типа бесконечности. Должно быть больше чем значения веса каждого из ребер в графе         }     }      visited[1] = 1; cout << "\n";           while(ne < n){         int min = 999;         int i = 1;         for(; i<=n; i++){                               for(int j=1; j<=n; j++){                 if(cost[i][j] < min){                      if(visited[i] != 0)                      {                         min = cost[i][j];                         a = u = i;                         b = v = j;                      }                 }             }                      }                      if(visited[u] == 0 || visited[v] == 0) {             path[path_index] = b;             path_index++;             //cout<<"\n "<<ne++<<"  "<<a<<"  "<<b<<min; //Можно вывести так             ne++; //если строчку выше раскомментировать - эту закомментировать             mincost+= min;             visited[b] = 1;         }              cost[a][b] = cost[b][a] = 999; }   cout << "\n";   cout << 1 << " --> "; for (int i=0; i<n-1; i++) {   cout << path[i];   if (i < n-2) cout <<" --> "; }   cout << "\n Минимальная стоимость  " << mincost; }

      Если использовать using namespace std, то с переменной min могут возникнуть проблемы, нужно будет её называть иначе.

      Ответить
12. doni1:

    10.11.2021 в 2:39 пп

    как сделать чтобы виводило макс стоимость ?

    Ответить