Informatică Algoritmi
Grafuri in informatica reprezentare 12a
Grafurile în informatică sunt structuri de date care modelează relații între obiecte, reprezentate prin noduri și muchii. Sunt folosite în rețele sociale, hărți și algoritmi.
Tipuri de reprezentare
- Matrice de adiacență Matrice pătratică unde A[i][j]=1 dacă există muchie de la nodul i la j. Exemplu: pentru 3 noduri, cost memorie O(n²).
- Liste de adiacență Vector de liste, fiecare listă conține vecinii unui nod. Exemplu: nodul 1 are vecinii [2,3], eficient pentru grafuri rare.
- Matrice de incidență Matrice cu noduri pe linii și muchii pe coloane, indicând conexiunile. Utilă pentru grafuri cu multe muchii.
Aplicații practice
- Căutare drumuri Algoritmi ca Dijkstra pentru drumuri minime în rețele de transport.
- Rețele sociale Nodurile sunt utilizatori, muchiile prietenii, pentru analiza comunităților.
- Sisteme de fișiere Directoare și fișiere ca noduri, legături ca muchii, pentru navigare ierarhică.
Alege reprezentarea în funcție de densitatea grafului: matrice pentru grafuri dense, liste pentru grafuri rare.