|
|
|
Aplicatie vectori: Componente conexe
Aplicatia poate fi formulata cel putin in doua moduri si a condus la aparitia unui tip abstract de date, numit colectie de multimi disjuncte ("Disjoint Sets").
Fiind data o multime de valori (de orice tip) si o serie de relatii de echivalenta intre perechi de valori din multime, se cere sa se afiseze clasele de echivalenta formate cu ele. Daca sunt n valori, atunci numarul claselor de echivalenta poate fi intre 1 si n, inclusiv.
Exemplu de date initiale (relatii de echivalenta):
30 ~ 60 / 50 ~ 70 / 10 ~ 30 / 20 ~ 50 / 40 ~ 80 / 10 ~ 60 /
Rezultatul (clasele de echivalenta) : , ,
O alta formulare a problemei cere afisarea componentelor conexe dintr-un graf neorientat definit printr-o lista de muchii. Fiecare muchie corespunde unei relatii de echivalenta intre varfurile unite de muchie, iar o componenta conexa este un subgraf (o clasa de noduri ) in care exista o cale intre oricare doua varfuri. Exemplu:
1
8 2
7 3
6 4
5
In cazul particular al componentelor conexe dintr-un graf, este suficient un singur vector "cls", unde cls[k] este componenta in care se afla varful k.
In cazul mai general al claselor de echivalenta ce pot contine elemente de orice tip (numere oarecare sau siruri ce reprezinta nume), mai este necesar si un vector cu valorile elementelor. Pentru exemplul anterior cei doi vectori pot arata in final astfel (numerele de clase pot fi diferite):
val 10 20 30 40 50 60 70 80
cls 1 2 1 3 2 1 2 3
Vectorii val, cls si dimensiunea lor se reunesc intr-un tip de date numit "colectie de multimi disjuncte", pentru ca fiecare clasa de echivalenta este o multime, iar aceste multimi sunt disjuncte intre ele.
typedef struct ds;
Pentru memorarea unor date agregate intr-un vector avem doua posibilitati:
- Mai multi vectori paraleli, cu aceeasi dimensiune; cate un vector pentru fiecare camp din structura (ca in exemplul anterior).
- Un singur vector de structuri:
typedef struct entry;
typedef struct ds;
S-au stabilit urmatoarele operatii specifice tipului abstract "Disjoint Sets":
- Initializare colectie (initDS)
- Gasirea multimii (clasei) care contine o valoare data (findDS)
- Reunire multimi (clase) ce contin doua valori date (unifDS)
- Afisare colectie de multimi (printDS)
La citirea unei perechi de valori (unei relatii de echivalenta) se stabileste pentru cele doua valori echivalente acelasi numar de clasa, egal cu cel mai mic dintre cele doua (pentru a mentine ordinea in fiecare clasa).
Daca valorile sunt chiar numerele 1,2,..8 atunci evolutia vectorului de clase dupa fiecare pereche de valori citita va fi
clase
initial 1 2 3 4 5 6 7 8
dupa 3-6 1 2 3 4 5 3 7 8
dupa 5-71 2 3 4 5 3 5 8
dupa 1-31 2 1 4 5 1 5 8
dupa 2-51 2 1 4 2 1 2 8
dupa 4-81 2 1 4 2 1 2 4
dupa 1-61 2 1 4 2 1 2 4(nu se mai modifica nimic)
Urmeaza un exemplu de implementare cu un singur vector a tipului "Colectie de multimi disjuncte" si utilizarea sa in problema afisarii componentelor conexe.
typedef struct ds;
// determina multimea in care se afla x
int find ( ds c, int x)
// reunire multimi ce contin valorile x si y
void unif ( ds & c,int x,int y)
// afisare multimi din colectie
void printDS (ds c)
if (m) // daca exista valori in multimea i
printf('n'); // se trece pe alta linie
}
// initializare multimi din colectie
void initDS (ds & c, int n)
// afisare componente conexe
void main ()
In aceasta implementare operatia "find" are un timp constant O(1), dar operatia de reuniune este de ordinul O(n).
Cea mai buna implementare pentru "Disjoint Sets" foloseste tot un singur vector de intregi, dar acest vector reprezinta o padure de arbori. Elementele vectorului sunt indici (adrese) din acelasi vector cu semnificatia de pointeri catre nodul parinte. Fiecare multime este un arbore in care fiecare nod (element) contine o legatura la parintele sau, dar nu si legaturi catre fii sai. Radacina fiecarui arbore poate contine ca legatura la parinte fie chiar adresa sa, fie o valoare nefolosita ca indice (-1 ).
Pentru datele folosite anterior (8 varfuri in 3 componente conexe), starea finala a vectorului ce reprezinta colectia si arborii corespunzatori pot arata astfel:
valoare 1 2 3 4 5 6 7 8
legatura -1 -1 1 -1 2 3 5 4
1 2 4
| | |
3 5 8
| |
6 7
In functie de codul folosit sunt posibile si alte variante, dar tot cu trei arbori si cu aceleasi noduri (se modifica doar radacina si structura arborilor).
Daca se mai adauga o muchie 3-7 atunci se reunesc arborii cu radacinile in 1 si 2 intr-un singur arbore, iar in vectorul ce reprezinta cei doi arbori ramasi se modifica legatura lui 2 (p[2]=1).
1 4
/ |
3 28
/
65
7
Gasirea multimii care contine o valoare data x se reduce la aflarea radacinii arborelui in care se afla x, mergand in sus de la x catre radacina. Reunirea arborilor ce contin un x si un y se face prin legarea radacinii arborelui y ca fiu al radacinii arborelui x (sau al arborelui lui x la arborele lui y).
Urmeaza functiile ce realizeaza operatiile specifice tipului "Disjoint Sets":
typedef struct ds;
// initializare colectie
void init (ds & c, int n)
// determina multimea care contine pe x
int find ( ds c, int x)
// reunire clase ce contin valorile x si y
void unif ( ds & c,int x,int y)
In aceasta varianta operatia de cautare are un timp proportional cu adancimea arborelui, iar durata operatiei de reuniune este practic aceeasi cu durata lui "find". Pentru reducerea in continuare a duratei operatiei "find" s-au propus metode pentru reducerea adancimii arborilor. Modificarile au loc in algoritm, dar structura de date ramane practic neschimbata (tot un vector de indici catre noduri parinte).
