# Reprezentarea grafurilor: matrice și liste de adiacență

> Pagina: https://bacalaurescu.ro/informatica/lectii/grafuri-neorientate/graf-reprezentare
> Markdown: https://bacalaurescu.ro/informatica/lectii/grafuri-neorientate/graf-reprezentare.md
> Sursa: Bacalaurescu (bacalaurescu.ro), conținut gratuit pentru BAC 2027.

Materia: [Informatică](https://bacalaurescu.ro/informatica)

Capitolul: [Grafuri neorientate](https://bacalaurescu.ro/informatica/lectii/grafuri-neorientate)
Actualizat: 2026-09-22

Matricea de adiacență, listele de adiacență și calculul gradelor, în 4 limbaje.

## Matricea de adiacență

Pentru un graf cu $n$ noduri, matricea $a$ are $n \times n$ elemente:

$$a[i][j] = \begin{cases} 1, & \text{dacă există muchie între } i \text{ și } j \\ 0, & \text{altfel} \end{cases}$$

Proprietăți la graf **neorientat**:
- matricea e **simetrică**: $a[i][j] = a[j][i]$;
- diagonala principală e formată din zerouri (fără bucle);
- **gradul nodului $i$** = suma elementelor de pe linia $i$;
- numărul de muchii = suma tuturor elementelor, **împărțită la 2**.

## Listele de adiacență

Pentru fiecare nod se reține lista vecinilor lui. Ocupă mai puțină memorie când graful are puține muchii (graf rar).

## Exemplu rezolvat

Graf cu 4 noduri și muchiile [1,2], [1,3], [2,3], [3,4]:

| | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| **1** | 0 | 1 | 1 | 0 |
| **2** | 1 | 0 | 1 | 0 |
| **3** | 1 | 1 | 0 | 1 |
| **4** | 0 | 0 | 1 | 0 |

Gradele: $d(1)=2$, $d(2)=2$, $d(3)=3$, $d(4)=1$. Suma = 8 = 2 × 4 muchii. ✓

> [!RETINE]
> Verificarea rapidă la examen: suma tuturor elementelor din matrice trebuie să fie **dublul numărului de muchii**. Dacă nu iese, ai greșit undeva.

## Greșeli frecvente

1. Se uită simetria și se completează doar jumătate din matrice.
2. Se numără muchiile fără să se împartă la 2.
3. Se pune 1 pe diagonala principală. Un nod nu e adiacent cu el însuși (fără bucle).