Determinarea componentelor tare conexe ale unui graf

Reamintim că un graf orientat se numește tare conex, dacă între oricare două vârfuri ale lui există cel puțin câte o calei în ambele sensuri. În cazul grafurilor neorientate, orice lanț poate fi parcurs în ambele sensuri, deci, dacă graful neorientat este conex, el este și tare conex. În cazul grafurilor neorientate, este însă posibil ca între anumite vârfuri să existe cale numai într-un singur sens. Astfel se explică dece a fost necesar să se introducă și conceptul de graf tare conex.

Vom considera că un graf constituit dintr-un singur vârf este tare conex. În acest caz, orice graf orientat este constituit din una sau mai multe componente tare conexe. Se pune problema găsirii tuturor acestor componente. De multe ori, omul poate face aceasta prin examinarea directă a desenului grafului. Pentru a face însă aceeasi operație pe calculator, este necesar un algoritm.

Exemplu: În figura 1 este reprezentat un graf orientat, în care există 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 următorul:
  1. Se creează o listă Lctc a componentelor tare conexe, care inițial este vidă;
  2. Se pornește de la unul din vârfurile grafului G și se construiește arborele de acoperire în adâncime A;
  3. Se creează lista L care conține rădăcina vr a arborelui A și toate vârfurile acestui arbore de la care există cale către rădăcina vr;
  4. Se elimină din graful G toate vârfurile care există în lista L;
  5. Se adaugă lista L la Lctc (remarcăm că Lctc este o listă de liste);
  6. Se repetă pașii 2-5 cât timp graful G mai conține vârfuri.
 
Pentru determinarea componentelor tare conexe ale grafului, în clasa Graf din fișierul Graf.java s-au introdus următoarele metode:

  1. Metoda publică
  public boolean existaCale(String etVarf1, String etVarf2)
care determină dacă există o cale de la vârful cu eticheta etVarf1 la cel cu eticheta etVarf2. Această metodă determină referințele către cele doua vârfuri, varf1 si varf2, creează o mulțime a vârfurilor parcurse (inițial vidă) și invocă metoda auxiliară recursivă
  private boolean existaCale(Varf v1, Varf v2, TreeSet parcurse)
care determină prin explorare în adâncime dacă există cale între vârfurile v1 și v2.

  2. Metoda publica
  public List tareConexe()
care întoarce lista listelor etichetelor vârfurilor componentelor tare conexe ale grafului. Această metodă construiește o clonă a grafului, folosind în acest scop metoda clone() din clasa Graf, apoi aplică tehnica descrisă mai sus pentru determinarea listei componentelor tare conexe ale grafului. Clona este necesară pentru a nu se distruge graful original. Pentru obținerea listei vârfurilor explorate ân adâncime se folosește metoda
  public List explorareAdancime(String etichetaVarfPornire)
existentă în clasa Graf și prezentată anterior, iar pentru a determina dacă există cale între vârfurile acestui arbore și rădăcină se folosește metoda existaCale prezentată mai sus.

În programul din fișierul TestGraf2A.java se testează extragerea componentelor tare conexe din graful reprezentat în figura 1.



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunărea de Jos" din Galați