Lucrarea nr.8

TDA GRAF. IMPLEMENTARE

1.TDA GRAF

1.1.Definitii

Un graf este o colecție de noduri si arce. Nodurile pot fi identificate prin chei, iar arcele reprezinta conexiuni intre noduri.

Un graf G poate fi notat G=(N,A), unde N e multimea nodurilor, iar A a arcelor.

Ordinul |G| unui graf G e dat de numarul nodurilor.

Arcul a ce leaga nodurile x si y se spune ca este incident cu x si y si se noteaza a~(x,y), iar x si y se spune ca sunt adiacente.

Gradul unui nod este egal cu numarul arcelor incidente lui. Un graf regulat are acelasi grad pentru toate nodurile.

Grafurile pentru care orice arc (x,y)=(y,x) sunt neorientate.

Bucla e un arc de forma a ~ (x,x).

Un graf simplu ( toate discutiile urmatoare se vor referi la astfel de grafuri ) nu accepta existenta arcelor multiple, deci intre orice doua noduri poate exista cel mult un arc.

Un graf G'=(N',A') este subgraf al unui graf G=(N,A) daca N' Ì N, A' Ì A si orice arc a' ~ (x,y) din A' conecteaza noduri din N' ( x si y sunt din N' ).

Un drum de la x la y e o succesiune de noduri conectate prin arce : x, n1, n2, n3,..., y, lungimea drumului fiind data de numarul de arce.

Un drum este simplu daca nodurile din drum sunt distincte (cu exceptia posibila a primului si ultimului ).

Un ciclu e un drum cu acelasi nod initial si final.

Doua noduri x si y se numesc conectate daca exista cel putin un drum intre ele.

Un graf este conex daca toate perechile sale de noduri sunt conectate.

Orice graf neconex este format din componenete conexe.

Se observa ca arborii sunt cazuri particulare ale grafurilor.

Un arbore de acoperire pentru un graf conex, este un subgraf care contine toate nodurile grafului, dar numai atâtea conexiuni câte sunt necesare formarii unui arbore. Pentru orice graf se poate gasi o padure de arbori de acoperire, cate unul pentru fiecare componenta conexa.

Un graf complet de ordinul n contine arcuri intre toate perechile ce se pot forma cu cele n noduri ( deci contine n (n-1)/2 arce ).

Un graf e rar daca are relativ putine arce si dens daca e aproape complet.

Un graf e orientat daca arcele sale au un sens precizat.

Un graf este ponderat daca arcelor sale li se asociaza cate o valoare.

Un graf ponderat orientat se numeste retea.

1.2.Operatorii TDA Graf

a) Setul extins de operatori

Se folosesc notatiile: Tip_Element - tipul nodurilor, cu campurile de Tip_Cheie si Tip_Info
g - graf
indic_Nod - indicator la nod
indic_Arc - indicator la arc
e - variabila de Tip_Element
k,k1,k2 - variabile de Tip_Cheie
x - variabila de Tip_Info
b - variabila booleana.

Operatorii setului extins sunt:

1. Init_Graf(g) - creaza graful vid
2. Graf_Vid(g) - verifica daca g e vid
3. Graf_Plin(g) - verifica daca g e plin, deci nu mai pot fi adaugate alte noduri (depinde de varianta de implementare)
4. Cheie_Elem_Graf(g,e) - returneaza cheia nodului e al grafului g
5. Cauta_Cheie_Graf(g,k) - returneaza true daca cheia k e gasita in g
6. Indica_Nod(g,k,indic_Nod) - indic_Nod va lua valoarea indicatorului spre nodul cu cheia k
7. Indica_Arc(g,k1,k2,indic_Arc) - indic_Arc va indica spre arcul ce conecteaza nodurile cu cheile k1 si k2
8. Arc_Vid(g,indic_Arc) - verifica daca indic_Arc este vid
9. Inser_Nod(g,e) - se insereaza in g nodul e ca nod izolat
10. Inser_Arc(g,k1,k2) - se insereaza arcul ce conecteaza nodurile de chei k1 si k2
11. Suprim_Nod(g,indic_Nod) - se suprima nodul indicat, cu toate arcele incidente
12. Suprim_Arc(g,indic_Arc) - suprima arcul precizat
13. Actualiz_Nod(g,indic_Nod,x) - actualizeaza cu x informatia nodului indicat
14. Furniz_Nod(g,indic_Nod) - returneaza valoarea nodului (de Tip_Element) indicat
15. Travers_Graf(g,Vizita(Lista_de_argumente)) - parcurge toate nodurile grafului g, pentru fiecare nod executand prelucrarea Vizita

