Grafuri orientate și neorientate: explicații simple și exemple pentru BAC

Grafurile sună complicat, dar de fapt sunt una dintre cele mai naturale idei din informatică. Harta unui oraș, prietenii dintr-o rețea socială, paginile legate prin linkuri — toate sunt grafuri. La BAC apar des, așa că hai să le înțelegem împreună, pas cu pas.

Ce este un graf

Un graf este o mulțime de noduri (numite și vârfuri) legate între ele prin muchii. Atât. Nodurile sunt "obiectele", iar muchiile arată relațiile dintre ele.

Gândește-te la o hartă cu orașe: fiecare oraș e un nod, iar fiecare drum care leagă două orașe e o muchie. Dacă vrei să știi cum ajungi din orașul A în orașul B, de fapt cauți un drum prin graf.

Notăm de obicei numărul de noduri cu n și numărul de muchii cu m. Nodurile le numerotăm 1, 2, ..., n ca să le putem manipula ușor în program.

Orientat vs. neorientat: care e diferența?

Aici e prima decizie importantă. Diferența ține de sensul muchiilor.

Într-un graf neorientat, muchia dintre nodurile u și v merge în ambele sensuri. Dacă A e legat de B, atunci și B e legat de A. Exemplu clasic: o prietenie — dacă tu ești prieten cu cineva, și acea persoană e prietenă cu tine.

Într-un graf orientat, muchiile au o direcție, ca niște săgeți. O muchie de la u la v nu înseamnă automat că există și una de la v la u. Exemplu: pe o rețea socială poți urmări pe cineva fără ca acea persoană să te urmărească înapoi.

Caracteristică	Neorientat	Orientat
Sensul muchiei	dublu (în ambele direcții)	unic (cu săgeată)
Exemplu	drumuri cu dublu sens	străzi cu sens unic
Matrice de adiacență	simetrică	nu neapărat simetrică
Tip de grad	un singur grad	grad intern și grad extern

Reține ideea cheie:

Într-un graf neorientat, o muchie e o relație reciprocă. Într-un graf orientat, o muchie e o relație într-un singur sens — de la cine pleacă săgeata, către cine arată.

Cum reprezinți un graf

Calculatorul nu vede desene cu cercuri și săgeți. Trebuie să-i dai graful sub o formă pe care o poate stoca. Ai două variante principale.

Matricea de adiacență

Este o matrice pătratică a de dimensiune n x n. Elementul a[i][j] este 1 dacă există muchie de la nodul i la nodul j, și 0 altfel.

La un graf neorientat, matricea e simetrică: dacă a[i][j] = 1, atunci și a[j][i] = 1.

Iată cum citești o matrice de adiacență pentru un graf neorientat în C++:

#include <iostream>
using namespace std;

int a[101][101];
int n, m;

int main() {
    cin >> n >> m;        // numărul de noduri și de muchii
    for (int k = 0; k < m; k++) {
        int x, y;
        cin >> x >> y;    // muchie între nodurile x și y
        a[x][y] = 1;
        a[y][x] = 1;      // graf neorientat => simetric
    }
    return 0;
}

Dacă graful ar fi orientat, ai scrie doar a[x][y] = 1; și ai renunța la linia simetrică.

Matricea de adiacență e simplă de înțeles și verifici instant dacă există o muchie între două noduri. Dezavantajul: ocupă n x n memorie, chiar dacă graful are puține muchii.

Listele de adiacență

Pentru fiecare nod ții o listă cu vecinii lui (nodurile cu care e legat direct). Este mai eficientă când graful are multe noduri, dar puține muchii.

#include <iostream>
#include <vector>
using namespace std;

vector<int> vecini[101];
int n, m;

int main() {
    cin >> n >> m;
    for (int k = 0; k < m; k++) {
        int x, y;
        cin >> x >> y;
        vecini[x].push_back(y);
        vecini[y].push_back(x);   // pentru graf neorientat
    }
    return 0;
}

Acum vecini[i] îți spune direct cu cine e legat nodul i, fără să mai parcurgi o întreagă linie de zerouri.

Gradul unui nod

Gradul unui nod îți spune câte muchii ies din el. E o noțiune care apare aproape sigur la BAC.

La un graf neorientat, gradul nodului i este numărul de vecini ai lui. În matricea de adiacență, e suma elementelor de pe linia i.

La un graf orientat ai două grade:

• Gradul extern (sau de ieșire): câte săgeți pleacă din nod.
• Gradul intern (sau de intrare): câte săgeți ajung în nod.

Un nod cu gradul 0 se numește nod izolat — nu e legat de nimic. Reține și o proprietate frumoasă: într-un graf neorientat, suma gradurilor tuturor nodurilor este egală cu 2 * m (fiecare muchie contribuie cu 1 la gradul fiecăruia dintre cele două capete).

Parcurgerea grafului: DFS și BFS

Adesea vrei să "vizitezi" toate nodurile la care poți ajunge pornind dintr-un nod. Există două strategii fundamentale de parcurgere.

DFS (Depth-First Search) — parcurgerea în adâncime. Pornești dintr-un nod, mergi cât poți de "adânc" pe un drum, și abia când te blochezi te întorci și încerci altă ramură. Se implementează natural cu recursivitate.

BFS (Breadth-First Search) — parcurgerea în lățime. Vizitezi întâi toți vecinii direcți ai nodului de start, apoi vecinii vecinilor, ca niște cercuri care se lărgesc. Se implementează cu o coadă și e ideală pentru drumul cel mai scurt în număr de muchii.

Iată un DFS simplu, recursiv, folosind matricea de adiacență:

#include <iostream>
using namespace std;

int a[101][101];
int vizitat[101];
int n;

void dfs(int nod) {
    vizitat[nod] = 1;
    cout << nod << " ";
    for (int j = 1; j <= n; j++) {
        if (a[nod][j] == 1 && vizitat[j] == 0) {
            dfs(j);   // mergem mai adânc, către vecinul nevizitat
        }
    }
}

int main() {
    // ... aici citești n, m și completezi matricea a ...
    dfs(1);   // pornim parcurgerea din nodul 1
    return 0;
}

Vectorul vizitat e esențial: fără el, programul ar intra la nesfârșit pe muchiile deja folosite. De fiecare dată când ajungi într-un nod nou, îl marchezi ca vizitat, ca să nu-l mai procesezi a doua oară.

Cu DFS și BFS poți răspunde la întrebări tipice de BAC: câte componente conexe are graful, dacă există drum între două noduri, sau în ce ordine sunt vizitate nodurile.

Sfaturi practice pentru BAC

• Citește cu atenție enunțul: scrie clar dacă graful e orientat sau neorientat. De asta depinde dacă adaugi muchia în ambele sensuri.
• Numerotează nodurile de la 1, ca în majoritatea subiectelor, și folosește indici de la 1 la n în program.
• Inițializează mereu vectorul vizitat cu 0 înainte de parcurgere.
• Exersează ambele reprezentări — la unele probleme matricea e mai comodă, la altele listele sunt mult mai rapide.

Concluzie

Grafurile par intimidante doar până le vezi clar: noduri, muchii și relațiile dintre ele. Odată ce înțelegi diferența orientat / neorientat, cum le reprezinți și cum le parcurgi cu DFS și BFS, ai deja baza pe care se construiesc majoritatea subiectelor de BAC.

La ByteSchool exersezi exact aceste noțiuni cu probleme reale și cu mentori care lucrează în tech, ca să ajungi la examen cu codul în degete, nu doar în cap. Pas cu pas, de la prima muchie până la algoritmi adevărați pe grafuri.