1
1. Problema reprezentarii
Un graf G=(V,E) are o multime de noduri V si o multime de muchii E. Ca sa putem prelucra un graf intr-un program, trebuie sa il reprezentam in memorie cu o structura de date.
Graful exemplu (folosit in toata lectia):
4 noduri: {1, 2, 3, 4}. Muchii neorientate: (1,2), (1,3), (2,3), (2,4).
Vizual: 1 este conectat cu 2 si 3; 2 este conectat cu 1, 3 si 4; 3 este conectat cu 1 si 2; 4 este conectat doar cu 2.
Cele doua reprezentari standard:
- Matricea de adiacenta — un tablou 2D de 0 si 1
- Listele de adiacenta — pentru fiecare nod, lista vecinilor sai
2
2. Matricea de adiacenta
Matricea de adiacenta A este un tablou de n x n intregi, unde:
A[i][j] = 1, daca exista muchia (i,j) in graf
A[i][j] = 0, daca nu exista muchia (i,j)
A[i][j] = 1, daca exista muchia (i,j) in graf
A[i][j] = 0, daca nu exista muchia (i,j)
Graful exemplu — matricea de adiacenta:
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 0 | 1 | 1 | 0 |
| 2 | 1 | 0 | 1 | 1 |
| 3 | 1 | 1 | 0 | 0 |
| 4 | 0 | 1 | 0 | 0 |
Gradul nodului 2 = suma liniei 2 = 1+0+1+1 = 3
Graf neorientat: matricea e simetrica (A[i][j] = A[j][i]). Diagonala principala = 0 (fara bucle).
Implementare Python (noduri indexate 1..n, pozitia 0 ignorata):
# Matrice de adiacenta -- graf neorientat, n=4 n = 4 mat = [[0] * (n + 1) for _ in range(n + 1)] muchii = [(1, 2), (1, 3), (2, 3), (2, 4)] for u, v in muchii: mat[u][v] = 1 mat[v][u] = 1 # neorientat: ambele sensuri print("Matricea de adiacenta (linii/coloane 1..4):") print(" ", " ".join(str(j) for j in range(1, n + 1))) for i in range(1, n + 1): print(f" {i} ", " ".join(str(mat[i][j]) for j in range(1, n + 1))) print() print("Gradul nodului 2:", sum(mat[2]))
Output real (rulat cu python):
Matricea de adiacenta (linii/coloane 1..4):
1 2 3 4
1 0 1 1 0
2 1 0 1 1
3 1 1 0 0
4 0 1 0 0
Gradul nodului 2: 3
3
3. Matricea de adiacenta pentru grafuri orientate
Intr-un graf orientat, arcul (i,j) merge din i catre j. Punem 1 DOAR la mat[i][j], NU si la mat[j][i].
Matricea nu mai este simetrica in general.
Grad exterior (grad+) al nodului i = suma liniei i = nr. arce care pleaca din i
Grad interior (grad-) al nodului i = suma coloanei i = nr. arce care intra in i
Matricea nu mai este simetrica in general.
Grad exterior (grad+) al nodului i = suma liniei i = nr. arce care pleaca din i
Grad interior (grad-) al nodului i = suma coloanei i = nr. arce care intra in i
Exemplu graf orientat: arce 1→2, 1→3, 2→4, 3→2
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 0 | 1 | 1 | 0 |
| 2 | 0 | 0 | 0 | 1 |
| 3 | 0 | 1 | 0 | 0 |
| 4 | 0 | 0 | 0 | 0 |
Cum citim gradele din matrice:
# grade pentru graf orientat (mat deja construit, n=4) for i in range(1, n + 1): grad_ext = sum(mat[i][j] for j in range(1, n + 1)) # pleaca din i grad_int = sum(mat[j][i] for j in range(1, n + 1)) # intra in i print(f" nod {i}: grad+={grad_ext}, grad-={grad_int}")
Output real (rulat cu python):
nod 1: grad+=2, grad-=0 nod 2: grad+=1, grad-=2 nod 3: grad+=1, grad-=1 nod 4: grad+=0, grad-=1
Interpretare:
Nodul 1 are grad exterior 2 (pleaca 2 arce) si grad interior 0 (nu intra nimic). Nodul 4 are grad exterior 0 (nu pleaca nimic) si grad interior 1 (intra un arc din 2).
4
4. Listele de adiacenta
Listele de adiacenta: pentru fiecare nod i stocam o lista cu toti vecinii sai directi.
adj[i] = lista tuturor nodurilor j cu care i este conectat (exista muchia sau arcul i→j).
Gradul nodului i = len(adj[i]).
adj[i] = lista tuturor nodurilor j cu care i este conectat (exista muchia sau arcul i→j).
Gradul nodului i = len(adj[i]).
Graful exemplu — listele de adiacenta:
nod 1: [2, 3] nod 2: [1, 3, 4] nod 3: [1, 2] nod 4: [2]
Gradul nodului 2 = len(adj[2]) = 3 (vecini: 1, 3, 4).
Implementare Python:
# Liste de adiacenta -- graf neorientat, n=4 n = 4 adj = [[] for _ in range(n + 1)] # adj[0] neutilizat muchii = [(1, 2), (1, 3), (2, 3), (2, 4)] for u, v in muchii: adj[u].append(v) adj[v].append(u) # neorientat print("Listele de adiacenta:") for i in range(1, n + 1): print(f" nod {i}: {adj[i]}") print() print("Gradul nodului 2:", len(adj[2])) print("Vecini ai nodului 1:", adj[1])
Output real (rulat cu python):
Listele de adiacenta: nod 1: [2, 3] nod 2: [1, 3, 4] nod 3: [1, 2] nod 4: [2] Gradul nodului 2: 3 Vecini ai nodului 1: [2, 3]
5
5. Comparatie: cand folosim ce?
Alegerea reprezentarii depinde de densitatea grafului si de operatiile frecvente.
| Criteriu | Matrice adiacenta | Liste adiacenta |
|---|---|---|
| Spatiu | O(n²) | O(n + m) |
| Exista muchia (i,j)? | O(1) — acces direct | O(grad(i)) — cauta in lista |
| Parcurge vecinii lui i | O(n) — parcurge toata linia | O(grad(i)) — doar vecinii reali |
| Potrivit pentru | Grafuri dense (m ≈ n²) | Grafuri rare (m << n²) |
| Cazul tipic Bac | n mic (≤ 10), usor de desenat pe foaie | n mare, algoritmi DFS/BFS |
Analogie
Matricea e ca un tabel de prezenta pentru o clasa: are o casuta pentru fiecare pereche de elevi, chiar si pentru cei care nu se cunosc (spatiu irosit). Listele sunt ca un carnet de adrese: fiecare persoana noteaza DOAR contactele pe care le are — compact si eficient.
6
6. Implementare C++ EXCLUSIV INTENSIV
⚡ Sectiune doar pentru intensiv informatica
La profilul intensiv implementam ambele reprezentari in C++. Matricea de adiacenta foloseste un tablou 2D static; listele de adiacenta folosesc vector<int>.
Matrice de adiacenta in C++:
#include <iostream> using namespace std; int main() { int n = 4; int mat[5][5] = {}; int u[] = {1, 1, 2, 2}; int v[] = {2, 3, 3, 4}; int m = 4; for (int i = 0; i < m; i++) { mat[u[i]][v[i]] = 1; mat[v[i]][u[i]] = 1; } cout << "Matrice adiacenta (n=" << n << "):" << endl; cout << " "; for (int j = 1; j <= n; j++) cout << j << " "; cout << endl; for (int i = 1; i <= n; i++) { cout << " " << i << " "; for (int j = 1; j <= n; j++) cout << mat[i][j] << " "; cout << endl; } int grad2 = 0; for (int j = 1; j <= n; j++) grad2 += mat[2][j]; cout << "Gradul nodului 2: " << grad2 << endl; return 0; }
Output real (compilat g++ -std=c++17, apoi rulat):
Matrice adiacenta (n=4):
1 2 3 4
1 0 1 1 0
2 1 0 1 1
3 1 1 0 0
4 0 1 0 0
Gradul nodului 2: 3
Liste de adiacenta in C++ cu vector:
#include <iostream> #include <vector> using namespace std; int main() { int n = 4; vector<int> adj[5]; vector<pair<int,int>> muchii = {{1,2},{1,3},{2,3},{2,4}}; for (auto [u, v] : muchii) { adj[u].push_back(v); adj[v].push_back(u); } cout << "Liste de adiacenta (n=" << n << "):" << endl; for (int i = 1; i <= n; i++) { cout << " nod " << i << ": ["; for (int j = 0; j < (int)adj[i].size(); j++) { if (j) cout << ", "; cout << adj[i][j]; } cout << "]" << endl; } cout << "Gradul nodului 2: " << adj[2].size() << endl; return 0; }
Output real (compilat g++ -std=c++17, apoi rulat):
Liste de adiacenta (n=4): nod 1: [2, 3] nod 2: [1, 3, 4] nod 3: [1, 2] nod 4: [2] Gradul nodului 2: 3
Ambele programe produc acelasi rezultat. Diferenta: matricea aloca intotdeauna n*n celule, listele aloca doar spatiul pentru muchiile existente.