Bella at 07:53, 4 June 2019

2019-06-04T07:53:09Z

New page

Proiect Cella Florescu, Andrei Diaconu, Alexandra Timofte
= Algoritmul lui Kruskal =

Algoritmul lui Kruskal gaseste arborele partial de cost minim al unui graf bidirectional cu muchii cu costuri. Ideea de baza este una de tip greedy care sorteaza muchiile in ordine crescatoare dupa cost si dupa verifica daca fiecare muchie uneste doua componente conexe diferite cu ajutorul algoritmului union-find.

== Istoric ==

Algoritmul a fost publicat prima data in Proceedings of the American Mathematical Society, anul 1956 si a fost scris de Joseph Kruskal, un matematician si informatician american, absolvent al Universitatii din Chicago.

== Studiu de caz ==

In general, in viata reala algoritmul se foloseste in mod concret pentru a gasi modul optim de a crea o retea care sa conecteze toate calculatoarele cu un cost cat mai mic. Poate de exemplu sa minimizeze lungimea cablurilor necesare, daca sunt calculatoarele fixe, sau sa creeze un plan in care se conecteaza calculatoarele intr-un mod cat mai eficient din punct de vedere financiar (daca stim pentru fiecare conexiune cat ar costa pentru a fi folosita).

= Pasii algoritmului =

# Creaza padurea de multimi disjuncte F in care initial fiecare nod este o multime separata.
# Citeste setul S de muchii si il sorteaza in ordine crescatoare dupa cost.
# Pentru fiecare muchie din S, in ordine: daca muchia uneste 2 arbori diferiti (2 multimi disjuncte), atunci uneste cei 2 arbori (cele 2 multimi) si marcheaza muchia ca utilizata.

La finalul algoritmului, daca graful este conex (F contine doar o multime disjuncta), atunci a fost gasit un arbore partial de cost minim, muchiile acestuia fiind cele marcate drept utilizate.

[[Image:kruskal.png|frame]]
[[File:UnionFindKruskalDemo.gif|400px|none]]

== Complexitate ==

Pentru un graf cu N noduri si M muchii, algoritmul lui Kruskal are o complexitate medie de ''O(M log M)'' sau ''O(M log N)'', cele 2 complexitati fiind de fapt echivalente pentru ca ''M < N<sup>2</sup>'', deci ''log M < 2 * log N'', constanta 2 nefiind luata in calculul complexitatii.
Aceasta complexitate este in primul rand obtinuta prin sortarea celor M muchii dupa cost. Utilizand un algoritm de sortare precum quick-sort, complexitatea sortarii va fi de ''O(M log M)''. De asemenea, pentru verificarea componentelor conexe, este folosita o padure de multimi disjuncte care poate cu usurinta sa faca operatiile in timp de ''O(M log M)''. Adunand cele doua complexitati obtinem complexitatea finala asimptotica de ''O(M log M)''.

Algoritmul poate fi imbunatatit daca padurile de multimi disjuncte sunt implementate sa compreseze caile si sa aiba grija sa ataseze multimea mai mica multimii mai mari. Complexitatea pasului 3 poate astfel fi redusa la ''O(M * a(N))'', unde a este inversa functiei foarte incet crescatoare a lui Ackermann, o buna aproximare a acestei complexitati fiind chiar ''O(M log* N)''. In cazul in care muchiile sunt deja date in ordine crescatoare dupa cost, complexitatea intregului algoritm poate fi redusa la ''O(M log* N)''.

Din punctul de vedere al memoriei, algoritmul foloseste ''O(N)'' memorie suplimentara pentru structura union-find, pe langa memoria de ordin ''O(M)'' necesara pentru a memora lista de muchii.

== Demonstratie ==

