Многу процеси и настани вклучуваат разгледување на множества од елементи и извршување на операции врз нив - како нивно спојување или откривање дали некои елементи припаѓаат на исто множество или не. На пример, можеме да разгледуваме множества од предмети, множества од лица, множества од локации (проверка дали тие припаѓаат на ист сопственик, или купување и со тоа спојување на повеќе локации кои претходно припаѓале на разни лица), итн.

Во продолжение, ќе се запознаеме со структура која ни овозможува извршување на две операции: спојување на множества, и откривање каде припаѓа одреден елемент (со тоа, на пример, ќе можеме да провериме дали два елемента припаѓаат на исто множество). Иако, пред се, ќе се фокусираме на разгледување на темиња (како да зборуваме за графови), структурата која ќе ја видиме може да се користи за множества од било какви елементи. Сепак, разгледувањето на елементите како тие да се темиња од некој граф ќе ни овозможи полесно да разбереме за што се работи, бидејќи самите множества ќе можеме едноставно да ги претставиме и графички.

Имплементација

Да речеме дека имаме N елементи, и сите тие припаѓаат на посебни множества – т.е., нека имаме N множества, каде што во секое множество имаме по еден елемент. Овие множества може да претставуваат луѓе, предмети, итн. Податочната структура која што ќе ја видиме во продолжение (и алгоритмите кои ќе ги вршиме врз неа), ни овозможува овие множества да ги спојуваме (со помош на функција union), како и да откриеме дали два елемента припаѓаат на исто множество (со помош на функција find).

Имено, нека за секој елемент чуваме по една вредност која ќе означува кој е негов водач – т.е., доколку сакаме да откриеме на кое множество припаѓа некој елемент, тој или ќе знае да “ни каже” самиот (доколку тој е главниот елемент во множеството и нема водач), или ќе знае (рекурзивно) да “го праша” неговиот водач. Ова е целата идеја на податочната структура за работа со неповрзани множества (анг. disjoint-set), и алгоритмите за работа врз таа структура (анг., union-find). Во продолжение, ќе се обидеме да ги направиме овие алгоритми поефикасни - на начин што истите ќе функционираат во скоро-константно време О(1).

Како што можете да видите од сликата (каде што се претставени три множества), поврзување или спојување на две множества во едно (унија) се прави со едноставно додавање на нова врска од елемент од едното множество (водачот) до елемент од другото множество. Практично, како што го опишавме алгоритамот погоре, ова значи дека ќе обележиме дека нов водач на главниот елемент од едното множество е елемент од второто множество. Притоа, забележете дека повеќето елементи на сликата имаат свој водач, но некои немаат такво нешто. За овие елементи велиме дека истите се главен водач во множеството (или "корен", бидејќи структурата наликува на збир од повеќе дрва).

Во ред, но како да знаеме дали два елемента припаѓаат на исто множество? Ова е многу едноставно. Имено, потребно е само да видиме кој е главниот водач во множеството на едниот елемент, и да видиме кој е главниот водач во множеството на другиот елемент. Ако тие имаат ист главен водач (корен), тогаш тие два елемента веќе припаѓаат на истото множество. Практично, целта е да напишеме функција find(X), која што за даден елемент X ќе врати кој елемент е главниот водач во множеството на кое припаѓа X. Ако го направиме ова, многу едноставно ќе биде да провериме дали два елемента X и Y веќе припаѓаат на исто множество, користејќи ја споредбата find(X) == find(Y).

Пред да продолжиме понатаму, да видиме како можеме да го подобриме овој алгоритам, така што истиот ќе биде многу поефикасен. Притоа, ќе направиме две подобрувања - едно при откривањето, а друго при спојувањето. Имено, кај откривањето, веќе споменавме дека треба да го пронајдеме главниот водач во множеството. Но, елементот од кој почнуваме може да има водач кој што не е корен на множеството, па рекурзивно треба да продолжиме со движење се додека не дојдеме до главниот водач (практично, да видиме кој е водач на првиот елемент, па понатаму кој е водач на тој водач, итн). Првото подобрување кое што ќе го направиме е следното: кога некој ќе ја повика функцијата find(X), и алгоритамот рекурзивно ќе пронајде кој е главниот водач во множеството на кое припаѓа X, тогаш пред истиот да ја врати бараната вредност, ќе запишеме дека нов водач на X е коренот на множеството. Ова има две позитивни страни. Имено, при следниот повик на find(X), нема да има потреба рекурзивно да се движиме низ повеќе елементи, бидејќи водач на X е коренот на множеството, па алгоритамот ќе заврши многу побрзо. Слично на ова, сите елементи на кои што пак X им е водач (нека еден од нив е Y), сега ќе можат многу побрзо да дојдат до главниот водач во множеството, бидејќи рекурзивно тие треба да поминат низ само две нивоа Y -> X -> главниот водач.

