Într-un articol mai vechi am discutat despre noțiunile de bază ale teoriei grafurilor. Acum se pune problema următoare: Cum putem reprezenta eficient un graf în C++? Altfel spus, cum putem reține informațiile necesare pentru prelucrarea unui graf? Voi analiza cele mai cunoscute trei metode: lista de muchii, matricea de adiacență și listele de adiacență.

Pentru a înțelege acest articol, aveți nevoie de cunoștințele următoare:

  • lower_bound și upper_bound: Am discutat despre cele două funcții în articolul despre căutarea binară.
  • std::vector: Iată documentația oficială despre acest container STL aici.
  • Definirea propriilor criterii de sortare. Am scris despre asta în articolul despre funcția sort.

Reprezentarea grafurilor prin lista de muchii

O soluție naivă este să reținem o listă cu toate muchiile (sau arcele) grafului. Pentru asta, putem folosi o matrice cu două coloane astfel: mat[i][0] și mat[i][1] ar fi extremitățile muchiei i. Dacă există costuri pe muchiile grafului, le putem reține adăugând încă o coloană la matrice: mat[i][2] ar fi costul muchiei i.

Exemplu: Reprezentarea unui graf prin lista de muchii

Totuși, ar fi mai elegant să definim un struct numit Edge (muchie în engleză) care să rețină informațiile aferente unei muchii. Deci, pentru stocarea muchiilor vom reține un vector cu elemente de tipul Edge. Un avantaj al utilizării unui struct este că va fi mai ușor să definim un criteriu de comparare pentru ce vom face în continuare.

Am definit și un constructor ce primește ca parametri două numere cu care care inițializează extremitățile muchiei curente. M-am săturat să primesc warning-uri pentru instrucțiuni de genul v.push_back({x, y}), așa că le-am înlocuit cu v.push_back(Edge(x, y)) 🙂 Ce trebuie să știți este că apelul Edge(x, y) returnează un obiect nou de tipul Edge, inițializat folosind constructor-ul de mai sus.

Acum urmează să vedem cum putem efectua operații obișnuite legate de muchii folosind acest mod de reprezentare. Este vorba de accesarea, ștergerea și inserarea unei muchii noi, precum și despre parcurgerea vecinilor unui nod.

Accesarea unei muchii

Pentru a accesa o muchie, sau a verifica dacă aceasta există, trebuie să o căutăm în vector. Desigur, căutarea liniară ar fi foarte slabă din punct de vedere al complexității. Soluția este să folosim căutare binară, însă pentru asta trebuie să menținem vectorul sortat după fiecare operație. Un criteriu simplu de sortare este:

Această funcție de comparare va fi apelată peste tot în locul operatorului < pentru variabilele de tipul Edge. Deci și în cadrul căutării binare, care va arăta obișnuit. Datorită acesteia, complexitatea accesării unei muchii va fi $O(\log_2 n)$.

Ștergerea unei muchii

Pentru a șterge o muchie, căutăm binar muchia respectivă în vector, și mutăm cu o poziție la stânga toate elementele care o succed. Complexitatea este $O(n + \log_2 n)$.

Inserarea unei muchii

Pentru a insera o muchie, căutăm binar în vector prima muchie mai mare sau egală cu aceasta. Apoi o mutăm atât pe ea, cât și pe cele care o succed, cu o poziție la dreapta, pentru a-i face loc muchiei noi, pe care o vom reține pe poziția găsită. Complexitatea este din nou $O(n + \log_2 n)$.

Parcurgerea vecinilor unui nod

Pentru a parcurge nodurile adiacente unui nod dat x, trebuie să știm prima și ultima poziție cu muchii de forma $[x, y]$. Pe ambele le putem determina prin câte o căutare binară. Apoi, afișăm toate muchiile cuprinse între ele (inclusiv). Complexitatea este $O(nrVecini + \log_2 n)$.

Pentru căutarea celor două muchii, am definit un criteriu de comparare cmp, care este folosit pentru a căuta muchii doar după prima extremitate a lor:

Sursă demonstrativă în C++

Mai jos este o sursă demonstrativă pentru reținerea unui graf neorientat prin lista sa de muchii. Aceasta prezintă o listă de muchii definită global și implementează funcții pentru operațiile descrise mai sus. Se poate observa că, lucrând cu grafuri neorientate, în funcțiile pentru inserare și ștergere, am lucrat atât cu muchia $[i, j]$, cât și cu muchia $[j, i]$. Sursa poate fi adaptată foarte ușor pentru grafurile orientate.

Reprezentarea grafurilor prin matricea de adiacență

Un mod mult mai bun de reprezentare a unui graf se realizează prin folosirea unei așa-numite matrice de adiacență. Aceasta are numărul de linii și numărul de coloane egale cu numărul de noduri ale grafului. Dacă e să o notăm cu ad (de la adiacență), pe ad[i][j] se găsește valoarea true dacă există muchie de la nodul i la nodul j, sau false dacă nu.

Dacă există cost pe muchiile grafului, acesta poate fi stocat în matricea de adiacență, doar că aceasta își va schimba numele în matrice de ponderi. Dacă există muchia $[i, j]$, pe ad[i][j] s-ar reține costul acesteia. Dacă nu, ad[i][j] ar avea o valoare pe care nu o poate avea niciun cost (de obicei $0$).

