- 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:
In clasa Graf, exista metoda
Cele doua metode prezentate aici sunt testate in programul din fisierul TestGraf2.java. |