Како што наведовме, второто подобрување се спроведува при спојувањето. Тука, потребно е само да имаме уште една вредност за секој елемент која ќе означува кој е неговиот ранг. Имено, целта која што сакаме да ја постигнеме со ова е, при спојување и разгледување на главниот водач на едното множество и главниот водач на другото множество, врската која што ќе ја поставиме да биде од оној водач со помал ранг до оној водач со поголем ранг. Притоа, рангот всушност ни помага да ја откриеме должината на најголемиот пат во дрвото (ако ја видите структурата и врските, секое множество наликува на дрво). Со други зборови, го поврзуваме помалото дрво на поголемото дрво. Притоа, бидејќи го поврзуваме главниот водач на едното дрво со главниот водач на другото дрво, резултатот ќе биде дрво каде што должината ќе биде или еднаква (доколку едното дрво е помало), или ќе се зголеми за 1 (доколку дрвата имале еднаква должина). Должината се зголемува за 1 поради тоа што, покрај сегашната должина, сега ќе има уште една врска (таа од едниот водач до другиот).

Имплементацијата на се она што зборувавме досега е дадена во продолжение.

#include <iostream>
#include <cstring>
using namespace std;

const int MAX_N = 101;

int leader[MAX_N];
int ranking[MAX_N];


int Find(int X) 
{
     if (leader[X] != X) 
     {
          int setLeader = Find(leader[X]); //prashaj go leader[X]
          
          //zapameti go rezultatot (podobruvanje)
          leader[X] = setLeader;
     }
     
     return leader[X];
}


void Union(int X, int Y) 
{
     int setLeaderX = Find(X);
     int setLeaderY = Find(Y);
     
     if (setLeaderX == setLeaderY) 
     {
          return /* vekje se vo istoto mnozhestvo */;
     }
     
     
     if (ranking[setLeaderX] == ranking[setLeaderY]) 
     {
          //ist rang, pa mozheme da izbereme eden od niv za spojuvanjeto
          leader[setLeaderY] = setLeaderX;
          
          //rangot sega kje se zgolemi
          ranking[setLeaderX]++;
     }
     else 
     {
          
          //razlichen rang, spoi vo ona so povisok (bez menuvanje na ranking[])
          if (ranking[setLeaderX] > ranking[setLeaderY]) 
          {
               leader[setLeaderY] = setLeaderX;
          }
          else 
          {
               leader[setLeaderX] = setLeaderY;
          }
     }
}



int main() 
{
     
     int N = 5;
     for (int i=0; i<N; i++)
     {
          //inicijalno, site si se vo svoe sopstveno mnozhestvo
          leader[i] = i;
     }
     
     //inicijalno, sekoe mnozhestvo dobiva rang 0
     memset(ranking, 0, sizeof(ranking));
     
     
     
     //da izvrshime nekolku operacii
     if (Find(0) != Find(1)) 
     {
          //ova kje se otpechati
          cout << "0 and 1 are in different sets." << endl;
     }
     
     Union(0, 1);
     if (Find(0) == Find(1)) 
     {
          //ova kje se otpechati
          cout << "Now, 0 and 1 are in the same set." << endl;
     }
     
     if (Find(0) != Find(2)) 
     {
          //ova kje se otpechati
          cout << "0 and 2 are in different sets." << endl;
     }
     
     
     
     Union(2, 3);
     Union(2, 4);
     
     //tuka, imame dve mnozhestva [0, 1], i [2, 3, 4]
     if (Find(0) != Find(2)) 
     {
          //ova kje se otpechati
          cout << "0 and 2 are in different sets." << endl;
     }
     
     
     
     Union(0, 4);
     
     //tuka, imame samo edno mnozhestvo [0, 1, 2, 3, 4]
     if (Find(0) == Find(3)) 
     {
          //ova kje se otpechati
          cout << "0 and 3 are in the same set." << endl;
     }
     
     return 0;
}