Exemplu: Reprezentarea unui graf prin matricea de adiacență

Se poate observa că în cazul unui graf neorientat, matricea de adiacență este simetrică după diagonala principală. Altfel spus, ad[i][j] are aceeași valoare cu ad[j][i]. Este evident, din moment ce $[i, j]$ și $[j, i]$ se referă de fapt la aceeași muchie.

Accesarea, inserarea și ștergerea unei muchii

Operațiile de accesare, inserare și ștergere se produc în $O(1)$, accesând și modificând elemente din matrice. Însă, la grafurile neorientate trebuie avută un pic de grijă: La inserarea sau ștergerea muchiei $[i, j]$, trebuie actualizate atât ad[i][j], cât și ad[j][i].

Parcurgerea vecinilor unui nod

Parcurgerea vecinilor unui nod i are complexitatea $O(n)$, unde n este numărul de noduri din graf: Trebuie parcursă întreaga linie i din matrice, și vor fi prelucrate doar elementele cu valoarea true.

Sursă demonstrativă în C++

Iată o sursă demonstrativă pentru reținerea unui graf neorientat prin matricea sa de adiacență. Din nou, ea este gândită pentru grafuri neorientate, însă poate fi adaptată extrem de ușor la grafuri orientate.

Reprezentarea grafurilor prin liste de adiacență

O altă soluție este să reținem câte o listă de adiacență pentru fiecare nod al grafului. Mai exact, lista de adiacență a unui nod va reține nodurile adiacente la acesta. Pentru implementare am putea folosi o matrice, iar fiecare linie i să fie lista de adiacență a nodului i. Însă, n-ar fi o idee prea eficientă ca memorie, pentru că s-ar reține o grămadă de poziții libere la finalul fiecărei linii. Listele ar trebui să fie alocate dinamic, ca să nu ocupe decât atâtea elemente câți vecini are nodul respectiv. Ca să simplific lucrurile, pentru liste am folosit container-ul vector din STL, căci este perfect pentru ce avem nevoie.

Exemplu: Reprezentarea unui graf prin liste de adiacență

Putem menține listele sortate, însă asta are rost doar dacă va trebui să facem multe inserări și ștergeri de muchii, pentru că astfel vom putea efectua căutări binare. Altfel, lucrurile sunt mult mai simple.

Accesarea unei muchii

Pentru a accesa o muchie $[i, j]$, trebuie doar să căutăm binar nodul j în lista de adiacență a nodului i. Complexitatea este $O(\log_2 nrVecini)$.

Ștergerea unei muchii

Pentru a șterge o muchie $[i, j]$, căutăm binar nodul j în lista nodului i; apoi îl ștergem similar modului descris în cazul listei de muchii. Complexitatea este $O(nrVecini + \log_2 nrVecini)$.

Inserarea unei muchii

Căutăm binar în lista lui i primul nod mai mare sau egal cu j și îl inserăm pe j imediat înaintea lui, ca mai sus. Complexitatea este din nou $O(nrVecini + \log_2 nrVecini)$.

Totuși, putem face inserarea în $O(1)$, atât timp cât nu ne interesează să avem listele sortate pentru căutări binare. Trebuie doar să adăugăm nodul j la sfârșitul listei i, cât și invers dacă graful este neorientat:

Parcurgerea vecinilor unui nod

Pentru a parcurge nodurile adiacente unui nod dat, trebuie doar să-i parcurgem lista de adiacență. Complexitatea este $O(nrVecini)$.

Sursă demonstrativă în C++

Mai jos este o sursă demonstrativă pentru reținerea unui graf neorientat prin liste de adiacență. Din nou, sursa poate fi modificată ușor ca să funcționeze pentru grafuri orientate.

Concluzii

Reprezentarea unui graf prin lista de muchii este cea mai proastă metodă, deoarece este greu de implementat (în varianta cea mai bună), și totodată foarte ineficientă. Una dintre foarte puținele aplicații practice ale listei de muchii este Algoritmul lui Kruskal.

Matricea de adiacență și listele de adiacență sunt cele mai folosite metode. Prima are cea mai bună complexitate pentru manipularea muchiilor, însă consumă cea mai multă memorie, și nu permite o parcurgere prea eficientă a vecinilor unui nod. Listele de adiacență sunt însă cele mai bune la capitolul din urmă, iar consumul de memorie al acestora depinde doar de numărul de muchii.

Alegerea celei mai potrivite metode de reprezentare a unui graf depinde foarte mult de restricțiile problemei. De obicei însă, matricea de adiacență este mai bună pentru grafurile dense (cu multe muchii), iar listele de adiacență sunt mai bune pentru grafurile rare (cu puține muchii).

Dacă aveți vreo întrebare legată de metodele de reprezentare a grafurilor în C++, nu ezitați să o adresați într-un comentariu, mai jos 🙂

Îți place conținutul acestui site?

Dacă vrei să mă susții în întreținerea server-ului și în a scrie mai multe articole de calitate pe acest blog, mă poți ajuta printr-o mică donație. Află aici cum o poți face!