Reprezentarea grafurilor în calculator

Grafurile pot fi reprezentate în calculator prin diferite structuri de date. În porgramarea orientată pe obiecte, aceste structuri se constituie în clase. Cel mai frecvent se reprezintă grafuri orientate. Grafurile neorientate sunt, de regulă reprezentate la fel ca cele orientate, dar fiecare muchie este reprezentată printr-o pereche de arce, orientate în ambele sensuri (unul de la vârful.Vi la Vj, iar celălalt invers).

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).

Reprezentarea prin matrice de adiacențe

Matricea de adiacențe a unui graf orientat este o matrice patrată E, având ordinul egal cu numărul de noduri al grafului, în care elementul E[i,j]=1 dacă există un arc de la nodul i la nodul j si E[i,j]=0 în caz contrar.

Fie graful din figura 1, în care nodurile sunt numerotate.


- Figura 1 -

Matricea de adiacențe a acestui graf este următoarea:
 

1
1
0
1
0
0
0
1
0
1
0
0
1
1
1
1

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:
 

0
1
1
1
0
0
0
1
0
1
0
0
0
0
1
1
0
1
1
1
0
1
0
1
0
0
0
0
0
0
1
0
0
1
0
0
0
1
0
1
0
1
0
0
0
0
0
1
0

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.
 
 

Reprezentarea prin tablou al arcelor (muchiilor)

Când numarul de arce este sensibil mai mic decât n2/2, unde n este numărul de vârfuri, poate fi convenabilă înlocuitrea matricei de adiacențe printr-un tablou al arcelor.

Tabloul arcelor este o matrice cu două coloane, în care pe fiecare linie sunt inscriși indicii bazei și vârfului unui arc. De exemplu, graful orientat din figura 1 poate fi reprezentat prin umătorul tablou al arcelor:
 

1
1
1
2
1
4
2
4
3
2
4
1
4
2
4
3
4
4

În cazul grafurilor neorientate, tabloul arcelor poate fi înlocuit cu tabloul muchiilor. De exemplu, graful neorientat din figura 2 poate fi reprezentat prin următorul tablou al muchiilor:
 

1
2
1
3
1
4
2
3
3
4
3
5
3
6
5
6
6
7

Reprezentarea prin liste de adiacențe

Reprezentarea prin tablouri de arce sau muchii prezintă desavantajul ca operațiile de căutare a unui arc (muchie) au complexitatea O(n). Pentru a reduce numărul de pași de căutare, în cazul grafurilor cu numar mare de vârfuri și de arce se preferă folosirea listelor de adiacențe. În acest caz, fiecărui element de indice i din tabloul vârfurilor i se asociază o listă, care conține indicii vârfurilor de destinație ale arcelor care pornesc din vârful i. Toate aceste liste pot fi plasate într-un singur tablou unidimensional, iar în tabloul vârfurilor se indică pentru fiecare element indicele de la care începe lista corespunzătoare în tabloul listelor. Ca exemplu, în figura 3 este dată reprezentarea prin liste de adiacențe a grafului din figura 1.


- Figura 3 -

În figura 3, V este tabloul vârfurilor, iar A este tabloul listelor de adiacențe. Elementul V[0] are valoarea -1, deoarece în graful din figura 1 numerotarea vârfurilor a început de la 1, deci nu există nod cu numărul 0. Elementul V[1] conține valoarea 0, care este indicele din tabloul A, de la care începe lista de adiacențe a vârfului 1. Există arcele 1..1, 1..2 și 1..4. Lista se termină cu un element care are valoarea convențională -1.
În mod similar, listele de adiacențe ale vârfurilor 2, 3 si 4 încep, respectiv, de la elementele A[4], A[6] si A[8] ale tabloului listelor de adiacențe A.

Întrucât numărul de arce care pornesc dintr-un vârf oarecare este relativ mic, se poate considera că complexitatea căutarii unui arc într-o astfel de reprezentare este O(1). Dacă arcelor și vârfurilor li se atașează și anumite informații, atunci V si A sunt tablouri de obiecte, iar fiecare astfel de obiect, în afară de indicele folosit pentru legatură, conține și informația atașată vârfului sau arcului respectiv.

Reprezentarea obiectuală a grafurilor în Java

Întrucât limbajul Java este orientat pe obiecte, este normal ca toate structurile de date, deci și grafurile, să fie reprezentate prin clase. Având în vedere diversitatea grafurilor, nu există în prezent clase predefinite. Vom da aici numai unele idei privind diferite modalități de reprezentare.

Reprezentarea cu matrice de adiacențe

Dacă arcele grafului nu au atașate informații (nu sunt etichetate, ponderate, colorate etc), graful G=(V, E) poate fi reprezentat ca o clasă, care conține  o listă a vârfurilor implementată ca tablou și o matrice de adiacența ca în exemplul următor:

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.

Reprezentarea cu liste de adiacențe înglobate în vârfuri

O altă posibilitate de reprezentare a grafurilor, este să se considere că acestea sunt constituite din vârfuri, care înglobează fiecare atât informația atașată, cât și o listă a vârfurilor adiacente, către care pornesc arce care au baza (originea) în vârful respectiv. Iată un exemplu de astfel de clasă:

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.

Atașarea de informații la vârfuri și arce

Pot fi imaginate diferite modălități de atașare de informație la vârfurile și arcele grafului. Clasa GrafLA din secțiunea precedentă conține deja etichete și obiecte de informație atașate vârfurilor. În mod similar cu clasa Vârf, se poate introduce o clasă Arc, care să conțină atat o referință la nodul de destinație a arcului, cât și o etichetă și un obiect de informație atașate arcului respectiv. În lista de adiacențe a vârfului de origine, în loc să se introducă doar referințe către nodurile spre care pornesc arce, se introduc referințe la instanțele clasei Arc corespunzătoare arcelor respective.
 
Î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.



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunărea de Jos" din Galați