b) Setul restrans de operatori

- graful contine multimile ATOM si POZITIE
- g=(P,R,f) - unde
- P - subset finit al multimii POZITIE
- f - functie P-> ATOM
- R - relatie simetrica in P ( si ireflexiva daca nu se admit bucle )
- p,q - variabile de tip POZITIE
- e - variabila de tip ARC
- a - variabila de tip ATOM

Operatorii setului restrans sunt:

1. Creaza(g) - creaza graful vid g
2. Adiacent(p,q,g) - verifica daca p si q sunt adiacente
3. Modifica(a,p,g) - se modifica la a zona de date a nodului indicat de p
4. Furnizeaza(p,g) - returneaza zona de date a nodului indicat de p
5. Suprim_Nod(p,g) - se suprima nodul indicat cu toate arcele adiacente
6. Suprim_Arc(e,g) - se suprima arcul a
7. Inser_Nod(p,g) - se adauga nodul indicat, ca nod izolat
8. Inser_Arc(e,g) - se adauga arcul e

2.TEHNICI DE IMPLEMENTARE A TDA GRAF

2.1.Implementarea grafurilor prin matrici de adiacenta

Se realizeaza mai intai o corespondenta intre numele nodurilor si multimea indicilor, in una din variantele :

• numele pot fi chiar indicii sau literele alfabetului
• corespondenta se mai poate face prin :
  • tablouri
  • liste
  • arbore binar
  • tabela ( tehnica dispersiei )

Varianta de implementare cu matrice de adiacente: O varianta de implementare cu matrice de adiacente este data mai jos, graful aparand ca o structura ce contine contorul nodurilor, tabloul nodurilor si matricea de adiacente ( arce ). Tabloul nodurilor nu este ordonat dupa chei. Un nod nou se adauga in continuarea celor existente. Suprimarea unui nod se realizeaza prin copierea ultimei intrari peste cea care se sterge in tabloul Noduri, respectiv a conexiunilor ultimului nod peste cele ale nodului sters in Arce:

const NumarNoduri = .......;

type  TipCheie    = .......;
 TipInfo     = .......;
 TipElement  = record
             	  Cheie: TipCheie;
      	  Info : TipInfo
           	end;

 TipContor      = 0..NumarNoduri;
 TipIndex       = 1..NumarNoduri;
 TipTablouElem  = array[TipIndex] of TipElement;
 TipMatrAdj     = array[TipIndex,TipIndex] of boolean;

 Graf           = record
             	    Contor  : TipContor;
             	    Noduri  : TipTablouElem;
             	    Arce    : TipMatrAdj
                  end;

 TipArc         = record
             	     linie,
             	     coloana: TipIndex
                  end;

var g: Graf;
          
procedure InserNod(var g: Graf;e: TipElement);
{ insertia unui nod izolat }

var i,j: TipIndex;

begin
  with g do
     begin
       contor := contor + 1;   { se plaseaza e
       Noduri[contor] := e;      in nodul nou}
       for i := 1 to contor do
         Arce[i,contor] := false { se initializeaza
       for j := 1 to contor do      matricea de adiacente
         Arce[contor,j] := false    pentru nodul nou }
     end {with}
end; {InserNod}

procedure InserArc(var g: Graf; indicArc: TipArc);

begin
  g.Arc[indicArc.linie,indicArc.coloana] := true;
  g.Arc[indicArc.coloana,indicArc.linie] := true
end; { InserArc }

procedure SuprimNod(var g: Graf; indicNod: TipIndex);
 { suprima nodul dat impreuna cu toate arcele incidente }