In primul rand, daca graful initial G este conex, cum fiecare muchie care uneste 2 componente conexe diferita este adaugata, atunci in graful rezultat nu vor exista ciclii si va fi conex. Asfel, algoritmul va construi un arbore partial al grafului initial.
In al doilea rand, minimalitatea poate fi demonstrata prin inductie. Fie P(X): pentru setul de muchii selectate pana la un anumit pas X, exista un arbore partial de cost minim al lui G care sa contina muchiile din X.
Initial, P clar este adevarata deoarece orice graf conex are cel putin un arbore partial de cost minim si acest arbore include multimea vida (arborele partial inaintea primului pas).
La un pas al programului sa presupunem ca muchiile din setul X au fost pana acum selectate si ca T este un arbore partial de cost minim al lui G care contine muchiile din X.
* Daca urmatoarea muchie care este selectata este e si aceasta apartine deja lui T, atunci P este adevarata si pentru X + e.
* Daca e nu apartine lui T, atunci graful T + e ar avea un ciclu, fie acesta C. Fie f o muchie din ciclul C care nu apartine lui X (exista o astfel de muchie intrucat e formeaza un ciclu in T, dar nu si in X). Datorita proprietatii P(X), f nu a fost pana acum considerata de algoritm, deci are costul mai mare sau egal cu al lui e. Prin urmare, T - f + e este tot un arbore si are un cost mai mic decat T. Rezulta ca T - f + e este un arbore de cost minim care contine muchiile din setul X + e. Astfel, P(X + e) este in continuare adevarata.
Din principiul inductiei matematice, P este adevarata la fiecare pas al algoritmului. Astfel, arborele partial gasit de acest algoritm este de fapt un arbore partial de cost minim.

= Implementare =

=== Varianta neoptimizata (muchii date sub forma unei matrice de adiacenta) ===
Complexitate: ''O(M log M + M * N)'' (worst case - sortarea aduce termenul de M log M, in timp ce structura de union-find aduce pe cel de M * N, deoarece fara compresia cailor in cel mai rau caz se executa O(N) operatii pentru a cauta reprezentantul grupei)
<syntaxhighlight>
#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 1e5; /// numarul maxim de noduri
const int MAXM = 1e6; /// numarul maxim de muchii

struct Edge { /// structura de muchii, x si y sunt cele doua noduri din capetele muchiei, c este costul
int x, y, c;
bool operator < (const Edge& other) const { /// comparatorul care sorteaza muchiile crescator dupa cost
return c < other.c;
}
} edg[MAXM], apm[MAXN];

int group[MAXN + 1]; /// vectorul de tati in structura union-find

int find_group(int node) { /// functia de gasire a grupei din structura union-find, fara compresia caii
if (node != group[node]) /// cat timp nu am gasit reprezentantul grupei
return find_group(group[node]); /// mergem recursiv din tata in tata pana il gasim
return group[node];
}

int main() {
int n, m;
cin >> n >> m;
int n, m = 0;
cin >> n; /// citim numarul de noduri
for (int i = 1; i <= n; ++i) /// si matricea de adiacenta
for (int j = 1; j <= n; ++j) {
cin >> edg[m].c; /// citim costul fiecarei muchii
edg[m].x = i; /// si o adaugam in lista noastra de muchii
edg[m++].y = j;
}
sort(edg, edg + m); /// sortarea muchiilor crescator dupa cost
for (int i = 1; i <= n; ++i) /// initial toate nodurile formeaza grupe singulare
group[i] = i;
int edg_apm = 0; /// initial nu avem nicio muchie in arborele partial de cost minim
for (int i = 0; i < m; ++i) { /// luam pe rand toate muchiile dupa ce le-am sortat
int x = find_group(edg[i].x), y = find_group(edg[i].y); /// cautam reprezentatii nodurilor din capetele muchiei
if (x != y) { /// daca sunt diferiti atunci inseamna ca muchia noastra trebuie adaugata la arborele partial de cost minim pe care il construim
group[x] = y; /// unim grupele celor doua noduri
apm[edg_apm++] = edg[i]; /// adaugam muchia la lista muchiilor ce formeaza arborele partial de cost minim
}
} /// la finalul algoritmului, vectorul apm[] va contine N - 1 elemente, muchiile ce formeaza un arbore partial de cost minim al grafului initial
return 0;
}
</syntaxhighlight>

