Un graf este o mulțime de noduri conectate prin muchii. Cele două reprezentări standard sunt lista de adiacență (fiecare nod stochează vecinii săi) și matricea de adiacență (o grilă V×V de valori booleane). Alegerea depinde de densitatea grafului.
Un graf este o mulțime de noduri conectate prin muchii. Cele două reprezentări standard sunt lista de adiacență (fiecare nod stochează vecinii săi) și matricea de adiacență (o grilă V×V de valori booleane). Alegerea depinde de densitatea grafului.
Graph: 0 - 1
| |
2 - 3
Adjacency list: Adjacency matrix:
0: [1, 2] 0 1 2 3
1: [0, 3] 0 [0 1 1 0]
2: [0, 3] 1 [1 0 0 1]
3: [1, 2] 2 [1 0 0 1]
3 [0 1 1 0]
# Adjacency list (dict of lists) — preferred for sparse graphs
adj = {0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}
neighbors = adj[1] # O(1) to get a vertex's neighbors
# Adjacency matrix
matrix = [[0]*4 for _ in range(4)]
matrix[0][1] = matrix[1][0] = 1
has_edge = matrix[0][1] == 1 # O(1) edge lookup
| Lista de adiacență | Matricea de adiacență | |
|---|---|---|
| Spațiu | O(V + E) | O(V²) |
| Muchie există? | O(grad) | O(1) |
| Iterare vecini | O(grad) | O(V) |
| Optim pentru | grafuri rare | grafuri dense |
Cea mai mare parte din grafurile din lumea reală (rețele sociale, hărți rutiere, grafuri de dependență) sunt rare, deci listele de adiacență economisesc un spațiu imens și accelerează traversări precum BFS/DFS.
Cunoașterea acestui compromis vă permite să alegeți reprezentarea care ține algoritmii grafului dvs. eficienți, în loc să folosiți accidental memorie O(V²).