Determinarea componentelor tare conexe ale unui graf
Reamintim ca un graf orientat se numeste tare conex daca intre oricare
doua varfuri ale lui exista cai in ambele sensuri. In cazul grafurilor
neorientate orice lant poate fi parcurs in ambele sensuri, deci, daca graful
neorientat este conex el este si tare conex. In cazul grafurilor neorientate
este insa posibil ca intre anumite varfuri sa existe cale numai intr-un
singur sens. Astfel se explica dece a fost necesar sa se introduca si conceptul
de graf tare conex.
Vom considera ca un graf constituit dintr-un singur varf este tare conex.
In acest caz, orice graf orientat este constituit din una sau mai multe
componente tare conexe. Se pune problema gasirii tuturor acestor componente.
De multe ori, omul poate face aceasta prin examinarea directa a desenului
grafului. Pentru a face insa aceeasi operatie pe calculator, este necesar
un algoritm.
Exemplu: In figura 1 este reprezentat un graf orientat,
in care exista urmatoarele componente tare conexe:
[A, B, C, D], [E, F, G, H], [I], [J].
- Figura 1 -
Un algoritm de determinare a tuturor componentelor tare conexe ale grafului
G = (V, E) este urmatorul:
1. Se creeaza o lista Lctc a componentelor tare conexe, care
initial este vida;
2. Se porneste de la unul din varfurile grafului G si se construieste
arborele de acoperire in adancime A;
3. Se creeaza lista L care contina radacina vr
arborelui A si toate varfurile acestui arbore de la care exista cale carte
radacina vr;
4. Se elimina din graful G toate varfurile care exista in lista
L;
5. Se adauga lista L la Lctc (remarcam ca Lctc este o lista
de liste);
6. Se repeta pasii 2-5 cat timp graful G mai contine varfuri.
Pentru determinarea componentelor tare conexe ale grafului, in clasa
Graf din fisierul Graf.java s-au introdus urmatoarele
metode:
1. Metoda publica
public boolean existaCale(String etVarf1, String etVarf2)
care determina daca exista o cale de la varful cu eticheta etVarf1
la cel cu eticheta etVarf2. Aceasta metoda determina referintele
catre cele doua varfuri, varf1 si varf2, creeaza o multime
a varfurilor parcurse (initial vida) si invoca metoda auxiliara
recursiva
private boolean existaCale(Varf v1, Varf v2, TreeSet parcurse)
care determina prin explorare in adancime daca exista cale
intre varfurile v1 si v2.
2. Metoda publica
public List tareConexe()
care intoarce lista listelor etichetelor varfurilor componentelor tare
conexe ale grafului. Aceasta metoda construieste o clona a grafului, folosind
in acest scop metoda clone() din clasa Graf, apoi aplica tehnica
descrisa mai sus pentru determinarea listei componentelor tare conexe ale
grafului. Clona este necesara pentru a nu se distruge graful original.
Pentru obtinerea listei varfurilor explorate in adancime se foloseste metoda
public List explorareAdancime(String etichetaVarfPornire)
existenta in clasa Graf si prezentata anterior, iar pentru a determina
daca exista cale intre varfurile acestui arbore si radacina se foloseste
metoda existaCale prezentata mai sus.
In programul din fisierul TestGraf2A.java
se testeaza extragerea componentelor tare conexe din graful reprezentat
in figura 1. |
© Copyright 2001 - Severin
BUMBARU, Universitatea "Dunarea de Jos" din Galati