=== Varianta neoptimizata (muchii date sub forma unei liste, sortare de complexitate patratica) ===
Complexitate: ''O(M<sup>2</sup>)'' (complexitatea este cea data, intrucat sortarea de complexitate patratica duce la ignorarea complexitatii algoritmului union-find din punct de vedere al complexitatilor asimptotice)
<syntaxhighlight>
#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 1e5; /// numarul maxim de noduri
const int MAXM = 1e6; /// numarul maxim de muchii

struct Edge { /// structura de muchii, x si y sunt cele doua noduri din capetele muchiei, c este costul
int x, y, c;
bool operator < (const Edge& other) const { /// comparatorul care sorteaza muchiile crescator dupa cost
return c < other.c;
}
} edg[MAXM], apm[MAXN];

int group[MAXN + 1]; /// vectorul de tati in structura union-find

int find_group(int node) { /// functia de gasire a grupei din structura union-find, fara compresia caii
if (node != group[node]) /// cat timp nu am gasit reprezentantul grupei
return find_group(group[node]); /// mergem recursiv din tata in tata pana il gasim
return group[node];
}

inline void my_sort(Edge v[], int n) { /// sortare in O(N^2), selection sort
for (int i = n - 1; i > 0; --i)
for (int j = 0; j < i; ++j)
if (v[j] > v[i]) { /// algoritmul clasic, daca elementul de pe prefixul scanat este mai mare decat cel ce trebuie fixat le interschimbam
Edge aux = v[i];
v[i] = v[j];
v[j] = aux;
}
}

int main() {
int n, m;
cin >> n >> m; /// citim numarul de noduri si de muchii
for (int i = 0; i < m; ++i) /// citirea listei de muchii
cin >> edg[i].x >> edg[i].y >> edg[i].c;
my_sort(edg, m); /// sortarea muchiilor crescator dupa cost
for (int i = 1; i <= n; ++i) /// initial toate nodurile formeaza grupe singulare
group[i] = i;
int edg_apm = 0; /// initial nu avem nicio muchie in arborele partial de cost minim
for (int i = 0; i < m; ++i) { /// luam pe rand toate muchiile dupa ce le-am sortat
int x = find_group(edg[i].x), y = find_group(edg[i].y); /// cautam reprezentatii nodurilor din capetele muchiei
if (x != y) { /// daca sunt diferiti atunci inseamna ca muchia noastra trebuie adaugata la arborele partial de cost minim pe care il construim
group[x] = y; /// unim grupele celor doua noduri
apm[edg_apm++] = edg[i]; /// adaugam muchia la lista muchiilor ce formeaza arborele partial de cost minim
}
} /// la finalul algoritmului, vectorul apm[] va contine N - 1 elemente, muchiile ce formeaza un arbore partial de cost minim al grafului initial
return 0;
}
</syntaxhighlight>

=== Varianta neoptimizata (muchii date sub forma unei liste) ===
Complexitate: ''O(M log M + M * N)'' (worst case - sortarea aduce termenul de M log M, in timp ce structura de union-find aduce pe cel de M * N, deoarece fara compresia cailor in cel mai rau caz se executa O(N) operatii pentru a cauta reprezentantul grupei)
<syntaxhighlight>
#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 1e5; /// numarul maxim de noduri
const int MAXM = 1e6; /// numarul maxim de muchii

struct Edge { /// structura de muchii, x si y sunt cele doua noduri din capetele muchiei, c este costul
int x, y, c;
bool operator < (const Edge& other) const { /// comparatorul care sorteaza muchiile crescator dupa cost
return c < other.c;
}
} edg[MAXM], apm[MAXN];

int group[MAXN + 1]; /// vectorul de tati in structura union-find

int find_group(int node) { /// functia de gasire a grupei din structura union-find, fara compresia caii
if (node != group[node]) /// cat timp nu am gasit reprezentantul grupei
return find_group(group[node]); /// mergem recursiv din tata in tata pana il gasim
return group[node];
}

