Sortarea topologica

Sortarea topologica poate fi aplicata in cazul grafurilor orientate fara cicluri. Un exemplu de astfel de graf este dat in figura 1.


- Figura 1 -

In aceasta figura se poate observa direct ca nu exista cicluri, deoarece toate arcele sunt orientate de la stanga la dreapta. Desigur, insa, ca acelasi graf putea fi desenat si altfel (de exemplu mutand unele varfuri catre stanga), astfel ca ar fi fost mai dificil de constatat absenta ciclurilor.

Amintim ca un graf neorientat fara cicluri este un arbore liber. In cazul grafurilor orientate, asa cum se poate constata si din figura 1, pot exista grafuri fara cicluri care nu sunt arbori. Astfel de relatii intre obiecte (varfurile grafului) se intalnesc frecvent in practica. De exemplu, majoritatea cursurilor predate in facultate sunt conditionate de absolvirea in prealabil a altor cursuri. In mod similar, efectuarea anumitor operatii asupra unei piese intr-un proces tehnologic de fabricatie este conditionata de efectuarea in prealabil a altor operatii etc.

Problema sortarii topologice se formuleaza in modul urmator: se vor sorta varfurile grafului astfel incat, daca varful vi se gaseste inaintea lui vj, sa nu existe nici o cale de la vi catre vj. In general, pentru acelasi graf pot exista mai multe sortari topologice posibile. Iata doua sortari 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 topologica se poate face prin urmatorul algoritm:

   1. Se creeaza o clona G1 a grafului G;
   2. Se creeaza o lista L vida;
   3. Cat timp exista inca varfuri in G1:
      3.1. Se pun in lista L toate etichetele varfurilor din G1 din care nu pornesc arce;
      3.2. Se elimina din G1 toate varfurile ale caror etichete au fost puse in L la pasul 3.1.
   4. Se intoarce lista L.

Acest algoritm functioneaza numai daca graful dat nu contine cicluri. In caz contrar algoritmul nu se va opri, deoarece nu se va indeplini niciodata conditia ca G1 sa nu contina varfuri. Pentru a remedia aceasta deficienta, se poate pune in plus conditia ca procesul sa se incheie cand se constata ca in G1 nu mai exista nici un varf din care nu pornesc arce.
 
In clasa Graf din fisierul Graf.java sortarea topologica se face prin metoda 
  public List sortareTopologica()
Daca graful nu contine cicluri, aceasta metoda intoarce o lista, in care varfurile grafului sunt sortate topologic.

Remarcam ca, la sortarea topologica, varfurile pot fi grupate pe nivele. Astfel, in cazul grafului din figura 1, gruparea pe nivele este urmatoarea:
    [I, J], [G, H], [D, E, F], [A, B, C]
Prima sublista contine varfurile de pe nivelul de baza, adice cele din care nu pornesc arce. Din fiecare varf de pe un nivel superior porneste cel putin un arc catre unul din varfurile de pe nivelul imediat inferior. Ge exemplu, exista arcele G-I, G-J, H-I.

In clasa Graf, exista metoda 
  public List sortTopoNivele()
care intoarce a varfurilor sortate pe nivele. Aceasta lista are drept componente subliste in care sunt grupate toate varfurile de pe acelasi nivel. Algoritmul folosit in aceasta metoda este similar celui din metoda precedenta, singura modificare fiind ca la fiecare parcurgere a ciclului in care se cauta varfurile din care nu pornesc arce, acestea se grupeaza intr-o listaNivel, care este apoi pusa ca element in listaSortata.

Cele doua metode prezentate aici sunt testate in programul din fisierul TestGraf2.java.



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunarea de Jos" din Galati