Informatică Algoritmi
Cum se implementeaza un graf in programare?
Un graf se implementează în programare folosind structuri de date care reprezintă noduri și muchii. Cele două metode principale sunt matricea de adiacență și lista de adiacență. Matricea de adiacență este o matrice pătratică unde fiecare celulă indică dacă există o muchie între două noduri, iar lista de adiacență stochează pentru fiecare nod o listă a vecinilor săi.
Matricea de adiacență
- Definiție O matrice bidimensională de dimensiune n x n, unde n este numărul de noduri. Valoarea 1 în poziția (i, j) indică o muchie de la nodul i la nodul j.
- Exemplu pentru 3 noduri Pentru un graf neorientat cu nodurile 0,1,2 și muchiile (0,1) și (1,2), matricea este [[0,1,0],[1,0,1],[0,1,0]].
- Complexitate spațiu O(n²), deci este eficientă pentru grafuri dense cu multe muchii.
- Verificare muchie Se face în O(1) accesând direct matricea[i][j].
Lista de adiacență
- Definiție Un array de liste, unde fiecare poziție i conține o listă cu nodurile vecine ale nodului i.
- Exemplu pentru același graf Lista este [[1], [0,2], [1]], deoarece nodul 0 are vecinul 1, nodul 1 are vecinii 0 și 2, iar nodul 2 are vecinul 1.
- Complexitate spațiu O(n + m), unde m este numărul de muchii, deci este eficientă pentru grafuri rare.
- Parcurgere vecini Se face în O(grade(i)), unde grade(i) este numărul de vecini ai nodului i.
Alege matricea de adiacență pentru grafuri dense și lista de adiacență pentru grafuri rare.