Reprezentarea grafurilor in calculator

Grafurile pot fi reprezentate in calculator prin diferite structuri de date. In porgramarea orientata pe obiecte, aceste structuri se constituie in clase. Cel mai frecvent se reprezinta grafuri orientate. Grafurile georientate sunt, de regula reprezentate la fel ca cele orientate, dar fiecare muchie este reprezentata printr-o pereche de arce, orientate in ambele sensuri.

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

Reprezentarea prin matrice de adiacente

Matricea de adiacenta a unui graf orientat este o matrice patrata E, avand ordinul egal cu numarul de noduri al grafului, in care E[i,j]=1 daca exista un arc de la nodul i la nodul j si E[i,j]=0 in caz contrar.

Fie graful din figura 1, in care nodurile sunt numerotate.


- Figura 1 -

Matricea de adiacenta a acestui graf este urmatoarea:
 

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

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:
 

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

Reprezentarea prin tablou al arcelor (muchiilor)

Cand numarul de arce este sensibil mai mic decat n2/2, unde n este numarul de varfuri, poate fi convenabila inlocuitrea matricei de adiacente printr-un tablou al arcelor.

Tabloul arcelor este o matrice cu doua coloane, in care pe fiecare linie sunt inscrisi indicii bazei si varfului unui arc. De exemplu, graful orientat din figura 1 poate fi reprezentat prin umatorul tablou al arcelor:
 

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

In cazul grafurilor neorientate, tabloul arcelor poate fi inlocuit cu tabloul muchiilor. De exemplu, graful neorientat din figura 2 poate fi reprezentat prin urmatorul 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 adiacente

Reprezentarea prin tablouri de arce sau muchii prezinta desavantajul ca operatiile de cautare a unui arc (muchie) au complexitatea O(n). Pentru a reduce numarul de pasi de cautare, in cazul grafurilor cu numar mare de varfuri si de arce se prefera folosirea listelor de adiacente. In acest caz, fiecarui element de indice i din tabloul varfurilor i se asociaza o lista, care contine indicii varfurilor de destinatie ale arcelor care pornesc din varful i. Toate aceste liste pot fi plasate intr-un singur tablou unidimensional, iar in tabloul varfurilor se indica pentru fiecare element indicele de la care incepe lista corespunzatoare in tabloul listelor. Ca exemplu, in figura 3 este data reprezentarea prin liste de adiacente a grafului din figura 1.


- Figura 3 -

In figura 3, V este tabloul varfurilor, iar A este tabloul listelor de adiacente. Elementul V[0] are valoarea -1, deoarece in graful din figura 1 numerotarea varfurilor a inceput de la 1, deci nu exista nod cu numarul 0. Elementul V[1] contine valoarea 0, care este indicele din tabloul A, de la care incepe lista de adiacente a varfului 1. Exista arcele 1-1, 1-2 si 1-4. Lista se termina cu un element care are valoarea conventionala -1.
In mod similar, listele de adiacente ale varfurilor 2, 3 si 4 incep, respectiv, de la elementele A[4], A[6] si A[8] ale tabloului listelor de adiacente A.

Intrucat numarul de arce care pornesc dintr-un varf oarecare este relativ mic, se poate considera ca complexitatea cautarii unui arc intr-o astfel de reprezentare este O(1). Daca arcelor si varfurilor li se ataseaza si anumite informatii, atunci V si A sunt tablouri de obiecte, iar fiecare astfel de obiect, in afara de indicele folosit pentru legatura, contine si informatia atasata varfului sau arcului respectiv.

Reprezentarea obiectuala a grafurilor in Java

Intrucat limbajul Java este orientat pe obiecte, este normal ca toate structurile de date, deci si grafurile, sa fie reprezentate prin clase. Avand in vedere diversitatea grafurilor, nu exista in prezent clase predefinite. Vom da aici numai unele idei privind diferite modalitati de reprezentare.

Reprezentarea cu matrice de adiacente

Daca arcele grafului nu au atasate informatii (nu sunt etichetate, ponderate, colorate etc), graful G=(V, E) poate fi reprezentat ca o clasa, care contine  o lista a varfurilor implementata ca tablou si o matrice de adiacenta ca in exemplul urmator:

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.

Reprezentarea cu liste de adiacente inglobate in varfuri

O alta posibilitate de reprezentare a grafurilor, este sa se considere ca acestea sunt constituite din varfuri, care inglobeaza fiecare atat informatia atasata, cat si o lista a varfurilor adiacente catre care pornesc arce care au baza (originea) in varful respectiv. Iata un exemplu de astfel de clasa:

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.

Atasarea de informatii la varfuri si arce

Pot fi imaginate diferite modalitati de atasare de informatie la varfurile si arcele grafului. Clasa GrafLA din sectiunea precedenta contine deja etichete si obiecte de informatie atasate varfului. In mod similar cu clasa Varf, se poate introduce o clasa Arc, care sa contina atat o referinta la nodul de destinatie a arcului, cat si o eticheta si o un obiect de informatie atasate arcului respectiv. In lista de adiacente a varfului de origine, in loc sa se introduca doar referinte catre nodurile catre care pornesc arce, se introduc insasi instantele clasei Arc corespunzatoare arcelor respective.
 
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.



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunarea de Jos" din Galati