Reprezentarea grafurilor: matrice și liste de adiacență

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]:

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

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).

#include <iostream>
using namespace std;

int main() {
    int n, m, a[101][101] = {0};
    cin >> n >> m;
    for (int k = 0; k < m; k++) {
        int x, y;
        cin >> x >> y;
        a[x][y] = 1;
        a[y][x] = 1;
    }
    for (int i = 1; i <= n; i++) {
        int grad = 0;
        for (int j = 1; j <= n; j++) grad += a[i][j];
        cout << "d(" << i << ")=" << grad << " ";
    }
    return 0;
}