Grafuri: noțiuni și matricea de adiacență în C++

Ce reprezintă un graf

O rețea de localități și drumurile directe dintre ele poate fi descrisă printr-un graf. Localitățile devin vârfuri, iar legăturile directe devin muchii. Poziția punctelor pe desen nu influențează graful: contează doar ce perechi sunt legate. Două linii care se intersectează pe hârtie nu creează automat un vârf nou.

În această lecție lucrăm cu grafuri neorientate, simple. O muchie între x și y poate fi parcursă în ambele sensuri. Nu există bucle, adică muchii de la un vârf la el însuși, și nici muchii repetate între aceeași pereche. Notăm numărul de vârfuri cu n, iar numărul de muchii cu m. Vârfurile sunt numerotate de la 1 la n.

Două vârfuri sunt adiacente dacă au o muchie între ele. Gradul unui vârf este numărul muchiilor incidente cu el. Un vârf de grad zero este izolat, dar face în continuare parte din graf. De aceea citim n separat, fără să încercăm să deducem toate vârfurile din muchii.

De la desen la matrice

Matricea de adiacență are a[i][j] = 1 dacă există muchia dintre i și j, respectiv 0 în caz contrar. Inițial toate elementele sunt zero. La citirea unei muchii atribuim atât a[x][y], cât și a[y][x]. Matricea este simetrică față de diagonala principală. Diagonala conține numai zero, deoarece nu avem bucle.

Imagine indisponibilă: Graful cu muchiile 1-2, 1-3, 2-4 și 3-4 are vârful 5 izolat; matricea simetrică are câte două valori unu pe primele patru linii.

În exemplul ilustrat, linia vârfului 1 este 0 1 1 0 0. Suma ei este 2, exact gradul lui 1. Linia lui 5 conține doar zerouri. Suma tuturor gradelor este 8, dublul celor patru muchii, deoarece fiecare muchie contribuie la două grade.

Program: gradele tuturor vârfurilor

Citirea începe cu n m, urmate de m perechi de capete. Presupunem date valide: 1 <= n <= 100, 0 <= m <= n*(n-1)/2, capete distincte în intervalul 1..n și perechi nerepetate. Programul afișează gradele vârfurilor în ordinea numerelor lor, pe o singură linie.

În varianta clasică, a[101][101] rezervă capacitatea maximă, iar zona folosită este 1..n pe fiecare direcție. Linia și coloana zero nu sunt utilizate. Acoladele goale inițializează inclusiv elementele folosite la zero. În varianta cu std::vector, alocăm n+1 linii de câte n+1 elemente și păstrăm aceeași numerotare. Nu folosim tablouri cu dimensiune variabilă.

Varianta clasică, cu tablouri

#include <iostream>

int main() {
    int n, m;
    std::cin >> n >> m;
    int a[101][101] = {};
    for (int i = 0; i < m; ++i) {
        int x, y;
        std::cin >> x >> y;
        a[x][y] = 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];
        if (i > 1) std::cout << ' ';
        std::cout << grad;
    }
    std::cout << '\n';
}

Varianta echivalentă cu std::vector

#include <iostream>
#include <vector>

int main() {
    int n, m;
    std::cin >> n >> m;
    std::vector<std::vector<int>> a(n + 1, std::vector<int>(n + 1, 0));
    for (int i = 0; i < m; ++i) {
        int x, y;
        std::cin >> x >> y;
        a[x][y] = 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];
        if (i > 1) std::cout << ' ';
        std::cout << grad;
    }
    std::cout << '\n';
}

Pentru 5 4, urmat de muchiile 1 2, 1 3, 2 4, 3 4, rezultatul este 2 2 2 2 0. Cele două programe au aceleași date de intrare și același rezultat.

Cost și greșeli frecvente

Calculul gradelor examinează n*n poziții, deci are timp O(n²). Citirea costă O(m), iar matricea folosește O(n²) memorie în funcție de dimensiunea aleasă; tabloul clasic rezervă efectiv 101 pe 101 elemente indiferent de n. Testarea existenței unei muchii este O(1).

O listă de vecini stochează pentru fiecare vârf doar vârfurile adiacente. Ea ocupă O(n+m) memorie și este utilă pentru grafuri rare, dar nu este reprezentarea utilizată de programele de aici. std::vector<std::vector<int>> din exemplu este tot o matrice, nu o listă de vecini.

Dacă completezi numai a[x][y], programul modelează greșit o muchie neorientată. Dacă numerotezi vârfurile de la unu într-un tablou cu exact n elemente, accesul la indicele n este în afara lui. Revino la matrice dacă indicii nu sunt încă limpezi.

Exersează

1. Pentru muchiile 1-2, 1-3, 1-4, scrie gradele celor patru vârfuri.
2. Ce matrice obții pentru trei vârfuri fără muchii?
3. De ce suma gradelor nu poate fi impară într-un graf neorientat simplu?

Răspunsuri: 3 1 1 1; o matrice de trei pe trei cu toate valorile zero; fiecare muchie contribuie exact cu doi la sumă. Continuă cu parcurgerile, unde matricea ne ajută să găsim vârfurile accesibile.