- 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: În clasa Graf, există metoda Cele două metode prezentate aici sunt testate în programul din fișierul TestGraf2.java. |