Grafuri

Definire:

Graful, asemenea arborelui, este o structura în care relatia dintre nodul parinte si nodul fiu este una ierarhica, dar care este mai putin restrictiva în sensul ca un nod are mai multi succesori, dar si mai multi predecesori. El este definit ca o colectie de date reunite în doua multimi: multimea N = { N1, N2, …, Nn | n – numarul de noduri al grafului}ce contine toate nodurile grafului si multimea A = { ( Ni, Nj ) = Aij | Ni, Nj N si i,j = 1,n cu i j}care contine arcele dintre doua noduri vecine.

Graful este de mai multe tipuri, fiind clasificat în functie de :

- directia arcelor; în cazul în care arcele dintre nodurile grafului sunt nedirectionate atunci graful este unul neorientat; când exista sens între doua noduri Ni, Nj si arcul este directionat (Ni Nj sau Ni Nj sau NiNj) atunci graful este unul orientat;

- greutatea arcelor; daca oricare arc dintre doua noduri ale grafului are asociata o valoare numerica (care reprezinta de cele mai multe ori distanta, durata de timp sau costul), atunci graful este cu greutate; în cazul în care arcele nu au asociate valori numerice, graful este unul fara greutate;

- existenta arcelor; daca într-un graf nu exista nici un nod izolat, altfel spus pentru oricare nod Ni cu i = 1..n exista cel putin un nod Nj cu 1 j n si i j pentru care exista arcul Aij asociat, atunci graful este conectat; un graf este neconectat daca exista cel putin un nod izolat.

Exista numeroase metode de reprezentare în memoria calculatorului a grafului, fiecare cu avantajele si dezavantajele ei :

- matricea de adiacenta;

- liste înlantuite;

- un vector de pointeri la liste simple sau dublu înlantuite de noduri adiacente;

- o lista simplu sau dublu înlantuita de pointeri la liste simple sau dublu înlantuite de noduri adiacente;

- un vector de pointeri la liste simple sau dublu înlantuite de arce.

Dintre toate, cele mai utilizate metode sunt primele doua.

Reprezentare prin matricea de adiacenta:

Reprezentarea prin matrice de adiacenta a grafului este eficienta când se cunoaste numarul nodurilor si numarul mediu al arcelor; acesta din urma trebuie sa fie mare pentru ca gradul de umplere al matricei de adiacenta sa fie scazut.

Initial matricea de adiacenta are toate elementele egale cu valoarea 0. Pentru a reprezenta arcul Aij dintre nodurile Ni si Nj (orientat de la Ni la Nj) la intersectia liniei i cu coloana j se trece valoarea 1, în cazul grafului cu fara greutate, sau greutatea arcului, pentru graful cu greutate.

Lungimea drumului dintre doua noduri ale unui graf orientat fara greutate este data de numarul de arce.

Reprezentare prin liste inlantuite:

Se defineste structura arc care este asociata elementelor din multimea arcelor:

struct arc

{

struct nodgraf * destinatie; // adresa nodului catre care exista arc

struct arc* next_arc; // referinta catre elementul urmator din lista de arce

int greutate; //greutatea arcului

}

Este vorba de o lista a arcelor ce este construita dinamic. Structura este cea a unei liste oarecare, cuprinzând informatia propriu-zisa, greutatea arcului, precum si cea necesara înlantuirii în lista, adresa elementului urmator.

La crearea grafului se introduc initial informatiile nodurilor, creându-se astfel lista lor. Dupa aceasta se vor crea listele de arce introducându-se informatia nodului sursa, a nodului destinatie si greutatea arcului.