Grafuri-Reprezentarea in memoria calculatorului
Lectia 2
REPREZENTAREA GRAFURILOR ÎN MEMORIA CALCULATORULUI
Reprezentarea în memoria calculatorului a grafurilor presupune memorarea numărului de noduri si a legăturilor dintre acestea. În practică cele mai folosite moduri de reprezentare presupun utilizarea variabilelor de tip tablou sau a structurilor de date dinamice.
a. Matricea de adiacenţă:
Fie un graf neorientat cu n noduri. Pentru memorarea muchiilor acestui graf se utilizează o matrice binară, cu n linii şi n coloane, notată A, unde nreprezintă numărul de noduri din graf. Fiecare element A[i][j] din matricea de adiacenţă A poate avea următoarele valori:
Declarea maricei de adiacenţă:
int A[număr maxim de linii][număr maxim de coloane];
Observaţii:
1. Matricea de adiacenţă este simetrică faţă de diagonala principală;
2. Numărul de muchii din graf este egal cu numărul de valori de 1 aflate deasupra diagonalei principale;
3. Diagonala principală va conţine doar valori nule;
4. Numărul valorilor de 1 de pe linia X reprezintă gradul nodului X
Exemplu:
Graf neorientat
Matricea de adiacenta
b. Listele de vecini (liste de adiacență)
Listele de vecini conțin nodurile care sunt adiacente cu fiecare nod din graf:
Exemplu:
Graf neorientat
Lista de vecini
pentru nodul 1: 2, 5
<Exemplu !> <Exercițiu de desenare 2> <Aprofundare-Lectie AEL>
Listele de vecini se pot implementa static( cu ajutorul vectorilor) sau dinamic(cu ajutorul listelor simplu înlănţuite).
1. Implementarea statică a listelor de vecini:
1.1 Implementarea tată-fii: Se utilizează un vector V care pentru oricare nod i ce aparţine grafului păstrează toate nodurile j cu care acesta este adiacent (dacă graful este neorientat atunci trebuie respectată condiţia j > i, deoarece se repetă muchii ). Prin convenţie se separă nodurile tată şi adiacenţii lor prin valoarea 0.
...,0, Nodul i, fiul 1i, fiul 2i, fiul 3i,..., 0,...
Fie următorul graf, cu cinci noduri reprezentat grafic:
atunci implementarea folosind vectorul tata-fii este:
2. Implementarea dinamică a listelor de vecini:
În cazul acestei reprezentări fiecărui nod al grafului i se asociază o listă de adiacenţă în care sunt înlănţuite toate nodurile cu care acesta este conectat. Acest mod de reprezentare va studiat mai în capitolele următoare.
Exemplu:
c.Vectorul de muchii
Această modalitate de memorare presupune utilizarea unui vector cu un număr de elemente egal cu numărul de muchii din graf, fiecare element din vector memorând extremităţile unei muchii. Pentru a memora o muchie se va folosi o structură, pe care o vom numi muchie şi care se defineşte astfel:
struct muchie {
int x;
int y;
};
Declararea vectorului de muchii se face astfel:
muchie V[număr maxim de muchii];
Vectorul de muchii reprezentat grafic este:
unde m reprezintă numărul de muchii din graf.
Exemplu:
Graf neorientat
Vectorul de muchii
Aplicatii rezolvate:
1. Scrieți o funcție care citește de la tastatură numărul de noduri ale unui graf neorientat si matricea de adiacență.
Rezolvare:
2. Scrieți o funcție care afișează pe ecran matricea de adiacență a unui graf neorientat cu n noduri.
Rezolvare:
3. Scrieți o funcție care citește numărul de noduri și matricea de adiacență a unui graf neorientat din fișierul text graf.in. Fișierul text conține pe prima linie un număr natural care reprezintă numărul de noduri ale grafului iar pe următoarele n linii matricea de adiacență a grafului.
Rezolvare:
Fișierul text graf.in va conține valorile:
4
0 1 1 1
1 0 0 1
1 0 0 1
1 1 1 0
3. Scrieți o funcție cu numele matrice_adiacenta, care construiește matricea de adiacență a unui graf neorientat cu n noduri. Funcția va avea doi parametri și anume a- matrice pătratică și n numărul de noduri din graf. Datele de intrare se citesc din fișierul text graf.in care conține pe prima linie un număr natural care reprezintă numărul de noduri din graf iar pe următoarele linii perechi de valori naturale care reprezintă muchiile grafului.
Rezolvare:
Fișierul text graf.in va avea următorul conținut:
4
1 2
1 3
1 4
2 4
3 4
4. Scrieți o funcție cu numele lista_vecinilor care va afișa pe ecran lista vecinilor unui nod,transmis ca parametru. Funcția va avea un singur parametru, notat x, care reprezintă nodul pentru care se dorește afișarea listei vecinilor.
Rezolvare: