Se pot imagina forme foarte variate de reprezentare a grafurilor ca structuri de date, fiecare din acestea putând fi adecvată unui anumit scop.
În cazul grafurilor abstracte, în care vârfurile și arcele nu sunt etichetate și nu poartă alte informații, reprezentarea se reduce la o matrice de adiacențe sau la un tablou al arcelor (muchiilor). În acest caz nodurile sunt reprezentate numai prin indicii lor.
Dacă vârfurile și/sau arcele sunt etichetate sau poartă alte informații, ele pot fi reprezentate prin structuri de date (în particular prin obiecte), între care există legături. Aceste legături pot fi păstrate chiar în structurile de date respective, sau pot fi reprezentate separat, ca și în cazul grafurilor abstracte, printr-o matrice de adiacențe sau printr-un tablou al arcelor (muchiilor).
Fie graful din figura 1, în care nodurile sunt numerotate.
- Figura 1 -
Matricea de adiacențe a acestui graf este următoarea:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Dacă graful este neorientat, matricea de adiacențe corespunzătoare este simetrică.
- Figura 2 -
De exemplu, în cazul grafului neorientat din figura 2,
matricea de adiacențe este următoarea:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Matricele de adiacențe sunt avantajoase, atunci când este necesar să se verifice frecvent prezența arcelor între anumite noduri. Dacă însă numărul de vârfuri n este mare, iar numărul de arce este sensibil mai mic decât n2, matricea de adiacențe are multe elemente nule și, deci, ocupă un spațiu prea mare în memorie.
Observație: În exemplele date aici, s-a considerat că
indexarea începe de la valoarea 1.
class GrafMA {
private Object[] varfuri;
private byte[][] matriceAdiacenta;
// Constructori, metode si clase interioare
}
Pentru elementele matricei de adiacența s-a folosit tipul byte,
deoarece valorile elementelor pot fi numai 0 sau 1. Lista vârfurilor
conține referințe la obiectele de informație atașate fiecărui vârf.
Iindicii liniilor și coloanelor din matricea de adiacențe sunt cei ai
vârfurilor corespunzatoare din lista vârfurilor.
În fișierul GrafMA.java este dat un exemplu de definire a clasei grafurilor cu matrice de adiacențe. Clasa conține metode de punere a vârfurilor și a arcelor și de eliminare a vârfurilor sau a arcelor. Un mic program de testare a acestei clase este dat în fișierul TestGrafMA.java. |
import java.util.ArrayList;
class GrafLA {
protected ArrayList varfuri;
public GrafLA() {
varfuri=new ArrayList(); // lista varfurilor grafului
}
// Metode ale clasei GrafLA
/* Clasa interioara Varf */
class Varf {
String eticheta;
Object info;
ArrayList adiacente; // lista varfurilor adiacente
// Constructori si metode ale clasei Varf
}
}
În fișierul GrafLA.java este dat un exemplu de definire a unei clase de grafuri, în care matricile de adiacențe sunt incluse în vârfuri. Clasa conține metode de punere și de eliminare a vârfurilor și a arcelor. Un mic program de testare este dat în fișierul TestGrafLA.java. |
În fișierul Graf.java este dat un
exemplu de definire a clasei Graf, în care: - vârfurile grafului se identifică prin etichetă, care este un String; - atât vârfurilor, cât și arcelor li se pot atașa obiecte de informație; - fiecare vârf conține o listă a arcelor care au baza (originea) în vârful respectiv; - vârfurile sunt instanțe ale clasei interioare Varf, care conține câmpurile String eticheta, Object info și ArrayList arce; - arcele sunt instanțe ale clasei interioare Arc, care conține câmpurile Varf varf (o referință la vârful de destinație al arcului) și Object info; - clasa Graf conține metode pentru punerea și eliminarea de vârfuri și arce, obținerea și modificarea informațiilor din vârfuri și arce, obținerea de iteratori ai grafului. Vârfurile grafului sunt păstrate în câmpul varfuri, care este o listă din clasa ArrayList. Pentru a se reduce timpul de căutare a unui vârf dupa etichetă, vârfurile sunt mentinuțe în această listă sortate în ordinea crescatoare a etichetelor. Din această cauză, căutarea unui nod și punerea unui vârf în listă nu se fac folosind metodele clasei ArrayList (care sunt specifice unei liste neordonate), ci prin metode proprii ale clasei Graf, respectiv prin metodele int indiceVarf(String eticheta) și boolean puneVarf(String eticheta, Object info). Pentru căutarea unui vârf se folosește metoda căutarii binare. Clasa Graf conține și metode de explorare a grafului, care sunt prezentate în secțiunea următoare. Pentru a putea transmite graful într-un flux de obiecte, folosind clasele ObjectOutputStream pentru ieșire și, respectiv, ObjectInputStream pentru intrare, clasa Graf și clasele ei interioare Varf și Arc implementează interfața Serializable. Pentru a se putea sorta vârfurile, clasa interioara Varf implementează și interfața Comparable. Testarea clasei Graf se face în aplicația din fișierul TestGraf.java. În această aplicație se creează un graf, în care se pun vârfuri și arce, se elimină unele vârfuri și arce, se parcurge graful în lățime sau în adâncime, se convertește graful în liste de vârfuri parcurse în lățime sau în adâncime, se scrie graful într-un fișier de obiecte, după care se citește din acest fisier. Rezultatul fiecărei astfel de testări este afișat pe ecran. |