var i,j: TipIndex;

begin
 with g do
    begin
       Noduri[indicNod] := Noduri[contor];
       for j := 1 to contor do
           Arce[indicNod,j] := Arce[contor,j];
       for i := 1 to contor do
           Arce[i,indicNod] := Arce[i,contor];
       contor := contor - 1
     end { with }
      end; { SuprimNod }

procedure SuprimArc(var g: Graf; indicArc: TipArc);

 	 begin
         g.Arc[indicArc.linie,indicArc.coloana] := false;
         g.Arc[indicArc.coloana,indicArc.linie] := false
 	end; { SuprimArc }

Construirea unui graf necesita cate un apel la InserNod pentru fiecare nod, respectiv cate un apel la InserArc pentru fiecare arc. Daca nodurile s-ar introduce ordonate dupa cheie in Noduri, localizarea unei chei poate fi facuta folosind cautarea binara.

2.2.Implementarea grafurilor prin structuri de adiacenta

Varianta a.) inceputurile listelor de inlantuiri se pastreaza intr-un tablou Stradj. Listele pot partaja acelasi nod final fictiv. Orice insertie se face la inceputul listei. Trebuie realizata o corespondenta intre numele nodurilor si multimea indicilor, prin functia index. Insertia unui arc implica insertia unui nod in fiecare din cele doua liste corespunzatoare nodurilor conectate.

   const maxN = 100;

   type legatura = ^Nod;
        Nod = record
                nume: integer; { index }
                urm: legatura
              end; { nod }

   var  Stradj: array[1..maxN] of legatura;

          Fiecare element din StrAdj ar putea retine si cheia nodului, astfel
nemaifiind necesara o alta asociere:

     StrAdj:array[1..maxN] of record
                           cheie:TipCheie;
                           adj:legatura
                    	   end;

Varianta b) Graful se implementeaza ca multilista: o lista a nodurilor contine, pentru fiecare nod, inceputul listei de adiacente. Nodurile pot fi pastrate ordonat sau nu, in lista nodurilor cat si in cele de adiacente. Se precizeaza ca valorile nodurilor sunt pastrate integral in lista de noduri, in lista de arce apar numai cheile.

type TipCheie   = .....;
TipInfo    = .....;
TipElement = record
              cheie: TipCheie;
              info : TipInfo
             end;

 PtrAdj    = ^Adj;

 Adj       = record
               cheieAdj: TipCheie;
               urmAdj  : PtrAdj
             end;

 ptrNod    = ^Nod;
 graf      = ptrNod;

 Nod       = record
                elem   : TipElement;
                urmNod : ptrNod;
                incepAdj : PtrAdj
              end;

TipArc     = record
                v1,v2 : ptrNod
             end;

var g : graf;  

Suprimarea unui nod din graf presupune nu numai suprimarea nodului respectiv, ci si a tuturor arcelor incidente acestui nod. Fie k cheia nodului de suprimat. Pentru fiecare nod k2 din lista de adiacente a lui k, se suprima arcul (k,k2) prin stergerea lui k din lista de adiacente a lui k2 si pe k2 din lista de adiacente a lui k.

Varianta c.) Ceea ce este diferit fata de varianta anterioara este faptul ca in listele de adiacente nu apar cheile nodurilor, ci pointerii spre nodurile adiacente din lista (principala) de noduri ale grafului, algoritmii de prelucrare devenind mai simpli.

type POZITIE = ^CelulaListNod;
PointListArc = ^CelulaListArc;

CelulaListNod = record
  data  : ATOM; { informatie apartinind nodului }
  urm : POZITIE; { urmatoarea celula in lista nodurilor }
  incep : PointListArc { pointer la lista de adiacente }
 end;

CelulaListArc = record
  data   : ...; { informatie atasata arcului }
  nod    : POZITIE; { destinatia arcului }
  urm    : PointListArc { inlantuirea in lista de arce }
 end;

 ARC = record
   nod1,nod2: POZITIE
 end;

 GRAF = POZITIE;