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