int main() {
int n, m;
cin >> n >> m; /// citim numarul de noduri si de muchii
for (int i = 0; i < m; ++i) /// citirea listei de muchii
cin >> edg[i].x >> edg[i].y >> edg[i].c;
sort(edg, edg + m); /// sortarea muchiilor crescator dupa cost
for (int i = 1; i <= n; ++i) /// initial toate nodurile formeaza grupe singulare
group[i] = i;
int edg_apm = 0; /// initial nu avem nicio muchie in arborele partial de cost minim
for (int i = 0; i < m; ++i) { /// luam pe rand toate muchiile dupa ce le-am sortat
int x = find_group(edg[i].x), y = find_group(edg[i].y); /// cautam reprezentatii nodurilor din capetele muchiei
if (x != y) { /// daca sunt diferiti atunci inseamna ca muchia noastra trebuie adaugata la arborele partial de cost minim pe care il construim
group[x] = y; /// unim grupele celor doua noduri
apm[edg_apm++] = edg[i]; /// adaugam muchia la lista muchiilor ce formeaza arborele partial de cost minim
}
} /// la finalul algoritmului, vectorul apm[] va contine N - 1 elemente, muchiile ce formeaza un arbore partial de cost minim al grafului initial
return 0;
}
</syntaxhighlight>

=== Varianta optima (union-find cu compresia caii, muchii date sub forma unei liste) ===
Complexitate: ''O(M log M)''
<syntaxhighlight>
#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 1e5; /// numarul maxim de noduri
const int MAXM = 1e6; /// numarul maxim de muchii

struct Edge { /// structura de muchii, x si y sunt cele doua noduri din capetele muchiei, c este costul
int x, y, c;
bool operator < (const Edge& other) const { /// comparatorul care sorteaza muchiile crescator dupa cost
return c < other.c;
}
} edg[MAXM], apm[MAXN];

int group[MAXN + 1]; /// vectorul de tati in structura union-find

int find_group(int node) { /// functia de gasire a grupei din structura union-find, cu tot cu compresia drumului
if (node != group[node]) /// daca nu am gasit reprezentantul grupei
group[node] = find_group(group[node]); /// cream o legatura de la nodul curent la reprezentant (compresia caii)
return group[node];
}

int main() {
int n, m;
cin >> n >> m; /// citim numarul de noduri si de muchii
for (int i = 0; i < m; ++i) /// citirea listei de muchii
cin >> edg[i].x >> edg[i].y >> edg[i].c;
sort(edg, edg + m); /// sortarea muchiilor crescator dupa cost
for (int i = 1; i <= n; ++i) /// initial toate nodurile formeaza grupe singulare
group[i] = i;
int edg_apm = 0; /// initial nu avem nicio muchie in arborele partial de cost minim
for (int i = 0; i < m; ++i) { /// luam pe rand toate muchiile dupa ce le-am sortat
int x = find_group(edg[i].x), y = find_group(edg[i].y); /// cautam reprezentatii nodurilor din capetele muchiei
if (x != y) { /// daca sunt diferiti atunci inseamna ca muchia noastra trebuie adaugata la arborele partial de cost minim pe care il construim
group[x] = y; /// unim grupele celor doua noduri
apm[edg_apm++] = edg[i]; /// adaugam muchia la lista muchiilor ce formeaza arborele partial de cost minim
}
} /// la finalul algoritmului, vectorul apm[] va contine N - 1 elemente, muchiile ce formeaza un arbore partial de cost minim al grafului initial
return 0;
}
</syntaxhighlight>

== Probleme ==
* [https://www.infoarena.ro/problema/ninjago ninjago]
* [https://www.infoarena.ro/problema/elicoptere elicoptere]
* [https://www.infoarena.ro/problema/radiatie radiatie]

= Bibliografie =
* [https://en.wikipedia.org/wiki/Kruskal%27s_algorithm https://en.wikipedia.org/wiki/Kruskal%27s_algorithm]

Proiect Cella Florescu - Revision history

Bella at 07:53, 4 June 2019