Se pot imagina forme foarte variate de reprezentare a grafurilor ca structuri de date, fiecare din acestea putand fi adecvata unui anumit scop.
In cazul grafurilor abstracte, in care varfurile si arcele nu sunt etichetate si nu poarta alte informatii, reprezentarea se reduce la o matrice de adiacente sau la un tablou al arcelor (muchiilor). In acest caz nodurile sunt reprezentate numai prin indicii lor.
Daca varfurile si/sau arcele sunt etichetate sau poarta alte informatii, ele pot fi reprezentate prin structuri de date (in particular prin obiecte), intre care exista legaturi. Aceste legaturi pot fi pastrate chiar in structurile de date respective, sau pot fi reprezentate separat, ca si in cazul grafurilor abstracte, printr-o matrice de adiacente sau printr-un tablou al arcelor (muchiilor).
Fie graful din figura 1, in care nodurile sunt numerotate.
- Figura 1 -
Matricea de adiacenta a acestui graf este urmatoarea:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Daca graful este neorientat, matricea de adiacenta corespunzatoare este simetrica.
- Figura 2 -
De exemplu, in cazul grafului neorientat din figura 2,
matricea de adiacenta este urmatoarea:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Matricele de adiacenta sunt avantajoase atunci cand este necesar sa se verifice frecvent prezenta arcelor intre anumite noduri. Daca insa numarul de varfuri n este mare, iar numarul de arce este sensibil mai mic decat n2, matricea de adiacenta are multe elemente nule si, deci, ocupa un spatiu prea mare in memorie.
Observatie: In exemplele date aici s-a considerat ca indexarea
incepe de la valoarea 1.
class GrafMA {
private Object[] varfuri;
private byte[][] matriceAdiacenta;
// Constructori, metode si clase interioare
}
Pentru elementele matricei de adiacenta s-a folosit tipul byte, deoarece
valorile elementelor pot fi numai 0 sau 1. Lista varfurilor contine referinte
la obiectele de informatie atasate fiecarui varf. Iindicii liniilor si
coloanelor din matricea de adiacenta sunt cei ai varfurilor corespunzatoare
din lista varfurilor.
In fisierul GrafMA.java este dat un exemplu de definire a clasei grafurilor cu matrice de adiacenta. Clasa contine metode de punere a varfurilor si a arcelor si de eliminare a varfurilor sau a arcelor. Un mic program de testare a acestei clase este dat in fisierul 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
}
}
In fisierul GrafLA.java este dat un exemplu de definire a unei clase de grafuri, in care matricile de adiacenta sunt incluse in varfuri. Clasa contine metode de punere si de eliminare a varfurilor si a arcelor. Un mic program de testare este dat in fisierul TestGrafLA.java. |
In fisierul Graf.java este dat un exemplu de
definire a clasei Graf, in care:
- varfurile grafului se identifica pentru eticheta, care este un String; - atat varfurilor, cat si arcelor li se pot atasa obiecte de informatie; - fiecare varf contine o lista a arcelor care au baza (originea) in varful respectiv; - varfurile sunt instante ale clasei interioare Varf, care contine campurile String eticheta, Object info si ArrayList arce; - arcele sunt instante ale clasei interioare Arc, care contine campurile Varf varf (o referinta catre varful de destinatie al arcului) si Object info; - clasa Graf contine metode pentru punerea si eliminarea de varfuri si arce, obtinerea si modificarea informatiilor din varfuri si arce, obtinerea de iteratori ai grafului. Varfurile grafului sunt pastrate in campul varfuri, care este o lista din clasa ArrayList. Pentru a se reduce timpul de cautare a unui varf dupa eticheta, varfurile sunt mentinute in aceasta lista sortate in ordinea crescatoare a etichetelor. Din aceasta cauza, cautarea unui nod si punerea unui varf in lista 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) si boolean puneVarf(String eticheta, Object info). Pentru cautarea unui varf se foloseste metoda cautarii binare. Clasa Graf contine si metode de explorare a grafului, care sunt prezentate in sectiunea urmatoare. Pentru a putea transmite graful intr-un flux de obiecte, folosind clasele de ObjectOutputStream pentru iesire si, respectiv, ObjectInputStream pentru intrare, clasa Graf si clasele ei interioare Varf si Arc implementeaza interfata Serializable. Pentru a se putea sorta varfurile, clasa interioara Varf implementeaza si interfata Comparable. Testarea clasei Graf se face in aplicatia din fisierul TestGraf.java. In aceasta aplicatie se creeaza un graf, in care se pun varfuri si arce, se elimina unele varfuri si arce, se parcurge graful in latime sau in adancime, se converteste graful in liste de varfuri parcurse in latime sau in adancime, se scrie graful intr-un fisier de obiecte, dupa care se citeste din acest fisier. Rezultatul fiecarei astfel de testari este afisat pe ecran. |