Algoritmi pentru arborele optim

Arbore partial de valoare minima sau maxima

KruskalSollinVarianta Kruskaln noduri → n-1 muchiifara cicluri
A

Algoritmul lui Kruskal

Alegerea succesiva a muchiilor de valoare minima (maxima), fara formarea ciclurilor
1

Dintre toate muchiile grafului se alege muchia de valoare minima (maxima). Daca minimul este multiplu, se alege una dintre muchiile respective.

2

Dintre toate muchiile ramase se alege cea de valoare minima (maxima).

3

Se alege urmatoarea muchie minima (maxima), dar numai daca nu formeaza un ciclu cu muchiile deja selectate.

4

Pasul 3 se repeta pana cand sunt colectate exact n-1 muchii.

Arbore cu n noduri   ⇒   exact n - 1 muchii
Cazul valorilor egale
Daca exista k muchii cu aceeasi valoare V, alegerea poate fi facuta arbitrar. In implementarea descrisa in curs, egalitatea poate fi eliminata prin perturbari foarte mici: V+e, V+2e, ..., V+ke, unde e este suficient de mic incat ordinea fata de urmatoarea valoare distincta sa nu se schimbe.

Garantie

Algoritmul gaseste un arbore optim. Daca exista mai multe alegeri posibile din cauza valorilor egale, pot rezulta arbori diferiti, dar toti au aceeasi valoare optima.

Problema computationala

In formularea directa, trebuie cautat repetat minimul intr-o multime potential foarte mare de muchii si trebuie verificat daca noua muchie creeaza un ciclu.

Cum evitam ciclurile?

Putem urmari componentele conexe. O muchie poate fi adaugata daca extremitatile ei apartin unor componente diferite.

Observatie moderna

In implementarea eficienta, muchiile se sorteaza o singura data, iar componentele sunt gestionate cu o structura de tip Union-Find / Disjoint Set.

B

Algoritmul lui Sollin

Cunoscut astazi frecvent si ca algoritmul Boruvka
1

Pentru fiecare nod se alege muchia adiacenta de valoare minima (maxima).

2

Se identifica componentele conexe ale grafului partial format din muchiile alese.

3

Pentru fiecare componenta conexa se alege cea mai ieftina (scumpa) muchie care iese din componenta.

4

Se revine la pasul 2 pana cand ramane o singura componenta conexa: arborele optim.

Ce inseamna muchie adiacenta unei componente?
Este o muchie care are exact o extremitate in componenta respectiva. Cealalta extremitate se afla intr-o alta componenta. Prin alegerea unei astfel de muchii, doua componente diferite sunt unite.

Avantaj

Cautarea se face local: initial pentru muchiile adiacente fiecarui nod, apoi pentru muchiile care ies din fiecare componenta.

Fara cicluri

Componente diferite sunt unite progresiv, astfel incat constructia evita in mod natural alegerea unei muchii interne inutile unei componente.

Dezavantaj in formularea clasica

Pentru grafuri foarte mari trebuie gestionate succesiv numeroase componente conexe si informatiile asociate acestora.

Imagine mentala

Nu creste un singur arbore. La inceput cresc mai multi arbori simultan, care se unesc treptat pana ramane unul singur.

C

O varianta a algoritmului lui Kruskal

Cresterea unei singure componente conexe
1

Dintre toate muchiile grafului se alege cea de valoare minima (maxima).

2

Dintre toate muchiile adiacente componentei conexe formate pana acum se alege cea de valoare minima (maxima).

3

Pasul 2 se repeta pana cand sunt colectate n-1 muchii.

O singura componenta

Spre deosebire de Sollin, algoritmul dezvolta permanent o singura componenta conexa.

Implementare simpla

La fiecare etapa ne intereseaza numai muchiile care pleaca din componenta curenta catre noduri aflate in exterior.

Observatie importanta: aceasta procedura este, in terminologia moderna, forma algoritmului lui Prim: arborele creste prin adaugarea celei mai ieftine muchii care leaga componenta curenta de un nod exterior.

Comparatie rapida

AlgoritmCe creste?Cum alege?CicluriIdeea-cheie
KruskalMai multe componenteCea mai ieftina muchie globala admisibilaTrebuie detectate/evitateSorteaza muchiile
Sollin / BoruvkaMai multe componente simultanCea mai ieftina muchie care iese din fiecare componentaEvitate prin unirea componentelorCreste in paralel
Varianta descrisa / PrimO singura componentaCea mai ieftina muchie care iese din componenta curentaUsor de evitatCreste un singur arbore
Toti urmaresc acelasi obiectiv: conectarea tuturor nodurilor, fara cicluri, cu valoare totala minima (sau maxima, in varianta corespunzatoare).