Sortarea topologică

Sortarea topologică poate fi aplicată în cazul grafurilor orientate fără cicluri. Un exemplu de astfel de graf este dat în figura 1.


- Figura 1 -

În această figură se poate observa direct că nu există cicluri, deoarece toate arcele sunt orientate de la stânga la dreapta. Desigur, însă, că același graf putea fi desenat și altfel (de exemplu mutând unele vârfuri către stânga), astfel că ar fi fost mai dificil de constatat absența ciclurilor.

Amintim că un graf neorientat fără cicluri este un arbore liber. În cazul grafurilor orientate, așa cum se poate constata și din figura 1, pot exista grafuri fără cicluri care nu sunt arbori. Astfel de relații între obiecte (vârfurile grafului) se întâlnesc frecvent în practică. De exemplu, majoritatea cursurilor predate în facultate sunt condiționate de absolvirea în prealabil a altor cursuri. În mod similar, efectuarea anumitor operații asupra unei piese într-un proces tehnologic de fabricație este condiționată de efectuarea în prealabil a altor operații etc.

Problema sortării topologice se formulează în modul următor: se vor sorta vârfurile grafului astfel încât, dacă varful vi se găsește înaintea lui vj, să nu existe nici o cale de la vi catre vj. In general, pentru același graf pot exista mai multe sortări topologice posibile. Iată două sortări topologice pentru graful din figura 1:
    I, J, G, H, D, E, F, A, B, C
    J, I, H, G, E, D, F, C, B, A

Sortarea topologică se poate face prin urmatorul algoritm:

   1. Se creează o clonă G1 a grafului G;
   2. Se creează o listă L vidă;
   3. Cât timp există încă vârfuri în G1:
      3.1. Se pun în lista L toate etichetele varfurilor din G1 din care nu pornesc arce;
      3.2. Se elimină din G1 toate vârfurile ale căror etichete au fost puse in L la pasul 3.1.
   4. Se întoarce lista L.

Acest algoritm funcționează numai dacă graful dat nu conține circuite. În caz contrar, algoritmul nu se va opri, deoarece nu se va îndeplini niciodată condiția ca G1 să nu mai conțină vârfuri. Pentru a remedia această deficiența, se poate pune în plus condiția ca procesul să se încheie când se constată că în G1 nu mai există nici un vârf din care nu pornesc arce.
 
În clasa Graf din fișierul Graf.java sortarea topologică se face prin metoda 
  public List sortareTopologica()
Dacă graful nu conține cicluri, această metodă întoarce o listă, în care vârfurile grafului sunt sortate topologic.

Remarcăm că, la sortarea topologică, vârfurile pot fi grupate pe niveluri. Astfel, în cazul grafului din figura 1, gruparea pe niveluri este următoarea:
    [I, J], [G, H], [D, E, F], [A, B, C]
Prima sublistă conține vârfurile de pe nivelul de bază, adică cele din care nu pornesc arce. Din fiecare vârf de pe un nivel superior pornește cel putin un arc către unul din vârfurile de pe nivelul imediat inferior. De exemplu, există arcele G-I, G-J, H-I.

În clasa Graf, există metoda 
  public List sortTopoNivele()
care întoarce o listă a vârfurilor sortate pe nivele. Această listă are drept componente subliste, în care sunt grupate toate vârfurile de pe același nivel. Algoritmul folosit în această metodă este similar celui din metoda precedentă, singura modificare fiind că, la fiecare parcurgere a ciclului în care se caută varfurile din care nu pornesc arce, acestea se grupează într-o listaNivel, care este apoi pusă ca element în listaSortata.

Cele două metode prezentate aici sunt testate în programul din fișierul TestGraf2.java.



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