Забележете дека оваа структура не овозможува бришење на врски и раздвојување на едно множество на две или повеќе (само спојување).

Примери

Се разбира, податочната структура што ја имплементиравме може да се користи за решавање на секакви проблеми поврзани со множества каде што главното барање е ефикасно спојување. Следно, ќе разгледаме два примера со цел да видиме колку широка примена има самата структура.

Најпрвин, ќе почнеме со разгледување на неориентиран граф, каде што имаме темиња кои се поврзани меѓусебно со ребра. Бидејќи е графот неориентиран, доколку постои пат помеѓу две темиња (директен, или преку поминување низ повеќе ребра), тогаш постои пат и во обратна насока. Она што ни овозможува структурата за неповрзани множества, е да правиме проверки на тоа дали додавање на ново ребро во графот ќе предизвика создавање на циклус во истиот. Имено, при разгледување на ново ребро, пред повикувањето на union(), потребно е само да провериме дали двете темиња кои ги поврзува реброто се веќе дел од истото множество (дали find(X) == find(Y)). Доколку тие се веќе во исто множество, тоа значи дека постои пат помеѓу нив, па додавањето и на ова ребро ќе предизвика создавање на циклус. (Имајте предвид дека ова важи само за неориентирани графови).

Ова можете да го забележите и од сликата дадена погоре. Имено, со додавање на реброто обоено со црвена боја, во графот ќе се појави циклус. Притоа, за да го идентификуваме проблемот пред додавање на самото ребро, потребно е само да ја искористиме структурата која што ја имплементиравме во претходниот дел.

Вториот пример кој ќе го разгледаме е всушност алгоритам за создавање на минимално опфаќачко дрво. Ако се сеќавате на претходните предавања, опфаќачко дрво е дрво кое што ги содржи сите темиња од еден неориентиран граф, но само дел од ребрата кои се доволни за сите темиња да бидат поврзани помеѓу себе. (Логично, во опфаќачко дрво нема циклуси). Минимално опфаќачко дрво е она опфаќачко дрво каде што збирот на тежините на сите одбрани ребра е најмал можен. Имено, бидејќи можат да постојат повеќе опфаќачки дрва кои ги поврзуваат темињата (особено кога во графот постојат голем број на ребра), нас обично не интересира она опфаќачко дрво со најмал збир на тежините. Притоа, кога зборувавме за овој проблем, разгледавме и еден алгоритам (Prim) за негово решавање. Имплементацијата на алгоритамот на Prim беше многу слична на онаа на алгоритамот за откривање на најкраток пат во граф Dijkstra, и се базира на идејата дека ќе почнеме од едно теме, а потоа ќе додаваме нови и нови темиња во дрвото (едно по друго), така што во секој чекор ќе го додаваме она теме кое што е најблиску до дрвото.

Друг алгоритам кој можеме да го искористиме за откривање на минимално опфаќачко дрво е т.н. алгоритам на Kruskal. За имплементација на истиот ни е потребна структурата за неповрзани множества која ја дефиниравме во ова предавање. Имено, алгоритамот на Kruskal, за разлика од оној на Prim, функционира на начин што истиот (едно по едно) ги разгледува сите ребра од почетниот граф, по редослед од она ребро со најмала тежина до она со најголема тежина. Притоа, кога разгледуваме едно ребро, одлуката дали истото ќе го додадеме или не во минималното опфаќачко дрво ќе зависи (само) од тоа дали двете темиња кои реброто ги поврзува се веќе во исто множество или не. Доколку истите не се во исто множество, тогаш реброто ќе го додадеме во опфаќачкото дрво, и ќе направиме спојување на двете множества кои тоа ребро ги поврзува. Се разбира, бидејќи е потребно да ги разгледаме ребрата почнувајќи од она со најмала тежина, истите ќе ги подредиме по растечки редослед во однос на нивната тежина. Имплементацијата на функциите Union() и Find() ќе бидат, нормално, комплетно идентични како претходно.

//koristi C++11 - http://mendo.mk/Lecture.do?id=26

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX_N = 101;

//pochetniot graf
int N;
vector<pair<int, int> > G[MAX_N];


//union-find
int leader[MAX_N];
int ranking[MAX_N];


int Find(int X) 
{
     if (leader[X] != X) 
     {
          int setLeader = Find(leader[X]);
          leader[X] = setLeader;
     }
     
     return leader[X];
}


void Union(int X, int Y) 
{
     int setLeaderX = Find(X);
     int setLeaderY = Find(Y);
     
     if (setLeaderX == setLeaderY) 
     {
          return /* vekje se vo istoto mnozhestvo */;
     }
     
     
     if (ranking[setLeaderX] == ranking[setLeaderY]) 
     {
          leader[setLeaderY] = setLeaderX;
          ranking[setLeaderX]++;
     }
     else 
     {
          
          if (ranking[setLeaderX] > ranking[setLeaderY]) 
          {
               leader[setLeaderY] = setLeaderX;
          }
          else 
          {
               leader[setLeaderX] = setLeaderY;
          }
     }
}




//posebna struktura koja ni ovozmozhuva da dodavame rebra vo niza so dinamicka
//golemina i da gi podredime so cel izminuvanje vo tochniot redosled
struct Edge 
{
     int from, to, weight;
};


int kruskal() 
{
     
     //inicijaliziraj gi vrednostite vo leader i ranking
     for (int i=0; i<N; i++) 
     {
          leader[i] = i; //sekoe teme e vo posebno mnozhestvo
     }
     memset(ranking, 0, sizeof(ranking));
     
     
     //sozdadi lista od site rebra, za da mozheme da gi podredime
     vector<Edge> edges;
     
     for (int i=0; i<N; i++) 
     {
          for (auto next : G[i]) 
          {
               Edge edge;
               edge.from = i;
               edge.to = next.first;
               edge.weight = next.second;
               
               edges.push_back(edge);
          }
     }
     
     sort(edges.begin(), edges.end(), [](const Edge a, const Edge b) -> bool 
     {
          return a.weight < b.weight;
     });
     
     
     //izmini gi rebrata (od ona so najmala tezhina, kon ona so najgolema)
     int totalEdgeWeight = 0;
     for (auto edge : edges) 
     {
          if (Find(edge.from) != Find(edge.to)) 
          {
               //teminjata se vo razlichno mnozhestvo
               Union(edge.from, edge.to);
               
               totalEdgeWeight += edge.weight;
          }
     }
     
     return totalEdgeWeight;
}



int main() 
{
     N = 5;
     
     G[0].push_back({1, 5}); //rebro od 0 do 1, so tezhina 5
     G[1].push_back({0, 5}); //grafot e nenasocen, pa dodaj go i obratnoto rebro
     
     G[0].push_back({3, 7}); //rebro od 0 do 3 so tezhina 7
     G[3].push_back({0, 7}); //grafot e nenasocen, pa dodaj go i obratnoto rebro
     
     G[0].push_back({4, 1}); //rebro od 0 do 4 so tezhina 1
     G[4].push_back({0, 1}); //grafot e nenasocen, pa dodaj go i obratnoto rebro
     
     G[3].push_back({4, 2}); //rebro od 3 do 4 so tezhina 2
     G[4].push_back({3, 2}); //grafot e nenasocen, pa dodaj go i obratnoto rebro
     
     G[4].push_back({2, 9}); //rebro od 4 do 2 so tezhina 9
     G[2].push_back({4, 9}); //grafot e nenasocen, pa dodaj go i obratnoto rebro
     
     
     int result = kruskal();
     cout << "Minimum spanning tree has a total weight of " << result << endl;
     return 0;
}

Се разбира, и алгоритмите на Prim и на Kruskal секогаш водат до точниот резултат. На вас е да одлучите кој од нив ви е поедноставен за имплементација, и кој ќе го искористите за решавање на одреден проблем. Лично, авторот на овие предавања повеќе го користи алгоритамот на Prim, бидејќи истиот е многу сличен со оној на Dijkstra за наоѓање на најкраток пат во граф. Во ова предавање, одлучивме да го споменеме алгоритамот на Kruskal како пример за тоа како може да се искористи структурата за неповрзани множества, како и да се потсетиме на алгоритмите за спојување (union) и откривање (find).

Дозвола за користење: CC BY-NC 2.5 ©